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:
- вихідний потік може містити одночасно нестиснені і стиснені дані (нестисні дані записуються як є, що економить біти).
- краща підтримка багатонитковості під час стискання і розпакування.
Примітки
- ↑ Игорь Павлов несколько раз заявлял на SourceForge, что алгоритм LZMA создан им. (19 лютого 2004). LZMA spec?. Архів оригіналу за 9 листопада 2012. Процитовано 16 червня 2013.
- ↑ 7z Format. Архів оригіналу за 3 квітня 2011. Процитовано 20 жовтня 2020.
- ↑ LZMA utils [Архівовано 27 жовтня 2020 у Wayback Machine.](англ.)
- ↑ squashfs на SourceForge.net
- ↑ Официальный сайт squashfs-lzma. Архів оригіналу за 29 жовтня 2012. Процитовано 20 жовтня 2020.
Посилання
- Офіційний сайт 7-Zip [Архівовано 12 травня 2006 у Wayback Machine.]
- LZMA SDK [Архівовано 2 лютого 2021 у Wayback Machine.]
- п
- о
- р
Ентропійний тип |
|
---|---|
Словниковий тип[en] |
|
Інші типи |
Поняття |
|
---|---|
Частини кодеків |
|
Поняття |
|
---|---|
Методи |
|
Поняття |
|
---|---|
Частини кодеків |
|
- Втратні
- Ентропія
- Квантування
- Надмірність
- Колмогоровська складність
- Швидкість — спотворення[en]
- Хронологія розвитку теорії інформації[en]
Формати стиснення даних
Програмне забезпечення для стиснення даних