LZMA

LZMA (англ. Lempel-Ziv-Markov chain-Algorithm) — алгоритм сжатия данных, разрабатываемый с 2001 года. Используется в архиваторе 7-Zip для создания сжатых архивов в формате 7z.

Алгоритм основан на схеме сжатия данных по словарю, сходной с использованной в LZ77, и обеспечивает высокий коэффициент сжатия (обычно превышающий коэффициент, получаемый при сжатии с использованием bzip2), а также позволяет использовать словари различного размера (до 4 Гб).

Также 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. С 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-патчем.

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

LZMA2

LZMA2 — новая версия алгоритма LZMA. Данный алгоритм имеет следующие преимущества перед алгоритмом LZMA:

• выходной поток может содержать одновременно несжатые и сжатые данные (несжимаемые данные записываются как есть - что экономит биты).
• Лучшая поддержка многопоточности при компрессии и декомпрессии.

Ссылки

• [www.7-zip.org/ Официальный сайт 7-Zip]
• [www.7-zip.org/sdk.html LZMA SDK]

Отрывок, характеризующий LZMA

5 ноября был первый день так называемого Красненского сражения. Перед вечером, когда уже после многих споров и ошибок генералов, зашедших не туда, куда надо; после рассылок адъютантов с противуприказаниями, когда уже стало ясно, что неприятель везде бежит и сражения не может быть и не будет, Кутузов выехал из Красного и поехал в Доброе, куда была переведена в нынешний день главная квартира.
День был ясный, морозный. Кутузов с огромной свитой недовольных им, шушукающихся за ним генералов, верхом на своей жирной белой лошадке ехал к Доброму. По всей дороге толпились, отогреваясь у костров, партии взятых нынешний день французских пленных (их взято было в этот день семь тысяч). Недалеко от Доброго огромная толпа оборванных, обвязанных и укутанных чем попало пленных гудела говором, стоя на дороге подле длинного ряда отпряженных французских орудий. При приближении главнокомандующего говор замолк, и все глаза уставились на Кутузова, который в своей белой с красным околышем шапке и ватной шинели, горбом сидевшей на его сутуловатых плечах, медленно подвигался по дороге. Один из генералов докладывал Кутузову, где взяты орудия и пленные.
Кутузов, казалось, чем то озабочен и не слышал слов генерала. Он недовольно щурился и внимательно и пристально вглядывался в те фигуры пленных, которые представляли особенно жалкий вид. Большая часть лиц французских солдат были изуродованы отмороженными носами и щеками, и почти у всех были красные, распухшие и гноившиеся глаза.
Одна кучка французов стояла близко у дороги, и два солдата – лицо одного из них было покрыто болячками – разрывали руками кусок сырого мяса. Что то было страшное и животное в том беглом взгляде, который они бросили на проезжавших, и в том злобном выражении, с которым солдат с болячками, взглянув на Кутузова, тотчас же отвернулся и продолжал свое дело.
Кутузов долго внимательно поглядел на этих двух солдат; еще более сморщившись, он прищурил глаза и раздумчиво покачал головой. В другом месте он заметил русского солдата, который, смеясь и трепля по плечу француза, что то ласково говорил ему. Кутузов опять с тем же выражением покачал головой.
– Что ты говоришь? Что? – спросил он у генерала, продолжавшего докладывать и обращавшего внимание главнокомандующего на французские взятые знамена, стоявшие перед фронтом Преображенского полка.
– А, знамена! – сказал Кутузов, видимо с трудом отрываясь от предмета, занимавшего его мысли. Он рассеянно оглянулся. Тысячи глаз со всех сторон, ожидая его сло ва, смотрели на него.
Перед Преображенским полком он остановился, тяжело вздохнул и закрыл глаза. Кто то из свиты махнул, чтобы державшие знамена солдаты подошли и поставили их древками знамен вокруг главнокомандующего. Кутузов помолчал несколько секунд и, видимо неохотно, подчиняясь необходимости своего положения, поднял голову и начал говорить. Толпы офицеров окружили его. Он внимательным взглядом обвел кружок офицеров, узнав некоторых из них.
– Благодарю всех! – сказал он, обращаясь к солдатам и опять к офицерам. В тишине, воцарившейся вокруг него, отчетливо слышны были его медленно выговариваемые слова. – Благодарю всех за трудную и верную службу. Победа совершенная, и Россия не забудет вас. Вам слава вовеки! – Он помолчал, оглядываясь.
– Нагни, нагни ему голову то, – сказал он солдату, державшему французского орла и нечаянно опустившему его перед знаменем преображенцев. – Пониже, пониже, так то вот. Ура! ребята, – быстрым движением подбородка обратись к солдатам, проговорил он.
– Ура ра ра! – заревели тысячи голосов. Пока кричали солдаты, Кутузов, согнувшись на седле, склонил голову, и глаз его засветился кротким, как будто насмешливым, блеском.
– Вот что, братцы, – сказал он, когда замолкли голоса…
И вдруг голос и выражение лица его изменились: перестал говорить главнокомандующий, а заговорил простой, старый человек, очевидно что то самое нужное желавший сообщить теперь своим товарищам.
В толпе офицеров и в рядах солдат произошло движение, чтобы яснее слышать то, что он скажет теперь.
– А вот что, братцы. Я знаю, трудно вам, да что же делать! Потерпите; недолго осталось. Выпроводим гостей, отдохнем тогда. За службу вашу вас царь не забудет. Вам трудно, да все же вы дома; а они – видите, до чего они дошли, – сказал он, указывая на пленных. – Хуже нищих последних. Пока они были сильны, мы себя не жалели, а теперь их и пожалеть можно. Тоже и они люди. Так, ребята?
Он смотрел вокруг себя, и в упорных, почтительно недоумевающих, устремленных на него взглядах он читал сочувствие своим словам: лицо его становилось все светлее и светлее от старческой кроткой улыбки, звездами морщившейся в углах губ и глаз. Он помолчал и как бы в недоумении опустил голову.