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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Реализация)
 
(не показано 48 промежуточных версий 9 участников)
Строка 1: Строка 1:
'''LZ77''' и '''LZ78''' — алгоритмы сжатие без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы наиболее известные варианты в семействе LZ*, которое включает в себя также [[Алгоритм LZW|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 ==
Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в [[RLE]].
 
=== Принципы работи алгоритма ===
 
Основная суть алгоритма - ето замена повторно вхождения строки ссылкою на одну из  предыдущих позиций вхождения.
 
Для етого используют метод скользящего окна.
 
Метод кодирования согласно принципу скользящего окна учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на ее первое вхождение).
 
Скользящее окно можно представить в видединамической структуры данных который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ.
 
Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне».
 
Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть менее или равен размеру окна декодировщика, но не наоборот.
 
Рассмотрим последовательность из N элементов.
 
  
В стандартном алгоритме LZ77 совпадения строки кодируются парой:
+
=== Идея алгоритма ===  
* длина совпадения (match length)
+
В кодируемых строках часто содержатся совпадающие длинные подстроки. Идея, лежащая в основе <tex>\mathrm{LZ77}</tex>, заключается в замене повторений на ссылки на позиции в тексте, где такие подстроки уже встречались.
* смещение (offset) или дистанция (distance)
 
Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в словаре на ''значение смещения''  символов и скопировать ''значение длины'' символов, начиная с текущей позиции».
 
Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары ''длина-смещение'' является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.
 
Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними.
 
Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары ''длина-смещение''.
 
=== Описания алгоритма===
 
LZ77 использует "скользящее" по сообщению окно, разделенное на две неравные части. Первая, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, является буфером, содержащим еще незакодированные символы входного потока. Обычно размер буфера составляет не более ста байт. Алгоритм пытается найти в скользящем окне фрагмент, совпадающий с содержимым буфера.
 
  
Алгоритм 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>.
{| border="2"
 
!Содержымое окна
 
!Содержимое буфера
 
!КОД
 
|-
 
|'.....'(
 
|Ячейка 2*2
 
|Ячейка 3*2
 
|-
 
|Ячейка 1*3
 
|Ячейка 2*3
 
|Ячейка 3*3
 
|}
 
  
              Поз. Длина    Симв.
+
[[Файл:LZ77-simple-example.jpg]]
  ''mississippi ''    0      0      a
 
a ''bracadabra''    0      0      b
 
ab ''racadabra''    0      0      r
 
'''a'''br ''acadabra''    3      1      c
 
abr'''a'''c ''adabra''    2      1      d
 
'''abra'''cad ''abra''    7      4      abra
 
  
{{скрытый текст}}
+
Для эффективного поиска повторов в <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>
 +
 
 +
=== Пример ===
 +
 
 +
Рассмотрим пример кодирования <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>
 +
<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> с [[Алгоритм Хаффмана|алгоритмом Хаффмана]], кодируя элементы пар и одиночные символы.
  
Even though all LZ77 algorithms work by definition on the same basic principle, they can vary widely in how they output their encoded data — what values are possible for lengths and distances, for example, and how length-distance pairs are distinguished from ''literals'' (single characters encoded as themselves, rather than as part of a length-distance pair.) A few examples:
 
* The algorithm illustrated in Lempel and Ziv’s original 1977 paper output all its data three values at a time: the length and distance of the longest match found in the buffer, and the literal which followed that match. If two successive characters in the input stream could only be encoded as literals, the length would be 0.
 
* In the [[PalmDoc]] format, a length-distance pair is always encoded by a two-byte sequence. Of the 16 bits that make up these two bytes, 11 bits go to encoding the distance, 3 go to encoding the length, and the remaining two are used to make sure the decoder can identify the first byte as the beginning of such a two-byte sequence.
 
* [[As of 2004]], the most popular LZ77 based compression method is called [[DEFLATE (algorithm)|DEFLATE]]; it combines LZ77 with [[Huffman coding]]. Literals, lengths, and a symbol to indicate the end of the current block of data are all placed together into one alphabet. Distances can be safely placed into a separate alphabet; since a distance only occurs just after a length, it cannot be mistaken for another kind of symbol or vice-versa.
 
-->
 
  
 
== LZ78 ==
 
== LZ78 ==
  
В отличие от LZ77, работающего с уже полученными данными, 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>
 +
 
 +
=== Пример ===
 +
 
 +
В этот раз для примера возьмем строку <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>.
  
== Ссылки ==
+
== См. также ==
* Jacob Ziv, Abraham Lempel. [http://www.cs.duke.edu/courses/spring03/cps296.5/papers/ziv_lempel_1977_universal_algorithm.pdf A Universal Algorithm for Sequential Data Compression] IEEE Transactions on Information Theory, 23(3), pp.337-343, May 1977.
+
* [[Алгоритм RLE]]
* [http://www.binaryessence.com/dct/en000138.htm Пример работы алгоритма LZ77 (см. example "abracadabra")]
+
* [[Алгоритм LZW]]
* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/ Описание алгоритма LZ77 в курсе лекций по теории кодирования информации]
+
* [[Алгоритм LZSS]]
* [http://www.intuit.ru/department/calculate/infotheory/class/free/6/2.html Описание алгоритма LZ78 в курсе лекций по теории кодирования информации]
+
* [[Алгоритм LZMA]]
  
{{compu-stub}}
+
== Примечания ==
{{методы сжатия}}
+
<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]
  
[[cs:LZ77]]
+
[[Категория: Дискретная математика и алгоритмы]]
[[de:LZ77]]
+
[[Категория: Алгоритмы сжатия]]
[[en:LZ77 and LZ78]]
 
[[et:LZ77]]
 
[[fr:LZ77 et LZ78]]
 
[[hu:LZ77]]
 
[[it:LZ77 e LZ78]]
 
[[ja:LZ77]]
 
[[pl:LZ77]]
 
[[pt:LZ77]]
 
[[zh:LZ77与LZ78]]
 

Текущая версия на 12:04, 8 октября 2019

[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 \gt 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].

См. также[править]

Примечания[править]

Источники информации[править]