Алгоритм цепей Лемпеля–Зива–Маркова ( LZMA ) — это алгоритм , используемый для сжатия данных без потерь . Он разрабатывался с 1996 или 1998 года Игорем Павловым [ требуется ссылка ] и впервые был использован в формате 7z архиватора 7-Zip . Этот алгоритм использует схему сжатия словаря , несколько похожую на алгоритм LZ77 , опубликованный Авраамом Лемпелем и Якобом Зивом в 1977 году, и отличается высокой степенью сжатия (обычно выше, чем у bzip2 ) [1] [2] и переменным размером словаря сжатия (до 4 ГБ ), [3] при этом сохраняя скорость распаковки, аналогичную другим часто используемым алгоритмам сжатия. [4]
LZMA2 — это простой формат контейнера, который может включать как несжатые данные, так и данные LZMA, возможно, с несколькими различными параметрами кодирования LZMA. LZMA2 поддерживает произвольно масштабируемое многопоточное сжатие и декомпрессию и эффективное сжатие данных, которые частично несжимаемы. [5]
LZMA использует алгоритм сжатия словаря (вариант LZ77 с огромными размерами словаря и специальной поддержкой для многократно используемых расстояний совпадений), чей вывод затем кодируется с помощью кодировщика диапазона , используя сложную модель для прогнозирования вероятности каждого бита. Компрессор словаря находит совпадения, используя сложные структуры данных словаря, и создает поток буквенных символов и ссылок на фразы, который кодируется по одному биту за раз кодировщиком диапазона: возможно множество кодировок, и используется алгоритм динамического программирования для выбора оптимальной при определенных приближениях. [6]
До LZMA большинство моделей кодировщиков были чисто байтовыми (т. е. они кодировали каждый бит, используя только каскад контекстов для представления зависимостей от предыдущих битов из того же байта). Главное новшество LZMA заключается в том, что вместо общей байтовой модели модель LZMA использует контексты, специфичные для битовых полей в каждом представлении литерала или фразы: это почти так же просто, как и общая байтовая модель, но дает гораздо лучшее сжатие, поскольку избегает смешивания несвязанных битов вместе в одном контексте. Кроме того, по сравнению с классическим сжатием словаря (например, используемым в форматах zip и gzip ), размеры словаря могут быть и обычно бывают намного больше, используя преимущество большого объема памяти, доступной в современных системах. [6]
В сжатии LZMA сжатый поток представляет собой поток битов, закодированных с использованием адаптивного двоичного кодера диапазона. Поток делится на пакеты, каждый пакет описывает либо один байт, либо последовательность LZ77 с неявно или явно закодированной длиной и расстоянием. Каждая часть каждого пакета моделируется с независимыми контекстами, поэтому предсказания вероятности для каждого бита коррелируют со значениями этого бита (и связанных битов из того же поля) в предыдущих пакетах того же типа. И lzip [7] , и документация LZMA SDK описывают этот формат потока. [6]
Существует 7 типов пакетов: [7]
LONGREP[*] относится к пакетам LONGREP[0–3], *REP относится как к LONGREP, так и к SHORTREP, а *MATCH относится как к MATCH, так и к *REP.
Пакеты LONGREP[n] удаляют используемое расстояние из списка последних расстояний и вставляют его заново в начало, чтобы избежать бесполезного повторного ввода, в то время как MATCH просто добавляет расстояние в начало, даже если оно уже присутствует в списке, а SHORTREP и LONGREP[0] не изменяют список.
Длина кодируется следующим образом:
Как и в LZ77, длина не ограничена расстоянием, поскольку копирование из словаря определяется так, как если бы копирование выполнялось побайтно, сохраняя расстояние постоянным.
Расстояния логически являются 32-битными, а расстояние 0 указывает на последний добавленный байт в словаре.
Кодирование расстояния начинается с 6-битного «слота расстояния», который определяет, сколько еще битов необходимо. Расстояния декодируются как двоичная конкатенация, от наиболее к наименее значимому, двух бит в зависимости от слота расстояния, некоторые биты кодируются с фиксированной вероятностью 0,5 и некоторые контекстно-кодированные биты, согласно следующей таблице (слоты расстояния 0−3 напрямую кодируют расстояния 0−3).
Полной спецификации сжатого формата на естественном языке, по-видимому, не существует, за исключением той, которая предпринята в следующем тексте.
Приведенное ниже описание основано на компактном декодере XZ Embedded Лассе Коллина, включенном в исходный код ядра Linux [8], из которого можно относительно легко вывести детали алгоритмов LZMA и LZMA2: таким образом, хотя цитирование исходного кода в качестве ссылки не является идеальным вариантом, любой программист должен иметь возможность проверить приведенные ниже утверждения, потратив несколько часов работы.
Данные LZMA на самом низком уровне декодируются по одному биту за раз декодером дальности по направлению декодера LZMA.
Контекстное декодирование диапазона вызывается алгоритмом LZMA, который передает ему ссылку на «контекст», состоящий из беззнаковой 11-битной переменной prob (обычно реализуемой с использованием 16-битного типа данных), представляющей прогнозируемую вероятность того, что бит будет равен 0, которая считывается и обновляется декодером диапазона (и должна быть инициализирована значением , представляющим вероятность 0,5).
Декодирование фиксированного диапазона вероятностей вместо этого предполагает вероятность 0,5, но работает несколько иначе, чем декодирование диапазона на основе контекста.
Состояние декодера диапазона состоит из двух беззнаковых 32-битных переменных: диапазона (представляющего размер диапазона) и кода (представляющего закодированную точку внутри диапазона).
Инициализация декодера диапазона состоит из установки диапазона в значение 2 32 − 1 и кода в 32-битное значение, начиная со второго байта в потоке, интерпретируемом как big-endian; первый байт в потоке полностью игнорируется.
Нормализация происходит следующим образом:
Контекстно-ориентированное декодирование диапазона бита с использованием переменной вероятности выполняется следующим образом:
Декодирование бита в диапазоне фиксированной вероятности происходит следующим образом:
Реализация декодирования с фиксированной вероятностью в ядре Linux rc_direct()в целях производительности не включает условный переход, а вместо этого безусловно вычитает диапазон из кода . Полученный бит знака используется как для определения бита для возврата, так и для генерации маски, которая объединяется с кодом и добавляется к диапазону .
Обратите внимание, что:
Декодер диапазона также предоставляет возможности декодирования битового дерева, обратного битового дерева и фиксированной вероятности целых чисел, которые используются для декодирования целых чисел и обобщают однобитовое декодирование, описанное выше. Для декодирования беззнаковых целых чисел, меньших предела , предоставляется массив из ( предел − 1) 11-битных вероятностных переменных, которые концептуально организованы как внутренние узлы полного двоичного дерева с предельными листьями.
Необратное декодирование битового дерева работает, сохраняя указатель на дерево переменных, которое начинается с корня. Пока указатель не указывает на лист, бит декодируется с использованием переменной, указанной указателем, и указатель перемещается либо к левому, либо к правому потомку в зависимости от того, равен ли бит 0 или 1; когда указатель указывает на лист, возвращается число, связанное с листом.
Таким образом, необратное декодирование битового дерева происходит от наиболее значимого бита к наименее значимому, останавливаясь, когда в допустимом диапазоне возможно только одно значение (это концептуально позволяет иметь размеры диапазонов, не являющиеся степенями двойки, хотя LZMA этого не использует).
Обратное декодирование битового дерева вместо этого декодирует от наименее значимых битов к наиболее значимым битам и, таким образом, поддерживает только диапазоны, которые являются степенями двойки, и всегда декодирует одинаковое количество бит. Это эквивалентно выполнению необратного декодирования битового дерева с пределом степени двойки и реверсированию последних log 2 ( limit ) бит результата.
В функции rc_bittree в ядре Linux целые числа фактически возвращаются в диапазоне [ limit , 2 × limit ) (с добавлением limit к концептуальному значению), а переменная с индексом 0 в массиве не используется, в то время как переменная с индексом 1 является корнем, а левые и правые индексы дочерних элементов вычисляются как 2 i и 2 i + 1. Функция rc_bittree_reverse вместо этого добавляет целые числа в диапазоне [0, limit ) к переменной, предоставленной вызывающей стороной, где limit неявно представлен своим логарифмом, и имеет свою собственную независимую реализацию из соображений эффективности.
Декодирование целых чисел с фиксированной вероятностью просто выполняет многократное декодирование битов с фиксированной вероятностью, считывая биты от наиболее значимых к наименее значимым.
Декодер LZMA настраивается байтом "свойств" lclppb и размером словаря. Значение байта lclppb равно lc + lp × 9 + pb × 9 × 5 , где:
В потоках, отличных от LZMA2, lc не должен быть больше 8, а lp и pb не должны быть больше 4. В потоках LZMA2 ( lc + lp ) и pb не должны быть больше 4.
В формате файла 7-zip LZMA конфигурация выполняется заголовком, содержащим байт "properties", за которым следует 32-битный little-endian размер словаря в байтах. В LZMA2 байт свойств может быть опционально изменен в начале пакетов LZMA2 LZMA, в то время как размер словаря указывается в заголовке LZMA2, как описано далее.
Формат пакета LZMA уже был описан, и в этом разделе определяется, как LZMA статистически моделирует потоки, закодированные с помощью LZ, или, другими словами, какие переменные вероятности передаются в декодер диапазона для декодирования каждого бита.
Эти вероятностные переменные реализованы как многомерные массивы; перед их введением определяются несколько значений, которые используются в качестве индексов в этих многомерных массивах.
Значение состояния концептуально основано на том , какой из шаблонов в следующей таблице соответствует последним 2–4 типам увиденных пакетов, и реализуется как состояние конечного автомата, обновляемое в соответствии с таблицей переходов, указанной в таблице, каждый раз при выводе пакета.
Начальное состояние равно 0, поэтому пакеты до начала считаются пакетами LIT.
Значения pos_state и literal_pos_state состоят из pb и lp (до 4 из заголовка LZMA или пакета свойств LZMA2) соответственно младших значимых битов позиции словаря (количество байтов, закодированных с момента последнего сброса словаря по модулю размера словаря). Обратите внимание, что размер словаря обычно кратен большой степени числа 2, поэтому эти значения эквивалентно описываются как младшие значимые биты числа несжатых байтов, увиденных с момента последнего сброса словаря.
Значение prev_byte_lc_msbs устанавливается равным lc (до 4, из заголовка LZMA или пакета свойств LZMA2) наиболее значимым битам предыдущего несжатого байта.
Значение is_REP указывает, является ли пакет, включающий длину, LONGREP, а не MATCH.
Значение match_byte — это байт, который был бы декодирован, если бы использовался пакет SHORTREP (другими словами, байт, найденный в словаре на последнем использованном расстоянии); он используется только сразу после пакета *MATCH .
literal_bit_mode — это массив из 8 значений в диапазоне 0–2, по одному для каждой позиции бита в байте, которые равны 1 или 2, если предыдущий пакет был *MATCH и это либо самая значимая позиция бита, либо все более значимые биты в литерале для кодирования/декодирования равны битам в соответствующих позициях в match_byte , в противном случае это 0; выбор между значениями 1 или 2 зависит от значения бита в той же позиции в match_byte .
Набор переменных literal/Literal можно рассматривать как «псевдо-битовое дерево», похожее на битовое дерево, но с 3 переменными вместо 1 в каждом узле, выбираемыми в зависимости от значения literal_bit_mode в битовой позиции следующего бита для декодирования после контекста битового дерева, обозначенного узлом.
Утверждение, встречающееся в некоторых источниках, что литералы после *MATCH кодируются как XOR значения байта с match_byte , неверно; вместо этого они кодируются просто как их значение байта, но с использованием только что описанного псевдобитового дерева и дополнительного контекста, перечисленного в таблице ниже.
Группы вероятностных переменных, используемые в LZMA, следующие:
Контейнер LZMA2 поддерживает несколько запусков сжатых данных LZMA и несжатых данных. Каждый сжатый запуск LZMA может иметь различную конфигурацию и словарь LZMA. Это улучшает сжатие частично или полностью несжимаемых файлов и позволяет выполнять многопоточное сжатие и многопоточное декомпрессирование, разбивая файл на запуски, которые могут быть сжаты или декомпрессированы независимо параллельно. Критика изменений LZMA2 по сравнению с LZMA включает поля заголовков, не охваченные CRC, и невозможность параллельной декомпрессии на практике. [5]
Заголовок LZMA2 состоит из байта, указывающего размер словаря:
Данные LZMA2 состоят из пакетов, начинающихся с контрольного байта, со следующими значениями:
Биты 5–6 для фрагментов LZMA могут быть:
Сброс состояния LZMA приводит к сбросу всего состояния LZMA, за исключением словаря, а именно:
Несжатые фрагменты состоят из:
Фрагменты LZMA состоят из:
Формат . xz , который может содержать данные LZMA2, задокументирован на tukaani.org , [9] в то время как формат файла .7z, который может содержать данные LZMA или LZMA2, задокументирован в файле 7zformat.txt, содержащемся в LZMA SDK. [10]
Реализация LZMA, извлеченная из 7-Zip , доступна как LZMA SDK. Первоначально она была лицензирована как GNU LGPL , так и Common Public License [11] с дополнительным специальным исключением для связанных двоичных файлов, но была помещена Игорем Павловым в общественное достояние 2 декабря 2008 года с выпуском версии 4.62. [10]
Сжатие LZMA2, представляющее собой улучшенную версию LZMA, [12] теперь является методом сжатия по умолчанию для формата .7z, начиная с версии 9.30 от 26 октября 2012 года. [13]
Эталонная библиотека сжатия LZMA с открытым исходным кодом изначально была написана на C++, но была портирована на ANSI C , C# и Java . [10] Существуют также сторонние привязки Python для библиотеки C++, а также порты LZMA на Pascal , Go и Ada . [14] [15] [16] [17]
Реализация 7-Zip использует несколько вариантов хеш-цепочек , двоичных деревьев и деревьев Патрисии в качестве основы для своего алгоритма поиска по словарю.
В дополнение к LZMA, SDK и 7-Zip также реализуют несколько фильтров предварительной обработки , предназначенных для улучшения сжатия, начиная от простого дельта-кодирования (для изображений) и BCJ для исполняемого кода. Он также предоставляет некоторые другие алгоритмы сжатия, используемые в 7z.
Код только для декомпрессии для LZMA обычно компилируется примерно до 5 КБ, а объем оперативной памяти, требуемый во время декомпрессии, в основном определяется размером скользящего окна, используемого во время сжатия. Небольшой размер кода и относительно низкие накладные расходы памяти, особенно при меньшей длине словаря, а также бесплатный исходный код делают алгоритм декомпрессии LZMA хорошо подходящим для встраиваемых приложений.
В дополнение к эталонной реализации 7-Zip, следующие поддерживают формат LZMA.
LZHAM (LZ, Хаффман, Арифметика, Марков) — это реализация, подобная LZMA, которая жертвует пропускной способностью сжатия ради очень высоких коэффициентов и более высокой пропускной способности декомпрессии. Она была размещена ее автором в открытом доступе 15 сентября 2020 года. [21]
LZMA2 — это модифицированная версия LZMA, которая обеспечивает лучшую степень сжатия для несжимаемых данных (случайные данные расширяются примерно на 0,005% по сравнению с 1,35% при использовании оригинальной LZMA) и может дополнительно сжимать несколько частей больших файлов параллельно, что значительно увеличивает скорость сжатия, но может при этом снижать степень сжатия.
LZHAM – это кодек сжатия данных без потерь, написанный на C/C++, со степенью сжатия, аналогичной LZMA, но с в 1,5–8 раз более высокой скоростью распаковки.
