LZMA

LZMA (сокращение от англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных, разрабатываемый с 2001 года, используется в архиваторе 7-Zip для создания сжатых архивов в формате 7z . Алгоритм основан на схеме сжатия данных по словарю, сходной с использованной в LZ77 и обеспечивает высокий коэффициент сжатия (обычно превышающий коэффициент, получаемый при сжатии с использованием bzip2), а также позволяет использовать словари различного размера (до 4 ГиБ).

Обзор

Библиотека сжатия с открытым исходным кодом LZMA, написанная на языке C++, использует улучшенный алгоритм компрессии LZ77, дополненный алгоритмом кодирования расстояний, а также специальными процедурами для обработки двоичных файлов.

LZMA поддерживает различные варианты хэш-цепочек, двоичных и префиксных деревьев в качестве основы алгоритмов поиска по словарю.

Алгоритмы для сжатия исполняемых файлов BCJ/BCJ2

LZMA SDK содержит алгоритм сжатия BCJ/BCJ2, реализованный для процессоров x86, ARM, PowerPC, IA64 и 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.^[1] В 2008 году она начинает всё чаще использоваться в системах управления пакетами — в частности, dpkg и RPM.

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

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

Некоторые сетевые устройства (вроде US Robotics 9105 и 9106) в качестве микропрограммы используют модифицированный Linux, загружаемый со сжатой файловой системы. В качестве алгоритма сжатия файловой системы вместо ZLIB используется алгоритм LZMA.

Примечания

См. также

• LZW

Ссылки

• Официальный сайт 7-Zip
• LZMA SDK
• p7zip Unix port of command-line utilities
• PyLZMA Python Wrapper
• Nullsoft Installer uses LZMA
• Inno Setup supports LZMA
• Compress home page
• LZMA support for cramfs filesystem
• FreeArc archiver and Haskell interface to the LZMA library
• Pascal port of the LZMA SDK

Это незавершённая статья о компьютерах. Вы можете помочь проекту, исправив и дополнив её.