Алгоритм цепочки Лемпеля – Зива – Маркова

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

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

Обзор

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

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

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

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

Существует 7 типов пакетов: ^{[ 8 ]}

Упакованный код (битовая последовательность)	Имя пакета	Описание пакета
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).

Дистанционное кодирование ^{[ 7 ]}
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. ^{[ 9 ]} из которого можно относительно легко вывести детали алгоритмов LZMA и LZMA2: таким образом, хотя цитирование исходного кода в качестве ссылки не является идеальным, любой программист должен иметь возможность проверить приведенные ниже утверждения, потратив несколько часов работы.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Декодер LZMA настраивается lclppb байт «свойств» и размер словаря. Ценность lclppb Байт $равен lc + lp \times 9 + pb \times 9 \times 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
2	*СООТВЕТСТВОВАТЬ	ШОРТРЕП	ЛИТ	ЛИТ	0	7	8	9
3	ЛИТ	ШОРТРЕП	ЛИТ	ЛИТ	0	7	8	9
4			СООТВЕТСТВОВАТЬ	ЛИТ	1	7	8	9
5			ЛОНГРЭП[*]	ЛИТ	2	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, и параллельная декомпрессия на практике невозможна. ^{[ 6 ]}

Заголовок 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 , ^{[ 10 ]} а формат файла .7z, который может содержать данные LZMA или LZMA2, документирован в файле 7zformat.txt, содержащемся в LZMA SDK. ^{[ 11 ]}

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

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

Сжатие LZMA2, которое является улучшенной версией LZMA. ^{[ 13 ]} теперь является методом сжатия по умолчанию для формата .7z, начиная с версии 9.30 от 26 октября 2012 г. ^{[ 14 ]}

Эталонная с открытым исходным кодом библиотека сжатия LZMA изначально была написана на C++, но была портирована на ANSI C , C# и Java . ^{[ 11 ]} Существуют также сторонние привязки Python для библиотеки C++, а также порты LZMA на Pascal , Go и Ada . ^{[ 15 ]}^{[ 16 ]}^{[ 17 ]}^{[ 18 ]}

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

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

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

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

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

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

ЛЖАМ

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

Ссылки

^ Игорь Павлов неоднократно заявлял на SourceForge , что этот алгоритм — его собственное творение. (19 февраля 2004 г.). «Спецификация ЛЗМА?» . Архивировано из оригинала 09.11.2012 . Проверено 16 июня 2013 г.
^ Перейти обратно: ^а ^б Лассе Коллин (31 мая 2005 г.). «Быстрый тест: Gzip, Bzip2 и LZMA» . Проверено 21 октября 2015 г. - Порт LZMA Unix наконец-то заменен на xz, который обеспечивает лучшее и быстрое сжатие; Отсюда мы знаем, что даже порт LZMA Unix был намного лучше, чем gzip и bzip2.
^ Клаусманн, Тобиас (8 мая 2008 г.). «Gzip, Bzip2 и Lzma сравнили» . Блог Альфа-животного . Архивировано из оригинала 6 января 2013 г. Проверено 16 июня 2013 г.
^ Игорь Павлов (2013). «Формат 7z» . Проверено 16 июня 2013 г.
^ Махони, Мэтт. «Объяснение сжатия данных» . Проверено 13 ноября 2013 г.
^ Перейти обратно: ^а ^б Антонио Диас Диас. «Формат Xz не подходит для долгосрочного архивирования» . Проверено 20 июля 2018 г.
^ Перейти обратно: ^а ^б ^с ^д «Спецификация LZMA.7z в LZMA SDK» . 7-zip.org .
^ Перейти обратно: ^а ^б «Формат потока Lzip» . Руководство по использованию LZIP . Проверено 14 ноября 2019 г.
^ Коллин, Лассе; Павлов Игорь. "lib/xz/xz_dec_lzma2.c" . Проверено 16 июня 2013 г.
^ «Формат файла .xz» . 27 августа 2009 г. Проверено 16 июня 2013 г.
^ Перейти обратно: ^а ^б ^с Игорь Павлов (2013). «LZMA SDK (Комплект разработки программного обеспечения)» . Проверено 16 июня 2013 г.
^ «Просмотр /LZMA SDK/4.23» . СоурсФордж . Проверено 12 февраля 2014 г.
^ «Помощь по настройке Inno» . jrsoftware.org . Проверено 16 июня 2013 г. LZMA2 — это модифицированная версия LZMA, которая обеспечивает лучшую степень сжатия несжимаемых данных (случайные данные расширяются примерно на 0,005 % по сравнению с 1,35 % при исходном LZMA) и дополнительно может сжимать несколько частей больших файлов параллельно, значительно увеличивая скорость сжатия, но с возможным снижением степени сжатия.
^ «ИСТОРИЯ 7-Zip» . 26 октября 2012 г. Проверено 16 июня 2013 г.
^ Баух, Иоахим (07 апреля 2010 г.). «PyLZMA — независимые от платформы привязки Python для библиотеки сжатия LZMA» . Проверено 16 июня 2013 г.
^ Бертлз, Алан (13 июня 2006 г.). «Помощь по программированию: Pascal LZMA SDK» . Проверено 16 июня 2013 г.
^ Виеру, Андрей (28 июня 2012 г.). «пакет compress/lzma для Go 1» . Архивировано из оригинала 21 сентября 2016 г. Проверено 16 июня 2013 г.
^ «Зип-Ада» .
^ Гиллем Джовер. «Принят dpkg 1.17.0 (исходный код amd64 all)» . Контроль качества пакета Debian . Проверено 21 октября 2015 г.
^ Диас, Диас. «Бенчмарки Lzip» . LZIP (нонгну).
^ «Что такое файл Zipx?» . WinZip.com . Проверено 14 марта 2016 г.
^ «ЛЖАМ – Кодек сжатия данных без потерь» . Ричард Гелдрейх. LZHAM — это кодек сжатия данных без потерь, написанный на C/C++, со степенью сжатия, аналогичной LZMA, но со скоростью распаковки в 1,5–8 раз большей.

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

