Interested Article - LZMA
- 2021-03-27
- 1
LZMA ( англ. Lempel-Ziv-Markov chain-Algorithm ) — алгоритм сжатия данных , разрабатываемый с 1996 или 1998 года Игорем Павловым . Используется в архиваторе 7-Zip того же автора для создания сжатых архивов в формате 7z.
Алгоритм основан на схеме сжатия данных по словарю , сходной с использованной в LZ77 , и обеспечивает высокий коэффициент сжатия (обычно превышающий коэффициент, получаемый при сжатии с использованием bzip2 ), а также позволяет использовать словари различного размера (до 4 Гб ).
Также lzma — утилита командной строки с открытым кодом для сжатия данных из LZMA SDK , которая работает с файлами, имеющими формат и расширение .lzma.
Обзор
Комплект средств разработки с открытым исходным кодом LZMA, написанный на языке C++ , использует улучшенный алгоритм сжатия LZ77 , дополненный алгоритмом интервального кодирования , а также специальными процедурами для обработки двоичных файлов.
LZMA поддерживает различные варианты хеш-цепочек , двоичных и префиксных деревьев в качестве основы алгоритмов поиска по словарю.
Алгоритмы BCJ/BCJ2 для исполняемых файлов
LZMA SDK содержит также алгоритм BCJ/BCJ2, реализованный для процессоров архитектуры x86 , ARM , PowerPC , IA-64 и ARM Thumb. В нём точки перехода перед сжатием нормализуются — то есть, например, для x86 это означает, что инструкции ближних и условных переходов и вызовы функций преобразуются из формы с относительным смещением «перейти на 1665 байт назад» в форму с абсолютным адресом «перейти к адресу 5554».
Алгоритм BCJ2, реализованный в 7-Zip , использует 32-битную адресацию. В упаковщике исполняемых файлов UPX адресация зависит от типа архитектуры (например, для исполняемых файлов DOS используется 16-битная адресация).
Реализации
Реализация, которая, начиная с версии 4.61 beta, переведена с лицензии CPL в категорию общественного достояния, имеет следующие свойства:
- Скорость сжатия: примерно 1 Мб/с на процессоре x86 с частотой 2 ГГц.
- Скорость извлечения: около 10—20 Мб/с на процессоре x86 с частотой 2 ГГц.
- Поддержка многопоточности при сжатии и распаковке.
Размер кода распаковки LZMA составляет порядка 5 Кб; расход динамической памяти зависит от размера словарей. Эти возможности позволяют реализовать распаковку на встраиваемых системах .
Использование особенностей Microsoft Windows в исходном коде усложняет создание версий программы для Unix. Тем не менее, существует две работоспособные портированные версии: в p7zip более или менее портированы версии утилит командной строки 7z и 7za для POSIX-систем ( GNU/Linux , Solaris , OpenBSD , FreeBSD , Cygwin и других), Mac OS X и BeOS .
Также есть официальная портируемая реализация — LZMA Utils, предназначенная для создания поточных компрессоров, подобных gzip . С 2008 года она начинает всё чаще использоваться в системах управления пакетами — в частности, dpkg и RPM .
7-Zip использует достаточно гибкий формат архива, его поддерживают и некоторые сторонние утилиты (например, чтение 7z поддерживает WinRAR ).
Также существует порт 7-Zip для Mac OS X, который называется Compress, в настоящее время представляющий собой достаточно недоработанный инструмент. Для Mac OS X существуют ещё сборки p7zip и .
Для работы с LZMA автор предоставляет свой кроссплаформенный SDK, обладающий вышеперечисленными свойствами. Основная часть SDK написана на C++ и изначально распространялась на условиях GNU LGPL. Стоит отметить несколько моментов:
- С версии 4.57 LZMA SDK предоставляет также ANSI C-реализации как алгоритма распаковки, так и алгоритма компрессии, что расширяет область применения SDK и упрощает использование во встраиваемых системах и иных ограниченных окружениях (например, в ядрах операционных систем).
- С версии 4.62 LZMA SDK стал доступен на условиях Public Domain , то есть допускается его использование для любых целей без каких-либо ограничений.
Некоторые сетевые устройства (вроде US Robotics 9105 и 9106) в качестве микропрограммы используют модифицированный Linux , загружаемый из сжатой файловой системы. В качестве алгоритма сжатия файловой системы вместо Zlib используется алгоритм LZMA. Как правило, такой файловой системой является squashfs с LZMA-патчем .
Кроме этого, LZMA используется в реализациях UEFI как один из алгоритмов сжатия.
LZMA2
LZMA2 — новая версия алгоритма LZMA. Данный алгоритм имеет следующие преимущества перед алгоритмом LZMA:
- выходной поток может содержать одновременно несжатые и сжатые данные (несжимаемые данные записываются как есть, что экономит биты).
- лучшая поддержка многопоточности при компрессии и декомпрессии.
Примечания
- Игорь Павлов несколько раз заявлял на SourceForge , что алгоритм LZMA создан им. (19 февраля 2004). Дата обращения: 16 июня 2013. 9 ноября 2012 года.
- . Дата обращения: 13 ноября 2009. 3 апреля 2011 года.
- от 27 октября 2020 на Wayback Machine (англ.)
- на сайте SourceForge.net
- . Дата обращения: 30 января 2009. 29 октября 2012 года.
Ссылки
- 2021-03-27
- 1