Lempel–Ziv–Markov chain algorithm

«ЛЗМА» перенаправляется сюда. Чтобы узнать об аэропорте с кодом ИКАО «LZMA», см. Аэропорт Мартин (Словакия) .

Алгоритм цепочки Лемпеля-Зива-Маркова ( LZMA ) — это алгоритм, используемый для сжатия данных без потерь . Он находится в разработке с 1996 или 1998 года Игорем Павловым. и впервые был использован в 7z формате архиватора 7-Zip . Этот алгоритм использует схему словарного сжатия , несколько похожую на алгоритм LZ77 , опубликованный Авраамом Лемпелем и Джейкобом Зивом в 1977 году, и имеет высокую степень сжатия (обычно выше, чем bzip2 ). и переменный размер словаря сжатия (до 4 ГБ ), сохраняя при этом скорость декомпрессии, аналогичную другим широко используемым алгоритмам сжатия.

LZMA2 — это простой формат контейнера, который может включать как несжатые данные, так и данные LZMA, возможно, с несколькими различными параметрами кодирования LZMA. LZMA2 поддерживает произвольно масштабируемое многопоточное сжатие и распаковку, а также эффективное сжатие частично несжимаемых данных.

Обзор

LZMA использует алгоритм сжатия словаря (вариант LZ77 с огромными размерами словаря и специальной поддержкой многократно используемых расстояний соответствия), выходные данные которого затем кодируются с помощью кодировщика диапазона , используя сложную модель для прогнозирования вероятности каждого бита. Компрессор словаря находит совпадения, используя сложные структуры словарных данных, и создает поток литеральных символов и ссылок на фразы, который кодируется побитно кодировщиком диапазона: возможно множество кодировок, а динамического программирования для выбора используется алгоритм . оптимальный при определенных приближениях.

До LZMA большинство моделей кодировщиков были чисто байтовыми (т.е. они кодировали каждый бит, используя только каскад контекстов для представления зависимостей от предыдущих битов того же байта). Основное нововведение LZMA заключается в том, что вместо общей байтовой модели модель LZMA использует контексты, специфичные для битовых полей в каждом представлении литерала или фразы: это почти так же просто, как общая байтовая модель, но дает гораздо лучшие результаты. сжатие, поскольку оно позволяет избежать смешивания несвязанных битов в одном контексте. Более того, по сравнению с классическим сжатием словаря (например, используемым в форматах zip и gzip ), размеры словаря могут быть и обычно намного больше, что обусловлено большим объемом памяти, доступной в современных системах.

Обзор сжатого формата

При сжатии LZMA сжатый поток представляет собой поток битов, закодированный с помощью адаптивного кодера двоичного диапазона. Поток делится на пакеты, каждый пакет описывает либо один байт, либо последовательность LZ77 с длиной и расстоянием, закодированными неявно или явно. Каждая часть каждого пакета моделируется с использованием независимых контекстов, поэтому прогнозы вероятности для каждого бита коррелируют со значениями этого бита (и связанных битов из того же поля) в предыдущих пакетах того же типа. Оба файла и документация LZMA SDK описывает этот формат потока.

Существует 7 типов пакетов:

Упакованный код (битовая последовательность)	Имя пакета	Описание пакета
0 + байт-код	ЛИТ	Один байт, закодированный с помощью адаптивного кодера двоичного диапазона.
1+0 + только + расстояние	СООТВЕТСТВОВАТЬ	Типичная последовательность LZ77, описывающая длину и расстояние последовательности.
1+1+0+0	ШОРТРЕП	Однобайтовая последовательность LZ77. Дистанция равна последней использованной дистанции LZ77.
1+1+0+1 + только	ЛОНГРЭП[0]	Последовательность LZ77. Дистанция равна последней использованной дистанции LZ77.
1+1+1+0 + только	ЛОНГРЭП[1]	Последовательность LZ77. Дистанция равна предпоследней использованной дистанции LZ77.
1+1+1+1+0 + только	ЛОНГРЭП[2]	Последовательность LZ77. Дистанция равна третьей последней пройденной дистанции LZ77.
1+1+1+1+1 + только	ЛОНГРЭП[3]	Последовательность LZ77. Дистанция равна четвертой последней пройденной дистанции LZ77.

LONGREP[*] относится к пакетам LONGREP[0–3], *REP относится как к LONGREP, так и к SHORTREP, а *MATCH относится как к MATCH, так и к *REP.

Пакеты LONGREP[n] удаляют использованное расстояние из списка самых последних расстояний и повторно вставляют его в начало, чтобы избежать бесполезного повторного ввода, в то время как MATCH просто добавляет расстояние в начало, даже если оно уже присутствует в списке, а SHORTREP и LONGREP [0] не изменять список.

Длина кодируется следующим образом:

Код длины (битовая последовательность)	Описание
0+ 3 бита	Длина, закодированная с использованием 3 битов, дает диапазон длин от 2 до 9.
1+0+ 3 бита	Длина, закодированная с использованием 3 битов, дает диапазон длин от 10 до 17.
1+1+ 8 бит	Длина, закодированная с использованием 8 бит, дает диапазон длин от 18 до 273.

Как и в LZ77, длина не ограничивается расстоянием, поскольку копирование из словаря определяется так, как если бы копирование выполнялось побайтно, сохраняя расстояние постоянным.

