Алгоритмы LZ77 и LZ78 — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 8 промежуточных версий 5 участников)
Строка 1: Строка 1:
LZ77 и LZ78 {{---}} алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы {{---}} самые известные варианты в семье LZ*, которая также включает LZW, LZSS, LZMA и другие алгоритмы.
+
<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 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78.
 
  
 
== LZ77 ==
 
== LZ77 ==
=== Описание алгоритма ===
 
LZ77 использует уже просмотренную часть сообщения как словарь. Чтобы достигнуть сжатия, алгоритм пытается заменить очередной фрагмент сообщения на указатель в содержимое словаря.
 
  
В качестве модели данных LZ77 использует "скользящее" по сообщению окно, разделенное на две неравных части. Первая часть, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, {{---}} буфер, содержащий еще не закодированные символы. Как правило, размер окна {{---}} несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буфера.
+
=== Идея алгоритма ===
 +
В кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <tex>\mathrm{LZ77}</tex>, заключается в замене повторений на ссылки на позиции в тексте, где такие подстроки уже встречались.
  
Алгоритм LZ77 выдает коды, состоящие из трех элементов:
+
Информацию о повторении можно закодировать парой чисел {{---}} смещением назад от текущей позиции (<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>.
*длина подстроки;
 
*первый символ в буфере после подстроки.
 
  
После этого алгоритм перемещает окно на длину совпадающей подстроки +1 символ влево.
+
[[Файл: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>
 +
<font color=green>// <tex>s</tex> {{---}} исходная строка
 +
// функция возвращает список блоков <tex>\langle offset, length, next \rangle</tex></font>
 +
'''list<Node>''' encodeLZ77('''string''' s):
 +
    '''list<Node>''' ans = []
 +
    pos = 0
 +
    '''while''' pos < s.length:
 +
        offset, length = findMatching(buffer, pos)  <font color=green>// ищем слово в словаре</font>
 +
        shiftBuffer(length + 1)                      <font color=green>// перемещаем скользящее окно</font>
 +
        pos += length
 +
        ans.push({offset, length, s[pos]})          <font color=green>// добавляем в ответ очередной блок</font>
 +
    '''return''' ans
 +
</code>
  
Если совпадение не найдено, алгоритм выдает код ''<0, 0, первый символ в буфере>'' и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.
 
 
=== Пример ===
 
=== Пример ===
{| border="1"  
+
 
!Сообщение
+
Рассмотрим пример кодирования <tex>\mathrm{LZ77}</tex> на строке <tex>abacabacabadaca</tex> с буфером размера <tex>5</tex>. Квадратом обведен буфер.
!Подстрока
+
 
!Код
+
{| class="wikitable"
|-
+
! Строка || Совпадение || Закодированная последовательность || Примечание
|<tex>\fbox{kababa}bababz</tex>
+
|-
|
+
| <tex>abacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, a \rangle</tex> || Буфер пуст
|<0,0,<tex>k</tex>>
+
|-
|-
+
| <tex>\fbox{$a$}bacabacabadaca</tex> || {{---}} || <tex>\langle 0, 0, b \rangle</tex> || В буфере нет <tex>b</tex>
|<tex>k\fbox{ababab}ababz</tex>
+
|-
|
+
| <tex>\fbox{$ab$}acabacabadaca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> ||
|<0,0,<tex>a</tex>>
+
|-
|-
+
| <tex>\fbox{$abac$}abacabadaca</tex> || <tex>abacaba</tex> || <tex>\langle 4, 7, d \rangle</tex> || Здесь выгодно сделать так, что <tex>offset < length</tex>
|<tex>ka\fbox{bababa}babz</tex>
+
|-
|
+
| <tex>abacaba\fbox{$cabad$}aca</tex> || <tex>a</tex> || <tex>\langle 2, 1, c \rangle</tex> || Последовательность <tex>aca</tex> уже встречалась, но она находится за пределами окна, и <tex>\mathrm{LZ77}</tex> её не находит
|<0,0,<tex>b</tex>>
+
|-
|-
+
| <tex>abacabaca\fbox{$badac$}a</tex> || <tex>a</tex> || <tex>\langle 2, 1, \varnothing \rangle</tex> || Символов в строке больше нет, поэтому в качестве <tex>next</tex> ставим символ конца строки
|<tex>kab\fbox{ababab}abz</tex>
+
|}
|<tex>ab</tex>
+
 
|<2,2,<tex>a</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>kababa\fbox{bababz}</tex>
+
=== Декодирование ===
|<tex>babab</tex>
+
Для декодирования <tex>\mathrm{LZ77}</tex> необходимо пройти по уже раскодированной строке назад, вывести необходимую последовательность, затем следующий символ.
|<2,5,<tex>z</tex>>
+
 
|}
+
Псевдокод этого алгоритма:
 +
 
 +
<code>
 +
  <font color=green>// <tex>encoded</tex> {{---}} список блоков <tex>\langle offset, length, next \rangle</tex>
 +
// функция возвращает декодированную строку</font>
 +
  '''string''' decodeLZ77('''list<Node>''' encoded):
 +
    ans = ""
 +
    '''for''' node '''in''' encoded:
 +
        '''if''' node.length > 0:                        <font color=green>// если необходим повтор</font>
 +
            start = ans.length - node.offset        <font color=green>// возвращаемся на <tex>offset</tex> символов назад</font>
 +
            '''for''' i = 0 .. node.length - 1:          <font color=green>// добавляем <tex>length</tex> символов</font>
 +
                ans += ans[start + i]
 +
        ans += node.next                            <font color=green>// добавляем следующий символ</font>
 +
    '''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 ==
 
== LZ78 ==
=== Описание алгоритма ===
 
Алгоритм LZ78 вносит все встреченные последовательности в словарь. Каждый раз, когда среди данных, которые нужно сжать, встречается последовательность, программа обращается к словарю:
 
  
* если последовательность находится в словаре, то на выход подается код для этой записи
+
=== Идея алгоритма ===
 +
Алгоритм <tex>\mathrm{LZ78}</tex> имеет немного другую идею: этот алгоритм в явном виде использует словарный подход, генерируя временный словарь во время кодирования и декодирования.
  
* если последовательность {{---}} дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь
+
Изначально словарь пуст, а алгоритм пытается закодировать первый символ. На каждой итерации мы пытаемся увеличить кодируемый префикс, пока такой префикс есть в словаре. Кодовые слова такого алгоритма будут состоять из двух частей {{---}} номера в словаре самого длинного найденного префикса (<tex>pos</tex>) и символа, который идет за этим префиксом (<tex>next</tex>). При этом после кодирования такой пары префикс с приписанным символом добавляется в словарь, а алгоритм продолжает кодирование со следующего символа.
 +
 
 +
=== Реализация ===
 +
 
 +
Будем хранить результат кодирования в такой структуре:
 +
 
 +
<code>
 +
'''struct''' Node:
 +
    '''int''' pos  <font color=green>// номер слова в словаре</font>
 +
    '''char''' next
 +
</code>
 +
 
 +
В качестве словаря будем использовать обычный <code>map</code>:
 +
 
 +
<code>
 +
'''list<Node>''' encodeLZ78('''string''' s):
 +
    '''string''' buffer = ""                              <font color=green>// текущий префикс</font>           
 +
    '''map<string, int>''' dict = {}                      <font color=green>// словарь</font>
 +
    '''list<Node>''' ans = []                            <font color=green>// ответ</font>
 +
    '''for''' i = 0 .. s.length - 1:
 +
        '''if''' dict.hasKey(buffer + s[i]):              <font color=green>// можем ли мы увеличить префикс</font>
 +
            buffer += s[i]
 +
        '''else''':
 +
            ans.push({dict[buffer], s[i]})          <font color=green>// добавляем пару в ответ</font>
 +
            dict[buffer + s[i]] = dict.length + 1  <font color=green>// добавляем слово в словарь</font>
 +
            buffer = ""                            <font color=green>// сбрасываем буфер</font>
 +
    '''if''' not (buffer is empty): <font color=green>// если буффер не пуст - этот код уже был, нужно его добавить в конец словаря</font>
 +
        last_ch = buffer.peek() <font color=green>// берем последний символ буффера, как "новый" символ</font>
 +
        buffer.pop() <font color=green>// удаляем последний символ из буфера</font>
 +
        ans.push({dict[buffer], last_ch}) <font color=green>// добавляем пару в ответ</font>
 +
    '''return''' ans
 +
</code>
  
Например, если в словаре уже хранится последовательность ''ABC'', и программа встречает последовательность ''ABCA'', то на выход сначала подается код из словаря для ''ABC'', затем символ ''A'', а затем последовательность ''ABCA'' будет добавлена в словарь. Если потом встретится последовательность ''ABCAB'', на выход подастся код для ''ABCA'', символ ''B'', и в словарь добавится ''ABCAB''. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет в словарь новую последовательность, которая на один байт длиннее.
 
 
=== Пример ===
 
=== Пример ===
{| border="1"
 
!Сообщение
 
!Код
 
!Новая последовательность в словаре
 
|-
 
| <tex>\ abracadabra</tex>
 
|<0,<tex>a</tex>>
 
|<tex>1.\ a</tex>
 
|-
 
|<tex>a\ bracadabra</tex>
 
|<0,<tex>b</tex>>
 
|<tex>2.\ b</tex>
 
|-
 
|<tex>ab\ racadabra</tex>
 
|<0,<tex>r</tex>>
 
|<tex>3.\ r</tex>
 
|-
 
|<tex>abr\ acadabra</tex>
 
|<1,<tex>c</tex>>
 
|<tex>4.\ ac</tex>
 
|-
 
|<tex>abrac\ adabra</tex>
 
|<1,<tex>d</tex>>
 
|<tex>5.\ ad</tex>
 
|-
 
|<tex>abracad\ abra</tex>
 
|<1,<tex>b</tex>>
 
|<tex>6.\ ab</tex>
 
|-
 
|<tex>abracadab\ ra</tex>
 
|<3,<tex>a</tex>>
 
|<tex>7.\ ra</tex>
 
|}
 
  
== Ссылки ==
+
В этот раз для примера возьмем строку <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 = [""]                        <font color=green>// словарь, слово с номером 0 {{---}} пустая строка</font>
 +
    '''string''' ans = ""                                <font color=green>// ответ</font>
 +
    '''for''' node '''in''' encoded:
 +
        word = dict[node.pos] + node.next          <font color=green>// составляем слово из уже известного из словаря и новой буквы</font>
 +
        ans += word                                <font color=green>// приписываем к ответу</font>
 +
        dict.push(word)                            <font color=green>// добавляем в словарь</font>
 +
    '''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://rain.ifmo.ru/cat/view.php/vis/data-compression/lz-2000 Визуализатор алгоритма LZ78]
* [http://ru.wikipedia.org/wiki/LZ77 Соответствующая статья в википедии(Алгоритм LZ77 описан по-другому) ]
 
 
* [http://compression.ru/download/articles/rev_univ/semenyuk_2001_econom_encoding.pdf Семенюк В.В. {{---}} Экономное кодирование дискретной информации]
 
* [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://mf.grsu.by/UchProc/livak/en/po/comprsite/theory_lz77.html Алгоритм LZ77]
* [http://acy-books.ru/?p=62 Алгоритм LZ78]
+
* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78]
* [http://www.binaryessence.com/dct/en000140.htm Lempel-Ziv-78 (LZ78)]
 
  
 
[[Категория: Дискретная математика и алгоритмы]]
 
[[Категория: Дискретная математика и алгоритмы]]
 
+
[[Категория: Алгоритмы сжатия]]
[[Категория: Алгоритмы сжатия ]]
 

Текущая версия на 19:05, 4 сентября 2022

[math]\mathrm{LZ77}[/math] и [math]\mathrm{LZ78}[/math] — алгоритмы сжатия без потерь, опубликованные Абрахамом Лемпелем[1] и Якобом Зивом[2] в [math]1977[/math] и [math]1978[/math] годах соответственно. Эти алгоритмы стали основой других алгоритмов семьи [math]\mathrm{LZ*}[/math]: LZW, LZSS, LZMA и другие. Оба приведенных алгоритма используют словарный подход.

LZ77

Идея алгоритма

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

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

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

LZ77-simple-example.jpg

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

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

Реализация

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

struct Node:
    int offset
    int length
    char next

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

Функция shiftBuffer сдвигает буфер вперёд на [math]x[/math] символов.

// [math]s[/math] — исходная строка
// функция возвращает список блоков [math]\langle offset, length, next \rangle[/math]
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

Пример

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

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

Результатом кодирования является список полученных троек: [math]\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][/math].

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

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

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

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

Модификации

Известно много различных модификаций алгоритма [math]\mathrm{LZ77}[/math]. Например, вместо блоков можно хранить отдельно одиночные символы и отдельно — пары [math]\langle offset, length \rangle[/math] (length-distance pair[3]). Алгоритм LZSS является улучшением [math]\mathrm{LZ77}[/math] и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате [math]\mathrm{PalmDoc}[/math][4] на каждую пару смещения и длины выделяется по [math]2[/math] байта.

Также на [math]\mathrm{LZ77}[/math] основаны алгоритмы [math]\mathrm{LZH}[/math][5] и [math]\mathrm{DEFLATE}[/math][6] (последний является широко используемым), которые совмещают [math]\mathrm{LZ77}[/math] с алгоритмом Хаффмана, кодируя элементы пар и одиночные символы.


LZ78

Идея алгоритма

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

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

Реализация

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

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

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

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

Пример

В этот раз для примера возьмем строку [math]abacababacabc[/math].

Словарь Осталось обработать Найденный префикс Код Примечание
[math]\varnothing[/math] [math]abacababacabc[/math] [math]\langle 0, a \rangle[/math] В словаре ничего не нашлось, вместо номера в словаре указываем [math]0[/math]
[math]a[/math] [math]bacababacabc[/math] [math]\langle 0, b \rangle[/math]
[math]a[/math], [math]b[/math] [math]acababacabc[/math] [math]a[/math] [math]\langle 1, c \rangle[/math] Нашелся префикс [math]a[/math] (слова в словаре нумеруются с [math]1[/math]), добавляем [math]ac[/math]
[math]a[/math], [math]b[/math], [math]ac[/math] [math]ababacabc[/math] [math]a[/math] [math]\langle 1, b \rangle[/math]
[math]a[/math], [math]b[/math], [math]ac[/math], [math]ab[/math] [math]abacabc[/math] [math]ab[/math] [math]\langle 4, a \rangle[/math]
[math]a[/math], [math]b[/math], [math]ac[/math], [math]ab[/math], [math]aba[/math] [math]cabc[/math] [math]\langle 0, c \rangle [/math]
[math]a[/math], [math]b[/math], [math]ac[/math], [math]ab[/math], [math]aba[/math], [math]c[/math] [math]abc[/math] [math]ab[/math] [math]\langle 4, c\rangle [/math]

Результатом кодирования является список пар: [math]\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][/math]

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

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

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

Модификации

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

Самой известной модификацией [math]\mathrm{LZ78}[/math] является LZW. В нём есть две важных особенности. Первая — словарь изначально инициализирован всеми символами алфавита. Вторая — после нахождения максимального префикса поиск следующего префикса начинается не с символа после неподходящего, а с самого неподходящего символа. Это позволяет не выводить неподходящий символ, а выяснять его прямо из словаря. Эта модификация используется в том числе в изображениях в формате [math]\mathrm{GIF}[/math][7].

См. также

Примечания

Источники информации