Алгоритм цепи Лемпеля-Зив-Маркова ( LZMA ) представляет собой алгоритм , используемый для выполнения сжатия без потерь данных . Он разрабатывался с 1996 или 1998 года Игорем Павловым [1] и впервые был использован в формате 7z архиватора 7-Zip . В этом алгоритме используется схема сжатия словаря , отчасти аналогичная алгоритму LZ77 , опубликованному Абрахамом Лемпелем и Якобом Зивом в 1977 году, и отличается высокой степенью сжатия (обычно выше, чем у bzip2 ) [2] [3]и переменный размер словаря сжатия (до 4 ГБ ), [4] при сохранении скорости распаковки, аналогичной другим широко используемым алгоритмам сжатия. [5]
LZMA2 - это простой контейнерный формат, который может включать как несжатые данные, так и данные LZMA, возможно, с несколькими различными параметрами кодирования LZMA. LZMA2 поддерживает произвольно масштабируемое многопоточное сжатие и декомпрессию, а также эффективное сжатие частично несжимаемых данных. Однако он считается небезопасным и менее эффективным, чем LZMA. [6]
Обзор
LZMA использует алгоритм сжатия словаря (вариант LZ77 с огромными размерами словаря и специальной поддержкой для многократно используемых расстояний сопоставления), выходные данные которого затем кодируются с помощью кодировщика диапазона , используя сложную модель для прогнозирования вероятности каждого бита. Компрессор словаря находит совпадения, используя сложные структуры данных словаря, и создает поток буквенных символов и ссылок на фразы, которые кодируются по одному биту кодировщиком диапазона: возможно множество кодировок, и алгоритм динамического программирования используется для выбора оптимальный при определенных приближениях. [7]
До LZMA большинство моделей кодировщиков были чисто байтовыми (т. Е. Они кодировали каждый бит, используя только каскад контекстов для представления зависимостей от предыдущих битов того же байта). Основное нововведение LZMA заключается в том, что вместо общей модели на основе байтов модель LZMA использует контексты, специфичные для битовых полей в каждом представлении литерала или фразы: это почти так же просто, как универсальная модель на основе байтов, но дает гораздо лучшие результаты. сжатие, потому что это позволяет избежать смешивания несвязанных битов вместе в одном контексте. Кроме того, по сравнению с классическим сжатием словаря (например, используемым в форматах zip и gzip ) размеры словаря могут быть и обычно намного больше, что позволяет использовать большой объем памяти, доступный в современных системах. [7]
Обзор сжатого формата
При сжатии LZMA сжатый поток представляет собой поток битов, закодированных с использованием адаптивного кодера двоичного диапазона. Поток делится на пакеты, каждый из которых описывает либо один байт, либо последовательность LZ77 с неявно или явно закодированными длиной и расстоянием. Каждая часть каждого пакета моделируется с помощью независимых контекстов, поэтому предсказания вероятности для каждого бита коррелируются со значениями этого бита (и связанных битов из того же поля) в предыдущих пакетах того же типа. И lzip [8], и документация LZMA SDK описывают этот формат потока. [7]
Всего существует 7 типов пакетов: [8]
Упакованный код (битовая последовательность) | Имя пакета | Описание пакета |
---|---|---|
0 + byteCode | LIT | Один байт, закодированный с помощью адаптивного двоичного кодировщика диапазона. |
1 + 0 + длина + расстояние | МАТЧ | Типичная последовательность LZ77, описывающая длину и расстояние последовательности. |
1 + 1 + 0 + 0 | КРАТКИЙ ОТЧЕТ | Однобайтовая последовательность LZ77. Расстояние равно последнему использованному расстоянию LZ77. |
1 + 1 + 0 + 1 + лен | LONGREP [0] | Последовательность LZ77. Расстояние равно последнему использованному расстоянию LZ77. |
1 + 1 + 1 + 0 + лен | LONGREP [1] | Последовательность LZ77. Расстояние равно второму последнему использованному расстоянию LZ77. |
1 + 1 + 1 + 1 + 0 + лен | LONGREP [2] | Последовательность LZ77. Расстояние равно третьему последнему использованному расстоянию LZ77. |
1 + 1 + 1 + 1 + 1 + лен | LONGREP [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 от Лассе Коллина, включенном в исходный код ядра Linux [9], из которого относительно легко можно вывести детали алгоритмов LZMA и LZMA2: таким образом, цитирование исходного кода в качестве ссылки не является идеальным, любой программист должен иметь возможность проверить приведенные ниже претензии за несколько часов работы.
Кодирование битов по диапазону
Данные LZMA на самом низком уровне декодируются по одному биту декодером диапазона в направлении декодера LZMA.
Декодирования диапазона контекста на основе вызываются с помощью алгоритма LZMA передавая ему ссылку на «контекст», который состоит из беззнаковой 11-битной переменной Prob (обычно реализуется с использованием типа данных 16-битным) , представляющого прогнозируемой вероятностью битовых существ 0, который считывается и обновляется декодером диапазона (и должен быть инициализирован до 2 ^ 10, что соответствует вероятности 0,5).
Декодирование с фиксированным диапазоном вероятности вместо этого предполагает вероятность 0,5, но работает несколько иначе, чем декодирование диапазона на основе контекста.
Состояние декодера диапазона состоит из двух 32-битных переменных без знака, диапазона (представляющего размер диапазона) и кода (представляющего закодированную точку в диапазоне).
Инициализация декодера диапазона состоит из установки диапазона 2 32 - 1 и кода 32-битного значения, начиная со второго байта в потоке, интерпретируемого как обратный порядок байтов; первый байт в потоке полностью игнорируется.
Нормализация происходит так:
- Сдвинуть диапазон и код влево на 8 бит
- Прочитать байт из сжатого потока
- Установите младшие 8 бит кода в значение прочитанного байта
Контекст основы диапазона декодирование бита с использованием проб выручки переменной вероятности следующим образом:
- Если диапазон меньше 2 ^ 24, выполните нормализацию
- Установить привязку к полу ( диапазон / 2 ^ 11) * проблема
- Если код меньше ограничения :
- Установить диапазон для привязки
- Задайте для проверки значение prob + floor ((2 ^ 11 - prob ) / 2 ^ 5)
- Возвратный бит 0
- В противном случае (если код больше или равен границе ):
- Установить диапазон на диапазон - граница
- Установить код в код - связан
- Установить пробу на пробу - этаж ( проба / 2 ^ 5)
- Бит возврата 1
Декодирование бита с фиксированным диапазоном вероятности происходит следующим образом:
- Если диапазон меньше 2 ^ 24, выполните нормализацию
- Установить диапазон на пол ( диапазон / 2)
- Если код меньше диапазона :
- Возвратный бит 0
- В противном случае (если код больше или равен диапазону ):
- Установить код на код - диапазон
- Бит возврата 1
Реализация декодирования с фиксированной вероятностью в rc_direct в ядре Linux по соображениям производительности не включает условную ветвь, а вместо этого безоговорочно вычитает диапазон из кода и использует полученный знаковый бит как для принятия решения о возврате бита, так и для генерации маска, которая сочетается с кодом и добавляется к диапазону .
Обратите внимание, что:
- Деление на 2 ^ 11 при вычислении границы и минимальной операции выполняется до умножения, а не после (очевидно, чтобы избежать необходимости быстрой аппаратной поддержки 32-битного умножения с 64-битным результатом)
- Декодирование с фиксированной вероятностью не строго эквивалентно декодированию диапазона на основе контекста с любым значением вероятности из-за того, что декодирование диапазона на основе контекста отбрасывает младшие 11 бит диапазона перед умножением на вероятность, как только что описано, в то время как декодирование с фиксированной вероятностью отбрасывает только последний бит
Кодирование целых чисел по диапазонам
Декодер диапазона также предоставляет средства декодирования битового дерева, обратного битового дерева и целочисленного с фиксированной вероятностью, которые используются для декодирования целых чисел и обобщения однобитового декодирования, описанного выше. Для декодирования беззнаковых целых чисел меньше limit предоставляется массив ( limit - 1) 11-битных вероятностных переменных, которые концептуально организованы как внутренние узлы полного двоичного дерева с предельными листьями.
Необратимое декодирование битового дерева работает, сохраняя указатель на дерево переменных, которое начинается с корня. Пока указатель не указывает на лист, бит декодируется с использованием переменной, указанной указателем, и указатель перемещается либо к левому, либо к правому дочернему элементу в зависимости от того, равен ли бит 0 или 1; когда указатель указывает на лист, возвращается число, связанное с листом.
Таким образом, необратимое декодирование битового дерева происходит от наиболее значимого к наименее значимому биту, останавливаясь, когда возможно только одно значение в допустимом диапазоне (это концептуально позволяет иметь размеры диапазона, которые не являются степенями двойки, даже если LZMA не делает использование этого).
Обратное декодирование битового дерева вместо этого декодирует от наименее значимого бита к наиболее значимому и, таким образом, поддерживает только диапазоны, которые являются степенями двойки, и всегда декодирует одинаковое количество битов. Это эквивалентно выполнению не обратного декодирования битового дерева с мощностью, равной двум пределам , и обращению последних log2 ( предельных ) битов результата.
В функции rc_bittree в ядре Linux целые числа фактически возвращаются в диапазоне [ limit , 2 * limit ) (с лимитом, добавленным к концептуальному значению), а переменная с индексом 0 в массиве не используется, а переменная с индексом 1 является корнем, а индексы левого и правого дочерних элементов вычисляются как 2 i и 2 i + 1. Функция rc_bittree_reverse вместо этого добавляет целые числа из диапазона [0, limit ) к переменной, предоставленной вызывающей стороной, где limit неявно представлен как логарифм и имеет собственную независимую реализацию по соображениям эффективности.
Целочисленное декодирование с фиксированной вероятностью просто выполняет многократное декодирование битов с фиксированной вероятностью, считывая биты от наиболее значимых к наименее значимым.
Конфигурация LZMA
Декодер 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, в то время как размер словаря указывается в заголовке LZMA2, как описано ниже.
Контексты кодирования LZMA
Формат пакета LZMA уже был описан, и в этом разделе указывается, как LZMA статистически моделирует потоки, закодированные с помощью LZ, или, другими словами, какие вероятностные переменные передаются в декодер диапазона для декодирования каждого бита.
Эти вероятностные переменные реализованы в виде многомерных массивов; перед их введением определяется несколько значений, которые используются в качестве индексов в этих многомерных массивах.
Значение состояния концептуально основано на том, какой из шаблонов в следующей таблице соответствует последним 2-4 типам наблюдаемых пакетов, и реализуется как состояние конечного автомата, обновляемое в соответствии с таблицей переходов, перечисленной в таблице, каждый раз, когда пакет выводится.
Начальное состояние - 0, и поэтому пакеты перед началом считаются пакетами LIT.
государственный | предыдущие пакеты | следующее состояние, когда следующий пакет | ||||||
---|---|---|---|---|---|---|---|---|
4-я предыдущая | 3-й предыдущий | 2-я предыдущая | предыдущий | LIT | МАТЧ | LONGREP [*] | КРАТКИЙ ОТЧЕТ | |
0 | LIT | LIT | LIT | 0 | 7 | 8 | 9 | |
1 | МАТЧ | LIT | LIT | 0 | 7 | 8 | 9 | |
2 | LONGREP [*] | LIT | LIT | 0 | 7 | 8 | 9 | |
*МАТЧ | КРАТКИЙ ОТЧЕТ | |||||||
3 | LIT | КРАТКИЙ ОТЧЕТ | LIT | LIT | 0 | 7 | 8 | 9 |
4 | МАТЧ | LIT | 1 | 7 | 8 | 9 | ||
5 | LONGREP [*] | LIT | 2 | 7 | 8 | 9 | ||
*МАТЧ | КРАТКИЙ ОТЧЕТ | |||||||
6 | LIT | КРАТКИЙ ОТЧЕТ | LIT | 3 | 7 | 8 | 9 | |
7 | LIT | МАТЧ | 4 | 10 | 11 | 11 | ||
8 | LIT | LONGREP [*] | 5 | 10 | 11 | 11 | ||
9 | LIT | КРАТКИЙ ОТЧЕТ | 6 | 10 | 11 | 11 | ||
10 | *МАТЧ | МАТЧ | 4 | 10 | 11 | 11 | ||
11 | *МАТЧ | * REP | 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 .
Набор переменных literal / Literal можно рассматривать как «псевдобитовое дерево», подобное битовому дереву, но с 3 переменными вместо 1 в каждом узле, выбираемых в зависимости от значения literal_bit_mode в битовой позиции следующего бита. для декодирования после контекста битового дерева, обозначенного узлом.
Утверждение, обнаруженное в некоторых источниках, что литералы после * MATCH кодируются как XOR значения байта с match_byte , неверно; вместо этого они кодируются просто как их байтовые значения, но с использованием только что описанного псевдобитового дерева и дополнительного контекста, перечисленного в таблице ниже.
В LZMA используются следующие группы переменных вероятности:
Имя XZ | Имя LZMA SDK | Параметризован | Используется, когда | Режим кодирования | Если бит 0, то | Если бит 1, то |
---|---|---|---|---|---|---|
is_match | IsMatch | состояние , pos_state | начало пакета | немного | LIT | *МАТЧ |
is_rep | IsRep | государственный | после битовой последовательности 1 | немного | МАТЧ | * REP |
is_rep0 | IsRepG0 | государственный | после битовой последовательности 11 | немного | КРАТКИЙ ОТЧЕТ / LONGREP [0] | LONGREP [1-3] |
is_rep0_long | IsRep0Long | состояние , pos_state | после битовой последовательности 110 | немного | КРАТКИЙ ОТЧЕТ | LONGREP [0] |
is_rep1 | IsRepG1 | государственный | после битовой последовательности 111 | немного | LONGREP [1] | LONGREP [2/3] |
is_rep2 | IsRepG2 | государственный | после битовой последовательности 1111 | немного | LONGREP [2] | LONGREP [3] |
буквальный | Буквальный | prev_byte_lc_msbs , literal_pos_state , literal_bit_mode [битовая позиция], контекст битового дерева | после битовой последовательности 0 | 256 значений псевдобитового дерева | буквальное значение байта | |
dist_slot | PosSlot | min ( match_length , 5), контекст битового дерева | расстояние: начало | 64 значения битового дерева | расстояние слот | |
dist_special | SpecPos | distance_slot , обратный контекст битового дерева | расстояние: 4–13 дистанционных слотов | (( distance_slot >> 1) - 1) -битное обратное битовое дерево | низкие биты расстояния | |
dist_align | Выровнять | обратный контекст битового дерева | расстояние: 14+ интервалов расстояния после битов фиксированной вероятности | 4-битное обратное битовое дерево | низкие биты расстояния | |
len_dec.choice | LenChoice | is_REP | длина матча: начало | немного | 2–9 длина | 10+ длина |
len_dec.choice2 | LenChoice2 | is_REP | длина совпадения: после битовой последовательности 1 | немного | 10–17 длина | 18+ длина |
len_dec.low | LenLow | is_REP , pos_state , контекст битового дерева | длина совпадения: после битовой последовательности 0 | 8 значений битового дерева | младшие биты длины | |
len_dec.mid | ЛенМид | is_REP , pos_state , контекст битового дерева | длина совпадения: после битовой последовательности 10 | 8 значений битового дерева | средние биты длины | |
len_dec.high | LenHigh | 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 или xz , кроме той, которая была предпринята в следующем тексте.
Приведенное ниже описание основано на кодировщике XZ for Java Лассе Коллина [12], который, по-видимому, является наиболее читаемым среди нескольких перезаписей исходного 7-zip с использованием тех же алгоритмов: опять же, цитирование исходного кода в качестве ссылки не В идеале любой программист должен быть в состоянии проверить приведенные ниже утверждения за несколько часов работы.
Датчик диапазона
Кодировщик диапазона не может делать каких-либо интересных выборов и может быть легко сконструирован на основе описания декодера.
Инициализация и завершение полностью не определены; кодировщик xz выводит 0 в качестве первого байта, который игнорируется декомпрессором, и кодирует нижнюю границу диапазона (что имеет значение для конечных байтов).
Кодировщик xz использует беззнаковую 33-битную переменную с именем low (обычно реализуется как 64-битное целое число, инициализируется 0), беззнаковую 32-битную переменную с именем range (инициализируется значением 2 32-1 ), 8-битную переменную без знака. называется cache (инициализируется 0), и беззнаковая переменная cache_size должна быть достаточно большой для хранения несжатого размера (инициализируется 1, обычно реализуется как 64-битное целое число).
В кэш - памяти / CACHE_SIZE переменные используются для правильной обработки несет, и представляют собой число , определенное большим обратным порядком байтов последовательности , начиная с кэш - значения, а затем CACHE_SIZE 0xff байт, который был перенесен из низкого регистра, но не имеет был написан еще, потому что он мог быть увеличен на единицу из-за переноса.
Обратите внимание, что первый выходной байт всегда будет равен 0 из-за того, что кеш и младший бит инициализированы на 0, а также реализация кодировщика; декодер xz игнорирует этот байт.
Нормализация происходит так:
- Если low меньше (2 ^ 32-2 ^ 24):
- Вывести байт, хранящийся в кеше, в сжатый поток
- Выходной cache_size - 1 байт со значением 0xff
- Набор кэш для битов 24-31 с низким
- Установите cache_size равным 0
- Если low больше или равно 2 ^ 32:
- Вывести байт, хранящийся в кеше, плюс один, в сжатый поток
- Выходной cache_size - 1 байт со значением 0
- Набор кэш для битов 24-31 с низким
- Установите cache_size равным 0
- Увеличить cache_size
- Набор низкого до самых низких 24 бит минимума сдвигается влево на 8 битов
- Установить диапазон на диапазон, сдвинутый влево на 8 бит
Контекст основе диапазона кодирования бита с использованием проб выручки переменной вероятности следующим образом:
- Если диапазон меньше 2 ^ 24, выполните нормализацию
- Установить привязку к полу ( диапазон / 2 ^ 11) * проблема
- Если кодируется 0 бит:
- Установить диапазон для привязки
- Задайте для проверки значение prob + floor ((2 ^ 11 - prob ) / 2 ^ 5)
- В противном случае (если кодируется 1 бит):
- Установить диапазон на диапазон - граница
- От низкого к низкому + предел
- Установить пробу на пробу - этаж ( проба / 2 ^ 5)
Кодирование бита в диапазоне фиксированной вероятности происходит следующим образом:
- Если диапазон меньше 2 ^ 24, выполните нормализацию
- Установить диапазон на пол ( диапазон / 2)
- Если кодируется 1 бит:
- Установить от низкого к низкому + диапазон
Прекращение действия происходит следующим образом:
- Выполните нормализацию 5 раз
Кодирование битового дерева выполняется так же, как и декодирование, за исключением того, что битовые значения берутся из входного целого числа для кодирования, а не из результата функций битового декодирования.
Для алгоритмов, которые пытаются вычислить кодирование с наименьшим размером постдиапазонного кодирования, кодировщик также должен предоставить оценку этого.
Структуры данных поиска по словарю
Кодировщик должен иметь возможность быстро находить совпадения в словаре. Поскольку LZMA использует очень большие словари (потенциально порядка гигабайт) для улучшения сжатия, простое сканирование всего словаря приведет к тому, что кодировщик будет слишком медленным, чтобы его можно было практически использовать, поэтому для поддержки быстрого поиска совпадений необходимы сложные структуры данных.
Хеш-цепочки
Самый простой подход, называемый «хеш-цепочками», параметризуется константой N, которая может быть 2, 3 или 4, которая обычно выбирается так, чтобы 2 ^ (8 × N ) было больше или равно размеру словаря.
Он состоит из создания для каждого k, меньшего или равного N , хэш-таблицы, индексированной кортежами по k байтов, где каждый из сегментов содержит последнюю позицию, в которой первые k байтов хэшируются до значения хеш-функции, связанного с этим сегментом хеш-таблицы. .
Цепочка достигается с помощью дополнительного массива, в котором для каждой позиции в словаре хранится последняя просмотренная предыдущая позиция, чьи первые N байтов хешируются с тем же значением, что и первые N байтов рассматриваемой позиции.
Чтобы найти совпадения длины N или выше, поиск начинается с использованием хэш-таблицы размером N и продолжается с использованием массива хеш-цепочек; остановка поиска после прохождения заранее определенного количества узлов цепочки хеширования или когда цепочки хеширования «оборачиваются», указывая, что часть ввода, которая была перезаписана в словаре, была достигнута.
Вместо этого совпадения размером меньше N можно найти, просто просмотрев соответствующую хеш-таблицу, которая либо содержит последнее такое совпадение, если таковое имеется, либо строку, хеширующую то же значение; в последнем случае кодировщик не сможет найти совпадение. Эта проблема смягчается тем фактом, что для удаленных коротких совпадений с использованием нескольких литералов может потребоваться меньше битов, а конфликты хешей в соседних строках относительно маловероятны; использование больших хэш-таблиц или даже таблиц прямого просмотра может уменьшить проблему за счет более высокой частоты промахов кеша и, следовательно, более низкой производительности.
Обратите внимание, что все совпадения должны быть проверены, чтобы убедиться, что фактические байты совпадают в настоящее время в этом конкретном совпадении позиции словаря, поскольку механизм хеширования гарантирует только то, что в какой-то прошлый раз в индекс корзины хэш-таблицы хешировались символы (некоторые реализации могут даже не гарантировать это, потому что они не инициализируют структуры данных).
LZMA использует цепи Маркова , как подразумевается буквой «M» в его названии.
Бинарные деревья
Дерево бинарного подход следует цепной подход хэш, за исключением того, что она логически использует бинарное дерево вместо связанного списка для цепочки.
Двоичное дерево поддерживается таким образом, что оно всегда является одновременно деревом поиска относительно лексикографического упорядочения суффиксов и максимальной кучей для позиции словаря [13] (другими словами, корнем всегда является самая последняя строка, а потомок не могут быть добавлены позже, чем его родительский элемент): предполагая, что все строки лексикографически упорядочены, эти условия однозначно определяют двоичное дерево (это тривиально доказывается индукцией по размеру дерева).
Поскольку строка для поиска и строка для вставки одинаковы, можно выполнять как поиск по словарю, так и вставку (что требует поворота дерева) за один обход дерева.
Патрисия пытается
Некоторые старые кодировщики LZMA также поддерживали структуру данных, основанную на попытках Патрисии , но с тех пор такая поддержка была прекращена, так как она была признана уступающей другим вариантам. [13]
Кодировщик LZMA
Кодеры LZMA могут свободно решать, какое совпадение выводить, или в любом случае игнорировать наличие совпадений и выходных литералов.
Возможность вспомнить 4 последних использованных расстояния означает, что, в принципе, использование сопоставления с расстоянием, которое понадобится снова позже, может быть глобально оптимальным, даже если оно не является локально оптимальным, и в результате этого оптимальное сжатие LZMA вероятно, требует знания всего ввода и может потребовать слишком медленных алгоритмов, чтобы их можно было использовать на практике.
Из-за этого в практических реализациях, как правило, используются неглобальные эвристики.
Кодировщики xz используют значение, называемое nice_len (по умолчанию 64): при обнаружении любого совпадения длины, по крайней мере, nice_len , кодировщик останавливает поиск и выводит его с максимальной длиной совпадения.
Быстрый кодировщик
Быстрый кодировщик XZ [14] (производный от быстрого кодировщика 7-zip) является самым коротким кодировщиком LZMA в исходном дереве xz.
Это работает так:
- Выполнять комбинированный поиск и вставку в структуру данных словаря
- Если любое повторяющееся расстояние соответствует длине не менее nice_len :
- Выведите наиболее часто используемое такое расстояние с помощью пакета REP.
- Если найдено совпадение длиной не менее nice_len :
- Выведите его с пакетом MATCH
- Установите основное совпадение на самое длинное совпадение
- Посмотрите на ближайшее совпадение каждой длины в порядке убывания длины до тех пор, пока нельзя будет произвести замену:
- Замените основное совпадение совпадением, которое на один символ короче, но расстояние которого меньше 1/128 текущего расстояния основного совпадения.
- Установите длину основного совпадения на 1, если текущее основное совпадение имеет длину 2 и расстояние не менее 128.
- Если было обнаружено повторное совпадение, и оно короче не более чем на 1 символ, чем основное совпадение:
- Вывести повторное совпадение с пакетом REP
- Если было обнаружено повторное совпадение, которое не более чем на 2 символа короче основного совпадения, а расстояние основного совпадения составляет не менее 512:
- Вывести повторное совпадение с пакетом REP
- Если было обнаружено повторное совпадение, и оно короче основного совпадения не более чем на 3 символа, а расстояние основного совпадения составляет не менее 32768:
- Вывести повторное совпадение с пакетом REP
- Если размер основного совпадения меньше 2 (или совпадений нет):
- Вывести LIT-пакет
- Выполните поиск по словарю следующего байта
- Если следующий байт короче не более чем на 1 символ, чем основное совпадение, с расстоянием менее 1/128 кратного расстояния основного совпадения, и если длина основного совпадения составляет не менее 3:
- Вывести LIT-пакет
- Если следующий байт имеет совпадение по крайней мере такой же длины, как и основное совпадение, и с меньшим расстоянием, чем основное совпадение:
- Вывести LIT-пакет
- Если следующий байт соответствует как минимум на один символ длиннее, чем основное совпадение, и такое, что 1/128 его расстояния меньше или равно, чем расстояние основного совпадения:
- Вывести LIT-пакет
- Если следующий байт соответствует более чем на один символ длиннее основного совпадения:
- Вывести LIT-пакет
- Если любое повторное совпадение короче основного совпадения не более чем на 1 символ:
- Выведите наиболее часто используемое такое расстояние с помощью пакета REP.
- Вывести основное совпадение с пакетом MATCH
Нормальный кодировщик
Нормальный кодировщик XZ [15] (производный от нормального кодировщика 7-zip) является другим кодировщиком LZMA в исходном дереве xz, который использует более сложный подход, который пытается минимизировать размер сгенерированных пакетов после кодирования диапазона.
В частности, он кодирует части ввода, используя результат алгоритма динамического программирования, где подзадачи находят приблизительно оптимальное кодирование (с минимальным размером пост-кодирования диапазона) подстроки длины L, начиная с байта, который сжимается. .
Размер части ввода, обрабатываемой в алгоритме динамического программирования, определяется как максимум между самым длинным совпадением словаря и самым длинным повторным совпадением, найденным в начальной позиции (которая ограничена максимальной длиной совпадения LZMA, 273); кроме того, если совпадение длиннее, чем nice_len , найдено в любой точке только что определенного диапазона, алгоритм динамического программирования останавливается, выводится решение подзадачи до этой точки, выводится совпадение с размером nice_len и новое динамическое программирование экземпляр проблемы запускается с байта после вывода совпадения.
Возможные решения подзадач постепенно обновляются с помощью кодировок кандидатов, построенных на основе решения для более короткой подстроки длины L ', расширенной всеми возможными «хвостами» или наборов из 1-3 пакетов с определенными ограничениями, которые кодируют вход в позиции L'. . После того, как окончательное решение подзадачи найдено, вычисляется состояние LZMA и наименее используемые расстояния для него, которые затем используются для соответствующего вычисления размеров его расширений после кодирования диапазона.
В конце оптимизации динамического программирования выводится все оптимальное кодирование самой длинной рассматриваемой подстроки, и кодирование продолжается с первого несжатого байта, который еще не закодирован, после обновления состояния LZMA и наименее используемых расстояний.
Каждая подзадача расширяется последовательностью пакетов, которую мы называем «хвостом», которая должна соответствовать одному из следующих шаблонов:
1-й пакет | 2-й пакет | 3-й пакет |
---|---|---|
любой | ||
LIT | LONGREP [0] | |
*МАТЧ | LIT | LONGREP [0] |
Причина для расширения не только отдельными пакетами состоит в том, что подзадачи имеют только длину подстроки в качестве параметра по причинам производительности и алгоритмической сложности, в то время как оптимальный подход динамического программирования также потребует наличия последних использованных расстояний и состояния LZMA в качестве параметра; таким образом, расширение с помощью нескольких пакетов позволяет лучше приблизиться к оптимальному решению и, в частности, лучше использовать пакеты LONGREP [0].
Следующие данные сохраняются для каждой подзадачи (конечно, сохраненные значения относятся к возможному решению с минимальной ценой ), где под «хвостом» мы ссылаемся на пакеты, расширяющие решение меньшей подзадачи, которые непосредственно описаны ниже состав:
XZ для имени члена Java | описание |
---|---|
цена | количество, которое необходимо минимизировать: количество битов пост-кодирования диапазона, необходимых для кодирования строки |
optPrev | несжатый размер подстроки, закодированной всеми пакетами, кроме последнего |
назад | -1, если последним пакетом является LIT, 0-3, если это повторение с использованием последнего использованного числа расстояния 0–3, 4 + расстояние, если это ПОИСКПОЗ (это всегда 0, если prev1IsLiteral истинно, поскольку последний пакет может только LONGREP [0] в этом случае) |
prev1IsLiteral | истина, если "хвост" содержит более одного пакета (в этом случае один перед последним является LIT) |
hasPrev2 | истина, если "хвост" содержит 3 пакета (допустимо, только если prev1IsLiteral истинно) |
optPrev2 | несжатый размер подстроки, закодированной всеми пакетами, кроме "хвоста" (допустимо, только если prev1IsLiteral и hasPrev2 истинны) |
назад | -1, если первый пакет в "хвосте" - LIT, 0-3, если это повторение с использованием последнего использованного числа расстояния 0–3, 4 + расстояние, если это СООТВЕТСТВИЕ (действительно только если prev1IsLiteral и hasPrev2 истинны) |
представители [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 , [16] с дополнительным особым исключением для связанных двоичных файлов, но 2 декабря 2008 года Игорь Павлов поместил его в общественное достояние с выпуском версии 4.62. . [11]
Сжатие LZMA2, которое является улучшенной версией LZMA, [17] теперь является методом сжатия по умолчанию для формата .7z, начиная с версии 9.30 26 октября 2012 г. [18]
Эталонная библиотека сжатия LZMA с открытым исходным кодом была первоначально написана на C ++, но была перенесена на ANSI C , C # и Java . [11] Существуют также сторонние привязки Python для библиотеки C ++, а также порты LZMA на Pascal , Go и Ada . [19] [20] [21] [22]
Реализация 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 система содержит код, хг и много дистрибьюторов программного обеспечения , как kernel.org , Debian [23] и Fedora теперь использовать XZ для сжатия своих релизов.
- lzip : еще одна реализация LZMA в основном для Unix-подобных систем, которая напрямую конкурирует с xz. [24] В основном он отличается более простым форматом файлов и, следовательно, более легким исправлением ошибок.
- ZIPX : расширение формата сжатия ZIP , созданное WinZip, начиная с версии 12.1. Он также может использовать различные другие методы сжатия, такие как BZip и PPMd . [25]
ЛЖАМ
LZHAM (LZ, Huffman, Arithmetic, Markov) - это реализация, подобная LZMA, в которой пропускная способность сжатия меняется на очень высокие коэффициенты и более высокую пропускную способность декомпрессии. Он был размещен его автором в общественное достояние 15 сентября 2020 года. [26]
Рекомендации
- ^ Игорь Павлов неоднократно заявлял на SourceForge, что алгоритм - его собственное творение. (2004-02-19). "Спецификация LZMA?" . Архивировано из оригинала на 2012-11-09 . Проверено 16 июня 2013 .
- ^ а б Лассе Коллин (31 мая 2005 г.). «Быстрый тест: Gzip против Bzip2 против LZMA» . Проверено 21 октября 2015 .- LZMA Unix Port был окончательно заменен на xz, который обеспечивает лучшее и быстрое сжатие; отсюда мы знаем, что даже порт LZMA Unix был намного лучше, чем gzip и bzip2.
- ^ Клаусманн, Тобиас (2008-05-08). «Сравнение Gzip, Bzip2 и Lzma» . Блог животного Альфа . Архивировано из оригинала на 2013-01-06 . Проверено 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» . 2009-08-27 . Проверено 16 июня 2013 .
- ^ а б в Игорь Павлов (2013). «LZMA SDK (комплект для разработки программного обеспечения)» . Проверено 16 июня 2013 .
- ^ «XZ на Java» . Архивировано из оригинала на 2016-09-21 . Проверено 16 июня 2013 .
- ^ а б Соломон, Дэвид (19 декабря 2006 г.). Сжатие данных: полный справочник (4-е изд.). Издательство Springer . п. 245. ISBN 978-1846286025.
- ^ Коллин, Лассе; Павлов, Игорь. "LZMAEncoderFast.java" . Архивировано из оригинала на 2012-07-16 . Проверено 16 июня 2013 .
- ^ Коллин, Лассе; Павлов, Игорь. "LZMAEncoderNormal.java" . Архивировано из оригинала на 2012-07-08 . Проверено 16 июня 2013 .
- ^ «Обзор / LZMA SDK / 4.23» . Sourceforge . Проверено 12 февраля 2014 .
- ^ «Справка по установке Inno» . jrsoftware.org . Проверено 16 июня 2013 .
LZMA2 - это модифицированная версия LZMA, которая предлагает лучшую степень сжатия для несжимаемых данных (случайные данные расширяются примерно на 0,005% по сравнению с 1,35% с исходным LZMA) и, при необходимости, может сжимать несколько частей больших файлов параллельно, что значительно увеличивает скорость сжатия, но с возможным уменьшением степени сжатия.
- ^ «ИСТОРИЯ 7-Zip» . 2012-10-26 . Проверено 16 июня 2013 .
- ^ Баух, Иоахим (07.04.2010). «PyLZMA - независимые от платформы привязки Python для библиотеки сжатия LZMA» . Проверено 16 июня 2013 .
- ^ Бертлс, Алан (13.06.2006). «Справка по программированию: Pascal LZMA SDK» . Проверено 16 июня 2013 .
- ^ Виеру, Андрей (28.06.2012). "Пакет compress / lzma для Go 1" . Архивировано из оригинала на 2016-09-21 . Проверено 16 июня 2013 .
- ^ «Зип-Ада» .
- ^ Гиллем Джовер. "Принято dpkg 1.17.0 (исходники amd64 все)" . Пакет Debian QA . Проверено 21 октября 2015 .
- ^ Диас, Диас. "Тесты Lzip" . LZIP (нонгну).
- ^ "Что такое Zipx-файл?" . WinZip.com . Проверено 14 марта 2016 .
- ^ «ЛЖАМ - Кодек сжатия данных без потерь» . Ричард Гельдрайх.
LZHAM - это кодек сжатия данных без потерь, написанный на C / C ++, с коэффициентом сжатия, аналогичным LZMA, но с более высокой скоростью распаковки в 1,5-8 раз.
Внешние ссылки
- Официальная домашняя страница
- Спецификация формата Lzip
- Спецификация формата XZ
- LZMA SDK (комплект для разработки программного обеспечения)
- LZMA Utils = XZ Utils
- Бинарные файлы Windows для XZ Utils
- Сжатие данных, Компрессоры и архиваторы