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

[math]\mathrm{LZ77}[/math] и [math]\mathrm{LZ78}[/math] — алгоритмы сжатия без потерь, опубликованные Абрахамом Лемпелем и Якобом Зивом в [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].

Для эффективного поиска повторов в [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). Алгоритм LZSS является улучшением [math]\mathrm{LZ77}[/math] и хранит однобитный флаг, показывающий, какие данные за ним идут: одиночный символ или пара смещения и длины. В формате [math]\mathrm{PalmDoc}[/math] на каждую пару смещения и длины выделяется по [math]2[/math] байта.

Также на [math]\mathrm{LZ77}[/math] основаны алгоритмы [math]\mathrm{LZH}[/math] и [math]\mathrm{DEFLATE}[/math] (последний является широко используемым), которые совмещают [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].

См. также

• Алгоритм RLE
• Алгоритм LZW
• Алгоритм LZSS
• Алгоритм LZMA

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

• Wikipedia — LZ77 and LZ78
• Википедия — LZ77
• The Lempel Ziv Algorithm
• Визуализатор алгоритма LZ78
• Семенюк В.В. — Экономное кодирование дискретной информации
• Алгоритм LZ77
• Lempel-Ziv-78