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. LZMA utils(англ.)
  4. squashfs на SourceForge.net
  5. Официальный сайт squashfs-lzma

Посилання
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.