Расстояния логически 32-битные, а расстояние 0 указывает на самый последний добавленный байт в словаре.

Кодирование расстояния начинается с 6-битного «слота расстояния», который определяет, сколько дополнительных бит необходимо.Расстояния декодируются как двоичная конкатенация двух битов, от старшего к наименее значимому, в зависимости от интервала расстояния, некоторых битов, кодируемых с фиксированной вероятностью 0,5, и некоторых битов, закодированных по контексту, в соответствии со следующей таблицей (слоты расстояния 0–3 непосредственно кодируют расстояния 0−3).

Дистанционное кодирование

6-битный интервал расстояния	Старшие 2 бита	Фиксированные биты вероятности 0,5	Биты, закодированные в контексте
0	00	0	0
1	01	0	0
2	10	0	0
3	11	0	0
4	10	0	1
5	11	0	1
6	10	0	2
7	11	0	2
8	10	0	3
9	11	0	3
10	10	0	4
11	11	0	4
12	10	0	5
13	11	0	5
14–62 (четный)	10	((слот / 2) − 5)	4
15–63 (нечетное)	11	(((слот − 1) / 2) − 5)	4

Подробности алгоритма декомпрессии

Полной спецификации сжатого формата на естественном языке, похоже, не существует, кроме той, которая предпринята в следующем тексте.

Приведенное ниже описание основано на компактном декодере XZ Embedded от Лассе Коллина, включенном в исходный код ядра Linux. из которого можно относительно легко вывести детали алгоритмов LZMA и LZMA2: таким образом, хотя цитирование исходного кода в качестве ссылки не является идеальным, любой программист должен иметь возможность проверить приведенные ниже утверждения, потратив несколько часов работы.

Диапазонное кодирование битов

Данные LZMA на самом низком уровне декодируются по одному биту декодером диапазона по указанию декодера LZMA.

Декодирование диапазона на основе контекста вызывается алгоритмом LZMA, передающим ему ссылку на «контекст», который состоит из 11-битной переменной без знака ( обычно реализуемой с использованием 16-битного типа данных), представляющей прогнозируемую вероятность того, что бит будет 0, который считывается и обновляется декодером диапазона (и должен быть инициализирован как ⁠ $2^{10}$⁠ , что соответствует вероятности 0,5).

Вместо этого декодирование диапазона с фиксированной вероятностью предполагает вероятность 0,5, но работает немного иначе, чем декодирование диапазона на основе контекста.

Состояние декодера диапазона состоит из двух беззнаковых 32-битных переменных: диапазона (представляющего размер диапазона) и кода (представляющего закодированную точку внутри диапазона).

Инициализация декодера диапазона состоит из установки диапазона на 2. ³² − 1 и код 32-битного значения, начиная со второго байта в потоке, интерпретируемом как обратный порядок байтов; первый байт в потоке полностью игнорируется.

Нормализация происходит следующим образом:

1. Сдвиг диапазона и кода влево на 8 бит.
2. Прочитать байт из сжатого потока
3. Установите младшие 8 бит кода в прочитанное значение байта.

Декодирование бита на основе контекста с использованием переменной вероятности вероятности происходит следующим образом:

1. Если диапазон меньше ⁠ $2^{24}$⁠ , выполнить нормализацию
2. Установить привязанный к ⁠ $\lfloor range/2^{11}\rfloor \times prob$⁠
3. Если код меньше связанного :
   1. Установить диапазон для ограничения
   2. Установить проблему на проблему + ⁠ $\lfloor 2^{11}-prob\rfloor /2^{5}$⁠
   3. Вернуть бит 0
4. В противном случае (если код больше или равен границе ) :
   1. Установить диапазон в диапазон — привязанный
   2. Установить код в код — связанный
   3. Установите пробник на ⁠ $prob-\lfloor prob/2^{5}\rfloor$⁠
   4. Вернуть бит 1

Декодирование бита в диапазоне фиксированной вероятности происходит следующим образом:

1. Если диапазон меньше ⁠ $2^{24}$⁠ , выполнить нормализацию
2. Установите диапазон на ⁠ $\lfloor range/2\rfloor$⁠
3. Если код меньше диапазона :
   1. Вернуть бит 0
4. В противном случае (если код больше или равен диапазону ):
   1. Установить код в код — диапазон
   2. Вернуть бит 1

Реализация декодирования с фиксированной вероятностью в ядре Linux в rc_direct(), по соображениям производительности, не включает условный переход, а вместо этого безоговорочно вычитает диапазон из кода . Полученный знаковый бит используется как для определения возвращаемого бита, так и для создания маски, которая объединяется с кодом и добавляется в диапазон .

Обратите внимание, что:

1. Деление на ⁠ $2^{11}$⁠ когда вычисление границ и нижних операций выполняется до умножения, а не после (очевидно, чтобы избежать необходимости быстрой аппаратной поддержки 32-битного умножения с 64-битным результатом)
2. Декодирование с фиксированной вероятностью не является строго эквивалентным декодированию диапазона на основе контекста с любым значением вероятности из-за того, что декодирование диапазона на основе контекста отбрасывает младшие 11 бит диапазона перед умножением на вероятность , как только что описано, в то время как декодирование с фиксированной вероятностью отбрасывает только последний бит

Кодирование диапазона целых чисел

