LZMA

LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм стиснення даних, розроблюваний від 1996 або 1998 року Ігорем Павловим.^[1] Використовується в архіваторі 7-Zip того ж автора для створення стиснутих архівів у форматі 7z.

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

Також 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^[3]. Від 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-патчем^[4][5].

Крім цього, LZMA використовується в реалізаціях UEFI як один з алгоритмів стиснення.

LZMA2

LZMA2 — нова версія алгоритму LZMA. Цей алгоритм має такі переваги перед алгоритмом LZMA:

• вихідний потік може містити одночасно нестиснені і стиснені дані (нестисні дані записуються як є, що економить біти).
• краща підтримка багатонитковості під час стискання і розпакування.

Примітки

1. Игорь Павлов несколько раз заявлял на SourceForge, что алгоритм LZMA создан им. (19 лютого 2004). LZMA spec?. Архів оригіналу за 9 листопада 2012. Процитовано 16 червня 2013.
2. 7z Format. Архів оригіналу за 3 квітня 2011. Процитовано 20 жовтня 2020.
3. LZMA utils [Архівовано 27 жовтня 2020 у Wayback Machine.](англ.)
4. squashfs на SourceForge.net
5. Официальный сайт squashfs-lzma. Архів оригіналу за 29 жовтня 2012. Процитовано 20 жовтня 2020.

Посилання

• Офіційний сайт 7-Zip [Архівовано 12 травня 2006 у Wayback Machine.]
• LZMA SDK [Архівовано 2 лютого 2021 у Wayback Machine.]