Алгоритмы LZ77 и LZ78

2020-04-21T10:04:16Z

178.94.18.98: offset > length !!!!

<tex>\mathrm{LZ77}</tex> и <tex>\mathrm{LZ78}</tex> {{---}} алгоритмы сжатия без потерь, опубликованные Абрахамом Лемпелем<ref>[https://en.wikipedia.org/wiki/Abraham_Lempel Wikipedia {{---}} Abraham Lempel]</ref> и Якобом Зивом<ref>[https://en.wikipedia.org/wiki/Yaakov_Ziv Wikipedia {{---}} Yaakov Ziv]</ref> в <tex>1977</tex> и <tex>1978</tex> годах соответственно. Эти алгоритмы стали основой других алгоритмов семьи <tex>\mathrm{LZ*}</tex>: [[Алгоритм_LZW|LZW]], [[Алгоритм_LZSS|LZSS]], [[Алгоритм_LZMA|LZMA]] и другие. Оба приведенных алгоритма используют словарный подход.

== LZ77 ==

=== Идея алгоритма ===
В кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <tex>\mathrm{LZ77}</tex>, заключается в замене повторений на ссылки на позиции в тексте, где такие подстроки уже встречались.

Информацию о повторении можно закодировать парой чисел {{---}} смещением назад от текущей позиции (<tex>offset</tex>) и длиной совпадающей подстроки (<tex>length</tex>). В таком случае, например, строка <tex>pabcdeqabcde</tex> может быть представлена как <tex>pabcdeq \langle 6, 5 \rangle</tex>. Выражение <tex>\langle 6, 5 \rangle</tex> означает «вернись на <tex>6</tex> символов назад и выведи <tex>5</tex> символов».

Алгоритм <tex>\mathrm{LZ77}</tex> кодирует ссылки блоками из трёх элементов {{---}} <tex>\langle offset, length, next \rangle</tex>. В дополнение к двум уже описанным элементам, новый параметр <tex>next</tex> означает первый символ после найденного совпадающего фрагмента. Если <tex>\mathrm{LZ77}</tex> не удалось найти совпадение, то считается, что <tex>offset = length = 0</tex>.

[[Файл:LZ77-simple-example.jpg]]

Для эффективного поиска повторов в <tex>\mathrm{LZ77}</tex> применяется метод «скользящего окна» {{---}} совпадения ищутся не на всём обработанном префиксе, а в небольшом буфере, состоящем из последних обработанных символов. Обычно длина буфера равна <tex>2</tex>, <tex>4</tex> или <tex>32 \mathrm{KB}</tex>. Таким образом, при больших объемах ввода алгоритм тратит меньше времени за счет того, что просматривается не вся исходная строка. С другой стороны, слишком маленькая длина словаря может привести к тому, что расположенные далеко друг от друга совпадения (на большем расстоянии, чем длина словаря) не будут учтены, и кодирование станет менее оптимальным.

Также нетривиальным может оказаться то, что при кодировании <tex>\mathrm{LZ77}</tex> значение <tex>offset</tex> может быть меньше, чем <tex>length</tex> (например, «вернись на <tex>2</tex> символа назад и выведи <tex>10</tex> символов»). Это означает, что подстрока будет повторяться несколько раз так, чтобы каждый символ совпадал с символом, стоящим на <tex>2</tex> позиции раньше, и всего добавилось <tex>10</tex> символов. Например: <tex>hello\langle 2, 10 \rangle \Leftrightarrow hello\boldsymbol{lololololo}</tex>. Символ всегда можно определить однозначно, даже если он отсутствует в буфере.

=== Реализация ===

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

<code>
'''struct''' Node:
'''int''' offset
'''int''' length
'''char''' next
</code>

Функция <code>findMatching</code> ищет в буфере строку, совпадающую с префиксом суффикса строки <tex>s</tex>, начинающегося с символа <tex>pos</tex> и возвращает искомую пару <tex>\langle offset, length \rangle</tex>.

Функция <code>shiftBuffer</code> сдвигает буфер вперёд на <tex>x</tex> символов.

<code>
// <tex>s</tex> {{---}} исходная строка
// функция возвращает список блоков <tex>\langle offset, length, next \rangle</tex>
'''list<Node>''' encodeLZ77('''string''' s):
'''list<Node>''' ans = []
pos = 0
'''while''' pos < s.length:
offset, length = findMatching(buffer, pos) // ищем слово в словаре
shiftBuffer(length + 1) // перемещаем скользящее окно
pos += length
ans.push({offset, length, s[pos]}) // добавляем в ответ очередной блок
'''return''' ans
</code>

=== Пример ===

Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</tex>. Квадратом обведен буфер.

{| class="wikitable"
! Строка || Совпадение || Закодированная последовательность || Примечание
|-
| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст
|-
| <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, b \rangle</tex> || В буфере нет <tex>b</tex>
|-
| <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> ||
|-
| <tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7, d \rangle</tex> || Здесь выгодно сделать так, что <tex>offset < length</tex>
|-
| <tex>abacaba\fbox{$cabad$}aca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex> её не находит
|-
| <tex>abacabaca\fbox{$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</tex> ставим символ конца строки
|}

Результатом кодирования является список полученных троек: <tex>\left[ \langle 0, 0, a \rangle, \langle 0, 0, b \rangle, \langle 2, 1, c \rangle, \langle 4, 7, d \rangle, \langle 2, 1, c \rangle, \langle 2, 1, \varnothing \rangle \right]</tex>.

=== Декодирование ===
Для декодирования <tex>\mathrm{LZ77}</tex> необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность, затем следующий символ.

Псевдокод этого алгоритма:

<code>
// <tex>encoded</tex> {{---}} список блоков <tex>\langle offset, length, next \rangle</tex>
// функция возвращает декодированную строку
'''string''' decodeLZ77('''list<Node>''' encoded):
ans = ""
'''for''' node '''in''' encoded:
'''if''' node.length > 0: // если необходим повтор
start = ans.length - node.offset // возвращаемся на <tex>offset</tex> символов назад
'''for''' i = 0 .. node.length - 1: // добавляем <tex>length</tex> символов
ans += ans[start + i]
ans += node.next // добавляем следующий символ
'''return''' ans
</code>

=== Модификации ===
Известно много различных модификаций алгоритма <tex>\mathrm{LZ77}</tex>. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно {{---}} пары <tex>\langle offset, length \rangle</tex> (length-distance pair<ref>[https://en.wikipedia.org/wiki/LZ77_and_LZ78#LZ77 Wikipedia {{---}} LZ77]</ref>). [[Алгоритм LZSS]] является улучшением <tex>\mathrm{LZ77}</tex> и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате <tex>\mathrm{PalmDoc}</tex><ref>[https://wiki.mobileread.com/wiki/PalmDOC Описание формата PalmDOC]</ref> на каждую пару смещения и длины выделяется по <tex>2</tex> байта.

Также на <tex>\mathrm{LZ77}</tex> основаны алгоритмы <tex>\mathrm{LZH}</tex><ref>[https://msdn.microsoft.com/en-us/library/hh554076.aspx LZH]</ref> и <tex>\mathrm{DEFLATE}</tex><ref>[https://en.wikipedia.org/wiki/DEFLATE Wikipedia {{---}} DEFLATE]</ref> (последний является широко используемым), которые совмещают <tex>\mathrm{LZ77}</tex> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.

== LZ78 ==

=== Идея алгоритма ===
Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования.

Изначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (<tex>pos</tex>) и символа, который идет за этим префиксом (<tex>next</tex>). При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа.

=== Реализация ===

Будем хранить результат кодирования в такой структуре:

<code>
'''struct''' Node:
'''int''' pos // номер слова в словаре
'''char''' next
</code>

В качестве словаря будем использовать обычный <code>map</code>:

<code>
'''list<Node>''' encodeLZ78('''string''' s):
'''string''' buffer = "" // текущий префикс
'''map<string, int>''' dict = {} // словарь
'''list<Node>''' ans = [] // ответ
'''for''' i = 0 .. s.length - 1:
'''if''' dict.hasKey(buffer + s[i]): // можем ли мы увеличить префикс
buffer += s[i]
'''else''':
ans.push({dict[buffer], s[i]}) // добавляем пару в ответ
dict[buffer + s[i]] = dict.length + 1 // добавляем слово в словарь
buffer = "" // сбрасываем буфер
'''if''' not (buffer is empty): // если буффер не пуст - этот код уже был, нужно его добавить в конец словаря
last_ch = buffer.peek() // берем последний символ буффера, как "новый" символ
buffer.pop() // удаляем последний символ из буфера
ans.push({dict[buffer], last_ch}) // добавляем пару в ответ
'''return''' ans
</code>

=== Пример ===

В этот раз для примера возьмем строку <tex>abacababacabc</tex>.

{| class="wikitable"
! Словарь || Осталось обработать || Найденный префикс || Код || Примечание
|-
| <tex>\varnothing</tex> || <tex>abacababacabc</tex> || {{---}} || <tex>\langle 0, a \rangle</tex> || В словаре ничего не нашлось, вместо номера в словаре указываем <tex>0</tex>
|-
| <tex>a</tex> || <tex>bacababacabc</tex> || {{---}} || <tex>\langle 0, b \rangle</tex> ||
|-
| <tex>a</tex>, <tex>b</tex> || <tex>acababacabc</tex> || <tex>a</tex> || <tex>\langle 1, c \rangle</tex> || Нашелся префикс <tex>a</tex> (слова в словаре нумеруются с <tex>1</tex>), добавляем <tex>ac</tex>
|-
| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex> || <tex>ababacabc</tex> || <tex>a</tex> || <tex>\langle 1, b \rangle</tex> ||
|-
| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex> || <tex>abacabc</tex> || <tex>ab</tex> || <tex>\langle 4, a \rangle</tex> ||
|-
| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex> || <tex>cabc</tex> || {{---}} || <tex>\langle 0, c \rangle </tex> ||
|-
| <tex>a</tex>, <tex>b</tex>, <tex>ac</tex>, <tex>ab</tex>, <tex>aba</tex>, <tex>c</tex> || <tex>abc</tex> || <tex>ab</tex> || <tex>\langle 4, c\rangle </tex> ||
|}

Результатом кодирования является список пар: <tex>\left[ \langle 0, a \rangle, \langle 0, b \rangle, \langle 1, c \rangle, \langle 1, b \rangle, \langle 4, a \rangle, \langle 0, c \rangle, \langle 4, c \rangle \right]</tex>

=== Декодирование ===

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

<code>
'''string''' decodeLZ78('''list<Node>''' encoded):
'''list<string>''' dict = [""] // словарь, слово с номером 0 {{---}} пустая строка
'''string''' ans = "" // ответ
'''for''' node '''in''' encoded:
word = dict[node.pos] + node.next // составляем слово из уже известного из словаря и новой буквы
ans += word // приписываем к ответу
dict.push(word) // добавляем в словарь
'''return''' ans
</code>

=== Модификации ===
Одна из главных проблем <tex>\mathrm{LZ78}</tex> {{---}} размер словаря. Он ничем не ограничен и может достигать огромных размеров на больших объемах входных данных. В различных модификациях установлены лимиты на размер словаря: при достижении определенного лимита словарь может «замораживаться» (в него перестают добавляться новые слова), из словаря могут удалять менее используемые или самые старые слова и так далее.

Самой известной модификацией <tex>\mathrm{LZ78}</tex> является [[Алгоритм LZW|LZW]]. В нём есть две важных особенности. Первая {{---}} словарь изначально инициализирован всеми символами алфавита. Вторая {{---}} после нахождения максимального префикса поиск следующего префикса начинается не с символа после неподходящего, а с самого неподходящего символа. Это позволяет не выводить неподходящий символ, а выяснять его прямо из словаря. Эта модификация используется в том числе в изображениях в формате <tex>\mathrm{GIF}</tex><ref>[https://en.wikipedia.org/wiki/GIF Wikipedia {{---}} GIF]</ref>.

== См. также ==
* [[Алгоритм RLE]]
* [[Алгоритм LZW]]
* [[Алгоритм LZSS]]
* [[Алгоритм LZMA]]

== Примечания ==
<references/>

== Источники информации ==
* [https://en.wikipedia.org/wiki/LZ77_and_LZ78 Wikipedia {{---}} LZ77 and LZ78]
* [http://ru.wikipedia.org/wiki/LZ77 Википедия {{---}} LZ77]
* [https://fenix.tecnico.ulisboa.pt/downloadFile/1407993358859638/Lempel_Ziv_by_Zeeh.pdf The Lempel Ziv Algorithm]
* [http://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]
* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]
* [http://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Алгоритмы сжатия]]

Викиконспекты - Вклад участника [ru]

Алгоритмы LZ77 и LZ78