Декодер диапазона также обеспечивает средства декодирования битового дерева, обратного битового дерева и целочисленного декодирования с фиксированной вероятностью, которые используются для декодирования целых чисел и обобщают однобитовое декодирование, описанное выше.Для декодирования целых чисел без знака, меньших предела , предоставляется массив ( предел — 1) 11-битных вероятностных переменных, которые концептуально организованы как внутренние узлы полного двоичного дерева с предельными листьями.

Необратное декодирование битового дерева работает, сохраняя указатель на дерево переменных, которое начинается с корня. Пока указатель не указывает на лист, бит декодируется с использованием переменной, указанной указателем, и указатель перемещается либо к левому, либо к правому дочернему элементу в зависимости от того, равен ли бит 0 или 1; когда указатель указывает на лист, возвращается число, связанное с этим листом.

Таким образом, необратное декодирование битового дерева происходит от наиболее значимого бита к наименее значимому, останавливаясь, когда возможно только одно значение в допустимом диапазоне (это концептуально позволяет иметь размеры диапазона, которые не являются степенями двойки, даже несмотря на то, что LZMA не использует этого).

Вместо этого декодирование обратного битового дерева декодирует от младшего значащего бита к наиболее значимому биту и, таким образом, поддерживает только диапазоны, являющиеся степенями двойки, и всегда декодирует одно и то же количество битов. Это эквивалентно выполнению необратного декодирования битового дерева с пределом степени двойки и обращению последних логарифмических ₂ ( предельных ) битов результата.

В rc_bittree в ядре Linux целые числа фактически возвращаются в диапазоне [ limit , 2 × limit ) (с добавлением предела к концептуальному значению), а переменная с индексом 0 в массиве не используется, а переменная с индексом 1 — корень, а индексы левого и правого дочерних элементов вычисляются как 2 i и 2 i + 1. Вместо этого функция rc_bittree_reverse добавляет целые числа в диапазоне [0, limit ) к переменной, предоставленной вызывающим объектом, где предел неявно представлен своим логарифмом и имеет собственную независимую реализацию по соображениям эффективности.

Декодирование целых чисел с фиксированной вероятностью просто многократно выполняет декодирование битов с фиксированной вероятностью, считывая биты от наиболее значимого к наименее значимому.

Конфигурация ЛЗМА

Декодер LZMA настраивается lclppb байт «свойств» и размер словаря. Ценность lclppb Байт равен lc + lp × 9 + pb × 9 × 5 , где:

• lc — количество старших бит предыдущего байта, которое будет использоваться в качестве контекста для буквального кодирования (значение по умолчанию, используемое LZMA SDK, равно 3).
• lp — количество младших битов позиции словаря, которые нужно включить в literal_pos_state (значение по умолчанию, используемое LZMA SDK, равно 0)
• pb — количество младших битов позиции словаря, которые нужно включить в pos_state (значение по умолчанию, используемое LZMA SDK, равно 2)

В потоках, отличных от LZMA2, lc не должен быть больше 8, а lp и pb не должны быть больше 4.В потоках LZMA2 ( lc + lp ) и pb не должны быть больше 4.

В формате файла LZMA 7-zip конфигурация выполняется с помощью заголовка, содержащего байт «свойств», за которым следует 32-битный размер словаря с прямым порядком байтов в байтах. В LZMA2 байт свойств может быть изменен в начале пакетов LZMA2 LZMA, а размер словаря указывается в заголовке LZMA2, как описано ниже.

Контексты кодирования LZMA

Формат пакета LZMA уже был описан, и в этом разделе указано, как LZMA статистически моделирует потоки, закодированные LZ, или, другими словами, какие переменные вероятности передаются в декодер диапазона для декодирования каждого бита.

Эти вероятностные переменные реализованы как многомерные массивы; перед их введением определяются несколько значений, которые используются в качестве индексов в этих многомерных массивах.

Значение состояния концептуально основано на том , какой из шаблонов в следующей таблице соответствует последним 2–4 замеченным типам пакетов, и реализуется как состояние конечного автомата, обновляемое в соответствии с таблицей переходов, указанной в таблице, каждый раз, когда выводится пакет.

Начальное состояние равно 0, поэтому пакеты до начала считаются пакетами LIT.

состояние	предыдущие пакеты				следующее состояние, когда будет следующий пакет
	4-й предыдущий	3-й предыдущий	2-й предыдущий	предыдущий	ЛИТ	СООТВЕТСТВОВАТЬ	ЛОНГРЭП[*]	ШОРТРЕП
0		ЛИТ	ЛИТ	ЛИТ	0	7	8	9
1		СООТВЕТСТВОВАТЬ	ЛИТ	ЛИТ	0	7	8	9
2		ЛОНГРЭП[*]	ЛИТ	ЛИТ	0	7	8	9
	*СООТВЕТСТВОВАТЬ	ШОРТРЕП
3	ЛИТ	ШОРТРЕП	ЛИТ	ЛИТ	0	7	8	9
4			СООТВЕТСТВОВАТЬ	ЛИТ	1	7	8	9
5			ЛОНГРЭП[*]	ЛИТ	2	7	8	9
		*СООТВЕТСТВОВАТЬ	ШОРТРЕП
6		ЛИТ	ШОРТРЕП	ЛИТ	3	7	8	9
7			ЛИТ	СООТВЕТСТВОВАТЬ	4	10	11	11
8			ЛИТ	ЛОНГРЭП[*]	5	10	11	11
9			ЛИТ	ШОРТРЕП	6	10	11	11
10			*СООТВЕТСТВОВАТЬ	СООТВЕТСТВОВАТЬ	4	10	11	11
11			*СООТВЕТСТВОВАТЬ	*РЕП	5	10	11	11

Значения 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 .

Литеральный/литеральный набор переменных можно рассматривать как «псевдобитовое дерево», похожее на битовое дерево, но с 3 переменными вместо 1 в каждом узле, выбираемыми в зависимости от значения literal_bit_mode в позиции бита следующего бита. для декодирования после контекста битового дерева, обозначенного узлом.

Утверждение, встречающееся в некоторых источниках, о том, что литералы после *MATCH кодируются как XOR значения байта с match_byte , неверно; вместо этого они кодируются просто как их байтовые значения, но с использованием только что описанного псевдобитового дерева и дополнительного контекста, указанного в таблице ниже.

Группы вероятностных переменных, используемые в LZMA:

XZ имя	Имя LZMA SDK	Параметризовано	Используется, когда	Режим кодирования	Если бит 0, то	Если бит 1, то
is_match	IsMatch	состояние , pos_state	начало пакета	кусочек	ЛИТ	*СООТВЕТСТВОВАТЬ
is_rep	Исреп	состояние	после битовой последовательности 1	кусочек	СООТВЕТСТВОВАТЬ	*РЕП
is_rep0	Исрепг0	состояние	после битовой последовательности 11	кусочек	ШОРТРЭП/ ЛОНГРЭП[0]	ЛОНГРЭП[1–3]
is_rep0_long	IsRep0Long	состояние , pos_state	после битовой последовательности 110	кусочек	ШОРТРЕП	ЛОНГРЭП[0]
is_rep1	Исрепг1	состояние	после битовой последовательности 111	кусочек	ЛОНГРЭП[1]	ЛОНГРЭП[2/3]
is_rep2	Исрепг2	состояние	после битовой последовательности 1111	кусочек	ЛОНГРЭП[2]	ЛОНГРЭП[3]
буквальный	Буквальный	prev_byte_lc_msbs , literal_pos_state , literal_bit_mode [позиция бита], контекст битового дерева	после последовательности бит 0	256 значений псевдобитового дерева	буквальное значение байта
dist_slot	ПосСлот	min( match_length , 5), контекст битового дерева	расстояние: начало	Битовое дерево 64 значений	дистанционный слот
dist_special	СпецПос	distance_slot , контекст обратного битового дерева	расстояние: 4–13 слотов расстояния	(( distance_slot >> 1) − 1)-битное обратное битовое дерево	небольшие расстояния
dist_align	Выровнять	контекст обратного битового дерева	расстояние: 14+ слотов расстояния, после битов фиксированной вероятности	4-битное обратное битовое дерево	небольшие расстояния
len_dec.choice	ЛенЧойс	is_REP	длина совпадения: начало	кусочек	длина 2–9	10+ длина
len_dec.choice2	ЛенЧойс2	is_REP	длина совпадения: после битовой последовательности 1	кусочек	длина 10–17	18+ длина
len_dec.low	ЛенЛоу	is_REP , pos_state , контекст битового дерева	длина совпадения: после последовательности бит 0	8-значное битовое дерево	младшие биты длины
len_dec.mid	ЛенМид	is_REP , pos_state , контекст битового дерева	длина совпадения: после битовой последовательности 10	8-значное битовое дерево	средние кусочки длины
len_dec.high	ЛенХай	is_REP , контекст битового дерева	длина совпадения: после битовой последовательности 11	256 значений битового дерева	большие биты длины

Формат LZMA2

Контейнер LZMA2 поддерживает несколько запусков сжатых и несжатых данных LZMA. Каждый сжатый запуск LZMA может иметь другую конфигурацию и словарь LZMA. Это улучшает сжатие частично или полностью несжимаемых файлов и позволяет выполнять многопоточное сжатие и многопоточную распаковку путем разбиения файла на фрагменты, которые можно сжимать или распаковывать независимо друг от друга параллельно.Критика изменений LZMA2 по сравнению с LZMA включает поля заголовка, не охватываемые CRC,и параллельная декомпрессия на практике невозможна.

Заголовок LZMA2 состоит из байта, указывающего размер словаря:

• 40 указывает размер словаря 4 ГБ - 1.
• Даже значения меньше 40 указывают на 2. ^{v /2 + 12} размер словаря в байтах
• Нечетные значения менее 40 указывают на 3×2. ^{( v − 1)/2 + 11} размер словаря в байтах
• Значения выше 40 недействительны.

Данные LZMA2 состоят из пакетов, начинающихся с управляющего байта, со следующими значениями:

• 0 обозначает конец файла
• 1 обозначает сброс словаря, за которым следует несжатый фрагмент.
• 2 обозначает несжатый фрагмент без сброса словаря.
• 3–0x7f — недопустимые значения.
• 0x80–0xff обозначает фрагмент LZMA, где младшие 5 битов используются как биты 16–20 несжатого размера минус один, а биты 5–6 указывают, что следует сбросить.

Биты 5–6 для фрагментов LZMA могут быть:

• 0: ничего не сбрасывается
• 1: сброс состояния
• 2: сброс состояния, сброс свойств с использованием байта свойств.
• 3: сброс состояния, сброс свойств с использованием байта свойств, сброс словаря

