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

редактировать

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

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

Содержание

  • 1 Обзор сжатого формата
  • 3 Подробности алгоритма декомпрессии
    • 3.1 Кодирование диапазона битов
    • 3.2 Диапазон кодирования целых чисел
    • 3.3 Конфигурация LZMA
    • 3.4 Контексты кодирования LZMA
    • 3.5 Формат LZMA2
    • 3.6 форматы xz и 7z
  • 4 Детали алгоритма сжатия
    • 4.1 Кодировщик диапазона
    • 4.2 Данные поиска по словарю структуры
      • 4.2.1 Хеш-цепочки
      • 4.2.2 Двоичные деревья
      • 4.2.3 Патрисия пытается
    • 4.3 Кодировщик LZMA
      • 4.3.1 Быстрый кодировщик
      • 4.3.2 Нормальный кодировщик
    • 4.4 Кодер LZMA2
    • 4.5 Верхние уровни кодирования
  • 5 Эталонная реализация 7-Zip
  • 6 Другая реализация
  • 7 LZHAM
  • 8 Ссылки
  • 9 Внешние ссылки

Обзор

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

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

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

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

Типов 7 типов:

Упакованный код (битовая последовательность)Имя пакетаОписание пакета
0 + byteCodeLITОдиночный байт, закодированный с использованием адаптивного двоичного кодера диапазона.
1 + 0 + len + distMATCHТипичная последовательность LZ77, описывающая длина и расстояние следовать.
1 + 1 + 0 + 0SHORTREPОднобайтовая последовательность LZ77. Расстояние равно последнему использованному расстоянию LZ77.
1 + 1 + 0 + 1 + lenLONGREP [0]Последовательность LZ77. Расстояние равно последнему использованному расстоянию LZ77.
1 + 1 + 1 + 0 + lenLONGREP [1]Последовательность LZ77. Используется второму последнему использованному расстоянию LZ77.
1 + 1 + 1 + 1 + 0 + lenLONGREP [2]Последовательность LZ77. Равно третьему последнему использованному расстоянию LZ77.
1 + 1 + 1 + 1 + 1 + lenLONGREP [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 битов вероятностиБиты контекстного кодирования
00000
10100
21000
31100
41001
51101
61002
71102
81003
91103
101004
111104
121005
131105
14–62 (четный)10((слот / 2) - 5)4
15–63 (нечетное)11((((slot - 1) / 2) - 5)4

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

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

Приведенное ниже описание основано на компактном встроенном декодере XZ Лассе Коллина, включенный в исходный код ядра 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. Установить привязку к полу (диапазон / 2 ^ 11) * вероятность
  3. Если код меньше границы:
    1. Установить границу диапазона
    2. Установить вероятность на вероятность + пол ((2 ^ 11 - вероятность) / 2 ^ 5)
    3. Вернуть бит 0
  4. В противном случае (если код больше или предел границы):
    1. Установить диапазон на границу диапазона
    2. Установить код на привязку к коду
    3. Установить пробу на пробу - этаж (
    4. Вернуть бит 1

В этом случае происходит декодирование бита в диапазоне фиксированной вероятности способ:

  1. Если диапазон меньше 2 ^ 24, выполнить мализацию
  2. Установить диапазон на пол (диапазон / 2)
  3. Если код меньше:
    1. Вернуть бит 0
  4. В противном случае (если код больше или равный диапазон):
    1. Установить код на code - range
    2. Вернуть бит 1

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

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

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

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

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

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

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

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

Функции rc_bittree в ядре Linux целые числа возвращаются в диапазоне [limit, 2 * limit) (с лимитом, добавленным к концептуальному значению), а переменный индекс 0 в массиве не используется, в то время как индекс индексом 1 является корнем, а индексы левого и правого дочерних элементов вычисляются как 2i и 2i + 1. Функция rc_bittree_reverse вместо этого целого числа в диапазоне [0, 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, как описано ниже, в заголовке LZMA2 может быть изменен размер словаря.

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

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

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

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

Начальное состояние - 0, и таким образом пакеты перед началом считаются пакетами LIT.

состояниепредыдущие пакетыследующее состояние, когда следующим пакетом является
4-й предыдущий3-й предыдущий2- © предыдущийпредыдущийLITMATCHLONGREP [*]SHORTREP
0LITLITLIT0789
1MATCHLITLIT0789
2LONGREP [*]LITLIT0789
* MATCHSHORTREP
3LITSHORTREPLITLIT0789
4MATCHLIT1789
5LONGREP [ *]LIT2789
* MATCHSHORTREP
6LITSHORTREPLIT3789
7LITMATCH4101111
8LITLONGREP [*]5101111
9LITSHORTREP6101111
10* MATCHMATCH4101111
11* MATCH* REP5101111

Значения pos_state и literal_pos_state состоят из соответственно pb и lp (до 4, из заголовка LZMA или L Пакет свойств ZMA2) младшие значащие биты позиции словаря (количество байтов, закодированных с момента последнего сброса словаря по модулю размера словаря). Обратите внимание, что размер словаря обычно кратен большой степени 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начало пакетабитLIT* MATCH
is_repIsRepсостояниепосле бита последовательность 1битMATCH* REP
is_rep0IsRepG0состояниепосле бита последовательность 11битSHORTREP /

LONGREP [0]

LONGREP [1-3]
is_rep0_longIsRep0Longсостояние, pos_stateпосле битовой последовательности 110битSHORTREPLONGREP [0]
is_rep1IsRepG1состояниепосле битовой последовательности 111битLONGREP [1]LONGREP [2/3]
is_rep2IsRepG2состояниепосле битовой последовательности 1111битLONGREP [2]LONGREP [3]
literalLiteralprev_byte_lc_msbs, literal_pos_state, literal_bit_mode [битовая позиция], контекст битового деревапосле битовой последовательности 0256 значений псевдобитового деревабуквальное значение байта
dist_slotPosSlotmin (match_length, 5), контекст битового дереварасстояние: начало64 значения битового дереваинтервал расстояния
dist_specialSpecPosDistance_slot, обратный контекст битового дереваdistance: 4–13 дистанционных слотов((distance_slot>>1) - 1) -битовое обратное битовое деревомладшие биты расстояния
dist_alignAlignобратный контекст битового дереварасстояние: 14+ интервалов расстояния после битов фиксирова нной вероятности4 -битовое обратное битовое деревомладшие биты расстояния
len_dec.choiceLenChoiceis_REPдлина соответствия: началобитдлина 2–9длина 10+
len_dec.choice2LenChoice2is_REPдлина соответствия: после битовой последовательности 1битдлина 10–17длина 18+
len_dec.lowLenLowis_REP, pos_state, контекст битового деревадлина соответствия: после битовой последовательности 08 значений бит- деревомладшие биты длины
len_dec.midLenMidis_REP, pos_state, контекст битового деревадлина соответствия: после битовой последовательности 108 значений битового деревасредние биты длины
len_dec.highLenHighis_REP, контекст битового деревадлина соответствия: после битовой последовательности 1 1256 значений битового деревастаршие биты длины

формат LZMA2

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

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

  • 40 указывает на 4 ГБ - 1 размер словаря
  • Четные значения меньше 40 указывают размер словаря 2 байта
  • Нечетные значения меньше 40 указывают размер словаря 3 × 2 байта
  • Значения больше 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

Несжатые блоки состоят из:

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

Блоки LZMA состоят из:

  • 16-битного прямого байта кодирования младшие 16 битов несжатого размера минус один
  • 16-битное значение с прямым порядком байтов, кодирующее сжатый размер минус один
  • байт свойств / lclppb, если бит 6 в контрольном байте равен set
  • Сжатые данные 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-битную переменную без знака с именем range (инициализируется значением 2-1), 8-битная переменная без знака, называемая cache (инициализированная до 0), и беззнаковая переменная, называемая cache_size, которая должна быть достаточно большой, чтобы хранить несжатый размер (инициализируется 1, обычно реализуется как 64-битное целое число).

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

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

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

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

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

  1. Если диапазон меньше 2 ^ 24, выполнить нормализацию
  2. Установить привязку к полу (диапазон / 2 ^ 11) * вероятность
  3. Если кодируется бит 0:
    1. Установить границу диапазона
    2. Установить вероятность на вероятность + пол ((2 ^ 11 - вероятность) / 2 ^ 5)
  4. В противном случае (если кодируется 1 бит):
    1. Установить диапазон на границу диапазона
    2. Установить нижнюю на нижнюю + границу
    3. Установить вероятность на вероятность - пол (вероятность / 2 ^ 5)

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

  1. Если диапазон меньше 2 ^ 24, выполнить нормализацию
  2. Установить диапазон на пол (диапазон / 2)
  3. Если кодируется 1 бит:
    1. Установить низкий уровень в низкий + диапазон

Завершение происходит следующим образом:

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

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

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

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

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

Хеш-цепочки

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

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

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

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

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

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

LZMA использует цепи Маркова, как подразумевается буквой «M» в его названии.

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

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

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

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

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

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

Кодировщик LZMA

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

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

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

The xz encoders use a value called nice_len (the default is 64): when any match of length at least nice_len is found, the encoder stops the search and outputs it, with the maximum matching length.

Fast encoder

The XZ fast encoder (derived from the 7-zip fast encoder) is the shortest LZMA encoder in the xz source tree.

It works like this:

  1. Perform combined search and insertion in the dictionary data structure
  2. If any repeated distance matches with length at least nice_len:
    • Output the most frequently used such distance with a REP packet
  3. If a match was found of length at least nice_len:
    • Output it with a MATCH packet
  4. Set the main match to the longest match
  5. Look at the nearest match of every length in decreasing length order, and until no replacement can be made:
    • Replace the main match with a match which is one character shorter, but whose distance is less than 1/128 the current main match distance
  6. Set the main match length to 1 if the current main match is of length 2 and distance at least 128
  7. If a repeated match was found, and it is shorter by at most 1 character than the main match:
    • Output the repeated match with a REP packet
  8. If a repeated match was found, and it is shorter by at most 2 characters than the main match, and the main match distance is at least 512:
    • Output the repeated match with a Пакет 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-й пакет
любой
LITLONGREP [0]
* MATCHLITLONGREP [0]

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

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

XZ для имени члена Javaописание
ценаколичество, которое необходимо минимизировать: количество битов пост-кодирования диапазона, необходимого для кодирования строки
optPrevнесжатый размер подстроки, закодированной всеми пакетами, кроме последнего
backPrev-1, если последний пакет LIT, 0-3, если это повторение с использованием последнего использованного номера расстояния 0–3, 4 + расстояние, если это ПОИСКПОЗ (это всегда 0, если prev1IsLiteral истинно, поскольку последний пакет может быть только LONGREP [0] в этом случае)
prev1IsLiteralистина, если "хвост" содержит более одного пакета (в этом случае пакета перед последним является LIT)
hasPrev2истина, если "хвост" содержит 3 пакета (только допустимо, если prev1IsLiteral истинно)
optPrev2несжатый размер подстроки, закодированной всеми пакетами, кроме «хвоста» (допустимо, только если prev1IsLiteral и hasPrev2 истинны)
backPrev2-1, если первый пакет в "хвосте" - LIT, 0-3, если это повторение с использованием последнего использованного номера расстояния 0–3, 4 + расстояние, если это СООТВЕТСТВИЕ (действительно только если 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

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

Ссылки

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

Последняя правка сделана 2021-05-26 06:04:15
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте