LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных, разрабатываемый с 2001 года. Используется в архиваторе 7-Zip для создания сжатых архивов в формате 7z.

Алгоритм основан на схеме сжатия данных по словарю, сходной с использованной в LZ77, и обеспечивает высокий коэффициент сжатия (обычно превышающий коэффициент, получаемый при сжатии с использованием bzip2), а также позволяет использовать словари различного размера (до 4 Гб^[1]).

Так же 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-битная адресация).

Реализации

Реализация, доступная по лицензии GNU LGPL, имеет следующие свойства:

• Скорость сжатия: примерно 1 Мб/с на процессоре с частотой 2 ГГц.
• Скорость извлечения: около 10—20 Мб/с на процессоре с частотой 2 ГГц.
• Поддержка многопоточности и технологии Hyper-threading, впервые реализованной в процессоре Pentium 4.

Размер кода распаковки LZMA составляет порядка 5 Кб; расход динамической памяти зависит от размера словарей. Эти возможности позволяют реализовать распаковку на встраиваемых системах.

Использование особенностей Microsoft Windows в исходном коде усложняет создание версий программы для Unix. Тем не менее, существует две работоспособные портированные версии: в p7zip более или менее портированы версии утилит командной строки 7z и 7za для POSIX-систем (GNU/Linux, Solaris, OpenBSD, FreeBSD, Cygwin и других), Mac OS X и BeOS.

Также есть официальная портируемая реализация — LZMA Utils, предназначенная для создания поточных компрессоров подобных gzip.^[2] С 2008 года она начинает всё чаще использоваться в системах управления пакетами — в частности, dpkg и RPM.

7-Zip использует достаточно гибкий формат архива, его поддерживает и некоторые сторонние утилиты (например, чтение 7z поддерживает WinRAR).

Также существует порт 7-Zip для Mac OS X, который называется Compress, в настоящее время представляющий из себя достаточно недоработанный инструмент. Для Mac OS X существуют ещё сборки p7zip и 7zX.

Для работы с 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-патчем.^[3][4]

Примечания