Сброс состояния LZMA вызывает сброс всего состояния LZMA, кроме словаря, а именно:

• Кодер диапазона
• Государственная ​ ценность
• Последние дистанции для повторных матчей
• Все вероятности LZMA

Несжатые фрагменты состоят из:

• 16-битное значение с прямым порядком байтов, кодирующее размер данных минус один.
• Данные, которые необходимо дословно скопировать в словарь, и результат

Чанки LZMA состоят из:

• 16-битное значение с прямым порядком байтов, кодирующее младшие 16 бит несжатого размера минус один.
• 16-битное значение с прямым порядком байтов, кодирующее сжатый размер минус один.
• Байт свойств/lclppb, если установлен бит 6 в байте управления.
• Сжатые данные LZMA, начиная с 5 байтов (из которых первый игнорируется), используемых для инициализации кодера диапазона (которые включены в сжатый размер).

форматы xz и 7z

. xz , который может содержать данные LZMA2, документирован на сайте tukaani.org , а формат файла .7z, который может содержать данные LZMA или LZMA2, документирован в файле 7zformat.txt, содержащемся в LZMA SDK.

Подробности алгоритма сжатия

Подобно ситуации с форматом декомпрессии, похоже, не существует полной спецификации методов кодирования на естественном языке в 7-zip или xz , кроме той, которая предпринята в следующем тексте.

Приведенное ниже описание основано на кодировщике XZ для Java Лассе Коллина. который кажется наиболее читаемым среди нескольких переписанных исходных файлов 7-zip с использованием тех же алгоритмов: опять же, хотя цитирование исходного кода в качестве ссылки не является идеальным, любой программист должен иметь возможность проверить приведенные ниже утверждения, потратив несколько часов работы.

Датчик диапазона

Кодер диапазона не может сделать какой-либо интересный выбор и может быть легко создан на основе описания декодера.

Инициализация и завершение не полностью определены; Кодер xz выводит 0 в качестве первого байта, который игнорируется декомпрессором, и кодирует нижнюю границу диапазона (что имеет значение для последних байтов).

Кодировщик xz использует 33-битную переменную без знака, называемую low (обычно реализуется как 64-битное целое число, инициализируемое значением 0), 32-битную переменную без знака, называемую диапазоном (инициализированную значением 2) . ³² − 1 ), 8-битная переменная без знака, называемая кэшем (инициализированная значением 0), и переменная без знака, называемая кэш_размер , которая должна быть достаточно большой для хранения несжатого размера (инициализированная значением 1, обычно реализуется как 64-битное целое число).

Переменные кэш значения / кеш_размер используются для правильной обработки переносов и представляют число, определяемое последовательностью с обратным порядком, начинающейся со кэша , за которой следуют байты кэша_размера 0xff, которые были смещены из нижнего регистра, но не были написано еще, потому что оно может быть увеличено на единицу из-за переноса.

Обратите внимание, что первый выходной байт всегда будет равен 0 из-за того, что кэш и нижний уровень инициализируются значением 0, а реализация кодировщика; декодер xz игнорирует этот байт.

Нормализация происходит следующим образом:

1. Если low меньше ( ⁠ $2^{32}-2^{24}$⁠ ):
   1. Вывести байт, хранящийся в кеше, в сжатый поток
   2. Выходной размер кэша — 1 байт со значением 0xff.
   3. Установите в кэше биты 24–31 низкого уровня.
   4. Установите размер кэша равным 0.
2. Если low больше или равен ⁠ $2^{32}$⁠ :
   1. Вывести байт, хранящийся в кеше, плюс один в сжатый поток.
   2. Выходной размер кэша — 1 байт со значением 0
   3. Установите в кэше биты 24–31 низкого уровня.
   4. Установите размер кэша равным 0.
3. Увеличить размер кэша
4. Установите низкий уровень на младшие 24 бита, сдвинутых влево на 8 бит.
5. Установить диапазон в диапазон, сдвинутый влево на 8 бит.

Кодирование бита на основе контекста с использованием переменной вероятности вероятности происходит следующим образом:

1. Если диапазон меньше ⁠ $2^{24}$⁠ , выполнить нормализацию
2. Установить привязанный к ⁠ $\lfloor range/2^{11}\rfloor \times prob$⁠
3. Если кодируется 0 бит:
   1. Установить диапазон для ограничения
   2. Установите пробник на ⁠ $prob+\lfloor 2^{11}-prob\rfloor /2^{5}$⁠
4. В противном случае (при кодировании 1 бита):
   1. Установить диапазон в диапазон — привязанный
   2. Установить от низкого к низкому + граница
   3. Установите пробник на ⁠ $prob-\lfloor prob/2^{5}\rfloor$⁠

Кодирование бита в диапазоне фиксированной вероятности происходит следующим образом:

1. Если диапазон меньше ⁠ $2^{24}$⁠ , выполнить нормализацию
2. Установите диапазон на ⁠ $\lfloor range/2\rfloor$⁠
3. Если кодируется 1 бит:
   1. Установить от низкого к низкому + диапазон

Прекращение происходит следующим образом:

1. Выполните нормализацию 5 раз

Кодирование битового дерева выполняется аналогично декодированию, за исключением того, что значения битов берутся из входного целого числа, подлежащего кодированию, а не из результата функций декодирования битов.

Для алгоритмов, которые пытаются вычислить кодировку с наименьшим размером после кодирования диапазона, кодер также должен предоставить его оценку.

Структуры данных поиска по словарю

Кодер должен иметь возможность быстро находить совпадения в словаре. Поскольку LZMA использует очень большие словари (потенциально порядка гигабайт) для улучшения сжатия, простое сканирование всего словаря приведет к тому, что кодер будет слишком медленным, чтобы его можно было практически использовать, поэтому для поддержки быстрого поиска совпадений необходимы сложные структуры данных.

Хэш-цепочки

Самый простой подход, называемый «хеш-цепочками», параметризуется константой N, которая может быть равна 2, 3 или 4, которая обычно выбирается так, чтобы 2 ^{8× N} больше или равен размеру словаря.

Он состоит в создании для каждого k меньшего или равного N хеш-таблицы, индексированной кортежами из k байтов, где каждый из сегментов содержит последнюю позицию, где первые k байтов хешируются до хеш-значения, связанного с этим сегментом хеш-таблицы. .

Цепочка достигается с помощью дополнительного массива, в котором для каждой позиции словаря сохраняется последняя увиденная предыдущая позиция, чьи первые N байтов хэшируются с тем же значением, что и первые N байтов рассматриваемой позиции.

Чтобы найти совпадения длины N или выше, поиск начинается с использованием хэш-таблицы размера N и продолжается с использованием массива хэш-цепочки; остановка поиска после прохождения заранее определенного количества узлов хэш-цепочки или когда хэш-цепочки «заворачиваются», указывая на то, что достигнута часть входных данных, которая была перезаписана в словаре.

Вместо этого совпадения размера меньше N находятся путем простого просмотра соответствующей хеш-таблицы, которая либо содержит последнее такое совпадение, если таковое имеется, либо строку, которая хешируется до того же значения; в последнем случае кодер не сможет найти совпадение.Эта проблема смягчается тем фактом, что для удаленных коротких совпадений с использованием нескольких литералов может потребоваться меньше битов, а возникновение конфликтов хеширования в соседних строках относительно маловероятно; использование более крупных хэш-таблиц или даже таблиц прямого поиска может уменьшить проблему за счет более высокого процента промахов в кэше и, следовательно, снижения производительности.

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

Бинарные деревья

Подход двоичного дерева следует подходу хэш-цепочки, за исключением того, что он логически использует двоичное дерево вместо связанного списка для связывания.

Бинарное дерево поддерживается таким образом, что оно всегда является одновременно деревом поиска относительно суффиксного лексикографического порядка и максимальной кучей для позиции словаря. (другими словами, корнем всегда является самая последняя строка, и дочерний элемент не может быть добавлен позже, чем его родительский элемент): если предположить, что все строки лексикографически упорядочены, эти условия явно однозначно определяют двоичное дерево (это тривиально доказывается по индукции от размера дерева).

Поскольку строка для поиска и строка для вставки одинаковы, можно выполнить как поиск по словарю, так и вставку (что требует поворота дерева) за один обход дерева.

Патрисия пытается

Некоторые старые кодеры LZMA также поддерживали структуру данных, основанную на попытках Patricia , но с тех пор от такой поддержки отказались, поскольку она считалась хуже других вариантов.

LZMA-кодер

Кодировщики LZMA могут свободно решать, какое совпадение выводить, или же игнорировать наличие совпадений и выходных литералов.

Возможность вспомнить 4 последних использованных расстояния означает, что в принципе использование совпадения с расстоянием, которое понадобится снова позже, может быть глобально оптимальным, даже если оно не является локально оптимальным, и как следствие этого оптимальное сжатие LZMA. вероятно, требует знания всего ввода и может потребовать слишком медленных алгоритмов, чтобы их можно было использовать на практике.

По этой причине в практических реализациях обычно используются неглобальные эвристики.

Кодировщики xz используют значение под названием nice_len (по умолчанию — 64): когда найдено любое совпадение длиной не ниже nice_len , кодер останавливает поиск и выводит его с максимальной длиной совпадения.

Быстрый кодер

Быстрый энкодер XZ (полученный из быстрого кодировщика 7-zip) — самый короткий кодировщик LZMA в дереве исходного кода xz.

Это работает следующим образом:

1. Выполнить комбинированный поиск и вставку в структуру данных словаря.
2. Если какое-либо повторяющееся расстояние соответствует длине хотя бы nice_len :
   • Выведите наиболее часто используемое такое расстояние с помощью пакета REP.
3. Если найдено совпадение длиной не менее nice_len :
   • Выведите его с помощью пакета MATCH.
4. Установите в качестве основного матча самое длинное совпадение
5. Посмотрите ближайшее совпадение каждой длины в порядке убывания длины до тех пор, пока замена не станет невозможной:
   • Замените основное совпадение совпадением, которое на один символ короче, но расстояние которого меньше 1/128 текущего расстояния основного совпадения.
6. Установите длину основного совпадения равным 1, если текущее основное совпадение имеет длину 2 и расстояние не менее 128.
7. Если обнаружено повторное совпадение, и оно короче основного совпадения не более чем на 1 символ:
   • Выведите повторное совпадение с пакетом REP.
