LZMA¶

LZMA (от англ. Lempel-Ziv-Markov chain algorithm) — это алгоритм сжатия данных без потерь, разработанный Игорем Павловым и впервые опубликованный в 1998 году. Алгоритм лежит в основе формата архивов 7z, используемого архиватором 7-Zip. LZMA характеризуется высокой степенью сжатия, сравнимой с лучшими арифметическими кодировщиками, при относительно умеренных требованиях к оперативной памяти для декомпрессии.

¶История

Разработка LZMA началась в конце 1990-х годов российским программистом Игорем Павловым. Первая реализация была включена в состав архиватора 7-Zip (версия 2.30 Beta, 1999 год). Алгоритм был создан как альтернатива распространённым на тот момент методам сжатия, таким как Deflate (используется в ZIP и gzip) и BZip2. Целью было достижение максимально возможной степени сжатия для широкого спектра типов данных, особенно для исполняемых файлов и текстов.

В 2001 году исходный код LZMA был опубликован под лицензией LGPL, что способствовало его широкому распространению. В 2007 году алгоритм был включён в стандарт 7z (формат архива). Позднее, в 2009 году, была выпущена модификация LZMA2, которая улучшила поддержку многопоточности и добавила возможность сжатия данных с переменным размером словаря.

¶Принцип работы

LZMA является гибридным алгоритмом, сочетающим два основных подхода:

• Скользящее окно (словарное сжатие): Основано на алгоритме LZ77. Алгоритм ищет повторяющиеся последовательности байтов в пределах скользящего окна (словаря) и заменяет их ссылками на ранее встреченные фрагменты. Размер словаря может варьироваться от 64 КБ до 1 ГБ (в реализации 7-Zip).
• Марковское моделирование (контекстное моделирование): Используется для кодирования длин совпадений и расстояний. Алгоритм строит вероятностные модели для последовательностей символов, что позволяет более эффективно сжимать данные, где повторения не являются точными (например, в тексте).

Ключевой элемент — арифметическое кодирование (точнее, его вариант — интервальное кодирование), которое используется для финального сжатия битового потока. В отличие от алгоритма Хаффмана, арифметическое кодирование позволяет кодировать символы с дробным количеством бит, что даёт выигрыш в степени сжатия на 5–10 % для случайных данных.

¶Схема работы

1. Поиск совпадений: Алгоритм просматривает входной поток байтов и ищет в скользящем окне (словаре) максимально длинные последовательности, совпадающие с текущей позицией.
2. Кодирование совпадений: Для каждого найденного совпадения кодируются три параметра:

• Расстояние (смещение в словаре).
• Длина совпадения (количество совпадающих байтов).
• Флаг (совпадение или литерал — новый байт).

1. Моделирование контекста: Для кодирования расстояний и длин используется цепь Маркова. Вероятность появления конкретного значения зависит от предыдущих кодированных значений (контекста). Например, если недавно встречались короткие совпадения, вероятность появления длинного совпадения снижается.
2. Арифметическое кодирование: Вероятностные оценки из марковской модели подаются на вход арифметического кодера, который генерирует выходной битовый поток.

¶Характеристики

¶Параметры сжатия

Основные параметры, влияющие на работу LZMA:

• Размер словаря (Dictionary Size): Определяет объём памяти, используемый для поиска совпадений. Чем больше словарь, тем выше степень сжатия, но больше время сжатия и требования к оперативной памяти. Типичные значения: 1–64 МБ.
• Размер цепочки совпадений (Match Finder Cycles): Влияет на глубину поиска совпадений. Большие значения увеличивают степень сжатия, но замедляют работу.
• Размер блока (Block Size): В LZMA2 данные разбиваются на блоки, что позволяет обрабатывать их независимо и ускоряет декомпрессию.
• Степень сжатия (Compression Level): В 7-Zip задаётся от 0 (быстро, низкая степень) до 9 (максимальная степень, медленно).

¶Сравнение с другими алгоритмами

¶Применение

LZMA широко используется в различных областях:

• Архивация и сжатие файлов: Формат 7z (основной), а также поддержка в архиваторах WinRAR, PeaZip, Keka и других. Используется для сжатия больших объёмов данных, включая дистрибутивы программного обеспечения, образы дисков и резервные копии.
• Сжатие прошивок и встраиваемых систем: Благодаря низким требованиям к памяти для декомпрессии (достаточно нескольких килобайт), LZMA применяется в микроконтроллерах, загрузчиках и прошивках BIOS/UEFI. Например, ядро Linux сжимается с помощью LZMA.
• Сжатие текстовых данных: В форматах документов (например, OpenDocument) и базах данных.
• Сжатие потокового видео и аудио: В некоторых кодеках (например, LZMA используется в аудиокодеке TAK для сжатия без потерь).
• Программное обеспечение: Входит в состав многих утилит (xz, lzma, 7z) и библиотек (liblzma, XZ Utils).

¶LZMA2

LZMA2 — это улучшенная версия алгоритма, выпущенная в 2009 году. Основные отличия:

• Поддержка многопоточности: Данные разбиваются на независимые блоки, которые могут сжиматься параллельно на многоядерных процессорах.
• Переменный размер словаря: Словарь может меняться от блока к блоку, что позволяет адаптироваться к разным типам данных в одном потоке.
• Улучшенное кодирование: Введена поддержка сжатия данных с переменной длиной блока и улучшено кодирование расстояний.

LZMA2 является стандартом по умолчанию для формата 7z в архиваторе 7-Zip начиная с версии 9.04.

¶Критика и ограничения

• Высокие требования к памяти при сжатии: Для достижения максимальной степени сжатия (уровень 9) требуется до 1 ГБ оперативной памяти, что может быть проблематично для старых или маломощных систем.
• Низкая скорость сжатия: Алгоритм значительно медленнее Deflate или LZ4, особенно при больших словарях. Для задач, где важна скорость (например, сжатие в реальном времени), LZMA неприменим.
• Отсутствие поддержки потокового сжатия в классической реализации: В отличие от gzip, LZMA изначально не предназначен для сжатия непрерывных потоков данных (например, для сетевых протоколов). LZMA2 частично решает эту проблему.
• Сложность реализации: Алгоритм требует аккуратной реализации арифметического кодирования и марковских моделей, что усложняет его внедрение в простые программы.

¶Интересные факты

• Исходный код LZMA был включён в ядро Linux в 2007 году как один из методов сжатия для initramfs.
• Алгоритм используется в формате сжатия XZ (LZMA2), который является стандартным для многих дистрибутивов Linux (например, для сжатия пакетов .deb и .rpm).
• В 2014 году была выпущена версия LZMA с поддержкой аппаратного ускорения (LZMA-HW) для FPGA, что позволило достичь скорости сжатия до 10 Гбит/с.

¶Источники

• Игорь Павлов. «7-Zip: LZMA SDK» (документация к LZMA SDK, 2001–2020).
• Salomon, D. (2007). Data Compression: The Complete Reference (4th ed.). Springer.
• Sayood, K. (2017). Introduction to Data Compression (5th ed.). Morgan Kaufmann.
• Спецификация формата 7z (7z Format Specification, 2007–2019).