[1] Игорь Павлов неоднократно заявлял на SourceForge , что этот алгоритм — его собственное творение. (19 февраля 2004 г.). «Спецификация ЛЗМА?» . Архивировано из оригинала 09.11.2012 . Проверено 16 июня 2013 г.

[gzip_bzip_lzma_bench-2] Перейти обратно: ^а ^б Лассе Коллин (31 мая 2005 г.). «Быстрый тест: Gzip, Bzip2 и LZMA» . Проверено 21 октября 2015 г. - Порт LZMA Unix наконец-то заменен на xz, который обеспечивает лучшее и быстрое сжатие; Отсюда мы знаем, что даже порт LZMA Unix был намного лучше, чем gzip и bzip2.

[3] Клаусманн, Тобиас (8 мая 2008 г.). «Gzip, Bzip2 и Lzma сравнили» . Блог Альфа-животного . Архивировано из оригинала 6 января 2013 г. Проверено 16 июня 2013 г.

[LZMA_Format-4] Игорь Павлов (2013). «Формат 7z» . Проверено 16 июня 2013 г.

[5] Махони, Мэтт. «Объяснение сжатия данных» . Проверено 13 ноября 2013 г.

[xz-inadequate-6] Перейти обратно: ^а ^б Антонио Диас Диас. «Формат Xz не подходит для долгосрочного архивирования» . Проверено 20 июля 2018 г.

[lzma-sdk-format-7] Перейти обратно: ^а ^б ^с ^д «Спецификация LZMA.7z в LZMA SDK» . 7-zip.org .

[lzip-format-8] Перейти обратно: ^а ^б «Формат потока Lzip» . Руководство по использованию LZIP . Проверено 14 ноября 2019 г.

[9] Коллин, Лассе; Павлов Игорь. "lib/xz/xz_dec_lzma2.c" . Проверено 16 июня 2013 г.

[10] «Формат файла .xz» . 27 августа 2009 г. Проверено 16 июня 2013 г.

[LZMA_SDK-11] Перейти обратно: ^а ^б ^с Игорь Павлов (2013). «LZMA SDK (Комплект разработки программного обеспечения)» . Проверено 16 июня 2013 г.

[12] «Просмотр /LZMA SDK/4.23» . СоурсФордж . Проверено 12 февраля 2014 г.

[13] «Помощь по настройке Inno» . jrsoftware.org . Проверено 16 июня 2013 г. LZMA2 — это модифицированная версия LZMA, которая обеспечивает лучшую степень сжатия несжимаемых данных (случайные данные расширяются примерно на 0,005 % по сравнению с 1,35 % при исходном LZMA) и дополнительно может сжимать несколько частей больших файлов параллельно, значительно увеличивая скорость сжатия, но с возможным снижением степени сжатия.

[14] «ИСТОРИЯ 7-Zip» . 26 октября 2012 г. Проверено 16 июня 2013 г.

[15] Баух, Иоахим (07 апреля 2010 г.). «PyLZMA — независимые от платформы привязки Python для библиотеки сжатия LZMA» . Проверено 16 июня 2013 г.

[16] Бертлз, Алан (13 июня 2006 г.). «Помощь по программированию: Pascal LZMA SDK» . Проверено 16 июня 2013 г.

[17] Виеру, Андрей (28 июня 2012 г.). «пакет compress/lzma для Go 1» . Архивировано из оригинала 21 сентября 2016 г. Проверено 16 июня 2013 г.

[18] «Зип-Ада» .

[dpkg_use_xz-19] Гиллем Джовер. «Принят dpkg 1.17.0 (исходный код amd64 all)» . Контроль качества пакета Debian . Проверено 21 октября 2015 г.

[lzip_bench-20] Диас, Диас. «Бенчмарки Lzip» . LZIP (нонгну).

[zipx-21] «Что такое файл Zipx?» . WinZip.com . Проверено 14 марта 2016 г.

[22] «ЛЖАМ – Кодек сжатия данных без потерь» . Ричард Гелдрейх. LZHAM — это кодек сжатия данных без потерь, написанный на C/C++, со степенью сжатия, аналогичной LZMA, но со скоростью распаковки в 1,5–8 раз большей.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

v т и Форматы архивов
Archiving only	ar cpio shar tar LBR WAD WARC
Compression only	Brotli bzip2 compress gzip Zopfli LZMA LZ4 lzip lzop SQ xz Zstandard
Archiving and compression	7z ACE ARC ARJ B1 Cabinet cfs cpt dar DGCA .dmg .egg kgb LHA lrzip LZX MPQ PEA RAR rzip sit sitx SQX UDA Xar zoo ZIP ZPAQ
Software packaging and distribution	apk App APPX deb HAP ipa JAR WAR Java RAR EAR MSI MSIX Package (macOS) RPM XAP XBAP
Document packaging and distribution	OEB Package Format OEBPS Container Format Open Packaging Conventions PAQ
Comparison List Category