8. Если обнаружено повторное совпадение, и оно короче основного совпадения максимум на 2 символа, а расстояние основного совпадения составляет не менее 512:
   • Выведите повторное совпадение с пакетом REP.
9. Если обнаружено повторное совпадение, и оно короче основного совпадения максимум на 3 символа, а расстояние основного совпадения составляет не менее 32768:
   • Выведите повторное совпадение с пакетом REP.
10. Если размер основного совпадения меньше 2 (или совпадений нет):
    • Вывод LIT-пакета
11. Выполнить поиск по словарю следующего байта
12. Если следующий байт короче основного совпадения не более чем на 1 символ, с расстоянием менее 1/128 расстояния основного совпадения и если длина основного совпадения составляет не менее 3:
    • Вывод LIT-пакета
13. Если следующий байт имеет совпадение по крайней мере такой же длины, как и основное совпадение, и с меньшим расстоянием, чем основное совпадение:
    • Вывод LIT-пакета
14. Если следующий байт имеет совпадение хотя бы на один символ длиннее основного совпадения и такое, что 1/128 его расстояния меньше или равно основному расстоянию совпадения:
    • Вывод LIT-пакета
15. Если следующий байт имеет совпадение более чем на один символ длиннее основного совпадения:
    • Вывод LIT-пакета
16. Если какое-либо повторное совпадение короче основного совпадения не более чем на 1 символ:
    • Выведите наиболее часто используемое такое расстояние с помощью пакета REP.
17. Выведите основное совпадение с помощью пакета MATCH.

Обычный кодер

Обычный кодер XZ (полученный из обычного кодировщика 7-zip) — это другой кодировщик LZMA в исходном дереве xz, который использует более сложный подход, который пытается минимизировать размер сгенерированных пакетов после кодирования диапазона.

В частности, он кодирует части входных данных, используя результат алгоритма динамического программирования, подзадачи которого заключаются в поиске приблизительно оптимальной кодировки (с минимальным размером кодирования после диапазона) подстроки длины L, начиная с сжимаемого байта. .

Размер части входных данных, обрабатываемых в алгоритме динамического программирования, определяется как максимальный размер между самым длинным совпадением словаря и самым длинным повторяющимся совпадением, найденным в начальной позиции (которая ограничена максимальной длиной совпадения LZMA, 273); кроме того, если совпадение длиннее, чем nice_len , найдено в любой точке только что определенного диапазона, алгоритм динамического программирования останавливается, выводится решение для подзадачи до этого момента, nice_len выводится совпадение размера и новое динамическое программирование. Экземпляр проблемы запускается в байте после вывода совпадения.

Решения-кандидаты подзадачи постепенно обновляются с помощью кодировок-кандидатов, построенных на основе решения для более короткой подстроки длины L', расширенной всеми возможными «хвостами», или наборов из 1–3 пакетов с определенными ограничениями, которые кодируют входные данные в позиции L'. . Как только окончательное решение подзадачи найдено, вычисляются состояние LZMA и наименее используемые расстояния для него, а затем используются для соответствующего вычисления размеров его расширений после кодирования диапазона.

В конце оптимизации динамического программирования выводится вся оптимальная кодировка самой длинной рассматриваемой подстроки, и кодирование продолжается с первого несжатого байта, который еще не закодирован, после обновления состояния LZMA и наименее используемых расстояний.

Каждая подзадача расширяется последовательностью пакетов, которую мы называем «хвостом», которая должна соответствовать одному из следующих шаблонов:

1-й пакет	2-й пакет	3-й пакет
любой
ЛИТ	ЛОНГРЭП[0]
*СООТВЕТСТВОВАТЬ	ЛИТ	ЛОНГРЭП[0]

Причина не только расширения с помощью отдельных пакетов заключается в том, что подзадачи имеют только длину подстроки в качестве параметра по причинам производительности и сложности алгоритма, в то время как оптимальный подход к динамическому программированию также потребует наличия последних использованных расстояний и состояния LZMA в качестве параметра; таким образом, расширение несколькими пакетами позволяет лучше приблизиться к оптимальному решению и, в частности, лучше использовать пакеты LONGREP[0].

Следующие данные сохраняются для каждой подзадачи (конечно, сохраненные значения относятся к возможному решению с минимальной ценой ), где под «хвостом» мы ссылаемся на пакеты, расширяющие решение меньшей подзадачи, которые описаны непосредственно в следующем документе. структура:

XZ для имени члена Java	описание
цена	количество, которое необходимо минимизировать: количество битов после кодирования диапазона, необходимых для кодирования строки.
optPrev	несжатый размер подстроки, закодированной всеми пакетами, кроме последнего
назадПредыдущий	-1, если последний пакет LIT, 0–3, если это повторение с использованием последнего использованного номера расстояния 0–3, 4 + расстояние, если это MATCH (это всегда 0, если prev1IsLiteral истинно, поскольку последний пакет может в этом случае будет только LONGREP[0])
предыдущая1IsLiteral	true, если «хвост» содержит более одного пакета (в этом случае пакет перед последним является LIT)
hasPrev2	true, если «хвост» содержит 3 пакета (действительно, только если prev1IsLiteral имеет значение true)
optPrev2	несжатый размер подстроки, закодированной всеми пакетами, кроме «хвоста» (действительно, только если prev1IsLiteral и hasPrev2 верны)
назадПредыдущая2	-1, если первый пакет в «хвосте» LIT, 0–3, если это повторение с использованием последнего использованного номера расстояния, 0–3, 4 + расстояние, если это MATCH (действительно, только если prev1IsLiteral и hasPrev2 верны)
повторения[4]	значения 4-х последних использованных расстояний после пакетов в решении (вычисляются только после определения лучшего решения подзадачи)
состояние	LZMA значение состояния после пакетов в решении (вычисляется только после того, как было определено лучшее решение подзадачи)

