LZMA

Материал из Википедии — свободной энциклопедии

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

Содержание

1 Обзор
2 Алгоритмы для сжатия исполняемых файлов BCJ/BCJ2
3 Реализация 7-Zip
4 См. также
5 Ссылки

[править] Обзор

Библиотека сжатия с открытым исходным кодом 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-битная адресация).

[править] Реализация 7-Zip

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

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

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

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

Также есть Unix-порт LZMA, представляющий из себя только реализацию алгоритма для создания поточных архиваторов подобных gzip. Это не архиватор, поэтому нет формата файла, как такового.

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

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

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

[править] См. также

[править] Ссылки

Методы сжатия

Методы сжатия без потерь	Теория: Энтропия · Сложность · Избыточность Энтропийное сжатие: Алгоритм Хаффмана · Адаптивный алгоритм Хаффмана · Арифметическое сжатие (Алгоритм Шеннона — Фано · Интервальное) · Коды Голомба · Дельта · Универсальный код (Elias · Fibonacci) Словарные методы: LZ77/78 · LZW · LZO · DEFLATE · LZMA · LZX Другие: RLE · BWT · PPM
Методы сжатия аудио	Теория: Свертка · PCM · Алиасинг · Теорема Котельникова Составные части аудиокодеков: LPC (LAR · LSP) · WLPC · CELP · ACELP · A-law · Mu-law · MDCT · Преобразование Фурье · Психоакустичская модель Разное: Dynamic range compression · Speech compression · Sub-band coding
Методы сжатия изображений	Термины: Цветовая модель · Пиксел · Прореживание цвета · Артефакты сжатия Методы: RLE · Фрактальный · Wavelet · SPIHT · ДКП · ПКЛ Разное: Битрейт · Сжатие с вейвлет · PSNR ·
Сжатие видео	Термины: Характеристики видео · Кадр · Типы кадров · Качество видео Составные части видеокодеков: Компенсация движения · ДКП · Квантование Разное: Видео кодеки · Rate distortion theory (CBR · ABR · VBR)