Обратите внимание, что в реализации XZ для Java члены optPrev и backPrev повторно используются для хранения прямого односвязного списка пакетов как часть вывода окончательного решения.

Кодер LZMA2

Кодер XZ LZMA2 обрабатывает входные данные частями (размером до 2 МБ в несжатом виде или размером до 64 КБ в сжатом виде, в зависимости от того, что меньше), передавая каждый фрагмент кодеру LZMA, а затем решает, выводить ли фрагмент LZMA2 LZMA, включая закодированные данные. или для вывода несжатого фрагмента LZMA2, в зависимости от того, какой из них короче (LZMA, как и любой другой компрессор, обязательно будет расширять, а не сжимать некоторые виды данных).

Состояние LZMA сбрасывается только в первом блоке, если вызывающая сторона запрашивает изменение свойств и каждый раз при выводе сжатого фрагмента. Свойства LZMA изменяются только в первом блоке или если вызывающая сторона запрашивает изменение свойств.Словарь сбрасывается только в первом блоке.

Верхние уровни кодирования

Перед кодированием LZMA2, в зависимости от предоставленных опций, xz может применить фильтр BCJ, который фильтрует исполняемый код для замены относительных смещений на абсолютные, которые более повторяются, или дельта-фильтр, который заменяет каждый байт разницей между ним и байтом. N байт перед ним.

Параллельное кодирование выполняется путем разделения файла на фрагменты, которые распределяются по потокам, и в конечном итоге каждый кодируется (с использованием, например, блочного кодирования xz) отдельно, что приводит к сбросу словаря между фрагментами в выходном файле.

Эталонная реализация 7-Zip

Реализация LZMA, извлеченная из 7-Zip , доступна как LZMA SDK. Первоначально он имел двойную лицензию: GNU LGPL и Common Public License . с дополнительным специальным исключением для связанных двоичных файлов, но был размещен Игорем Павловым в открытом доступе 2 декабря 2008 г. с выпуском версии 4.62.

Сжатие LZMA2 — улучшенная версия LZMA. теперь является методом сжатия по умолчанию для формата .7z, начиная с версии 9.30 от 26 октября 2012 г.

Эталонная с открытым исходным кодом библиотека сжатия LZMA изначально была написана на C++, но была портирована на ANSI C , C# и Java . Существуют также сторонние привязки Python для библиотеки C++, а также порты LZMA на Pascal , Go и Ada .

Реализация 7-Zip использует несколько вариантов хэш-цепочек , бинарных деревьев и деревьев Патриции в качестве основы для своего алгоритма поиска по словарю.

В дополнение к LZMA, SDK и 7-Zip также реализуют несколько фильтров предварительной обработки , предназначенных для улучшения сжатия, начиная от простого дельта-кодирования (для изображений) и BCJ для исполняемого кода. Он также предоставляет некоторые другие алгоритмы сжатия, используемые в 7z.

Код LZMA, предназначенный только для распаковки, обычно компилируется примерно до 5 КБ, а объем оперативной памяти, необходимый для распаковки, в основном определяется размером скользящего окна, используемого во время сжатия. Небольшой размер кода и относительно низкие затраты памяти, особенно при меньшей длине словаря, а также свободный исходный код делают алгоритм распаковки LZMA хорошо подходящим для встроенных приложений.

Другие реализации

Помимо эталонной реализации 7-Zip, формат LZMA поддерживают следующие форматы.

• xz : реализация потоковой передачи, содержащая инструмент командной строки, подобный gzip , поддерживающий как LZMA, так и LZMA2 в формате файла xz. Он проник во многие программы Unix-подобного мира благодаря своей высокой производительности (по сравнению с bzip2 ) и небольшим размером (по сравнению с gzip ). Ядро Linux , системы dpkg и RPM содержат код xz, а многие распространители программного обеспечения, такие как kernel.org , Debian и Fedora теперь используют xz для сжатия своих выпусков.
• lzip : еще одна реализация LZMA, в основном для Unix-подобных систем, которая напрямую конкурирует с xz. В основном он имеет более простой формат файла и, следовательно, более простое восстановление ошибок.
• ZIPX : расширение формата сжатия ZIP , созданное WinZip, начиная с версии 12.1. Он также может использовать различные другие методы сжатия, такие как BZip и PPMd .

ЛЖАМ

LZHAM (LZ, Huffman, Arithmetic, Markov) — это реализация, подобная LZMA, в которой пропускная способность сжатия обменивается на очень высокие коэффициенты и более высокую пропускную способность распаковки. Он был размещен автором в открытом доступе 15 сентября 2020 года.

Внешние ссылки

• Официальная домашняя страница
• Спецификация формата Lzip
• Спецификация формата XZ
• LZMA SDK (Комплект разработки программного обеспечения)
• Утилиты LZMA = Утилиты XZ
• Бинарные файлы Windows для XZ Utils
• Сжатие данных, компрессоры и архиваторы