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

Материал из Викиконспекты
Перейти к: навигация, поиск

LZ77 и LZ78 - алгоритмы сжатия без потерь, опубликованные в статьях Абрахама Лемпеля и Якоба Зива в 1977 и 1978 годах. Эти алгоритмы - самые известные варианты в семье LZ*, которая также включает LZW, LZSS, LZMA и другие алгоритмы. Оба алгоритма - алгоритмы со словарным подходом. Алгоритм LZ77 использует "скользящее окно", которое эквивалентно неявному использованию словарного подхода, сначала предложенного в LZ78.

LZ77

Описание алгоритма

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

В качестве модели данных LZ77 использует "скользящее" по сообщению окно, разделенное на две неравных части. Первая часть, большая по размеру, включает уже просмотренную часть сообщения. Вторая, намного меньшая, - буфер, содержащий еще не закодированные символы. Как правило, размер окна - несколько килобайтов. Буфер намного меньше, обычно не больше, чем сто байтов. Алгоритм пытается найти фрагмент в словаре, который совпадает с содержанием буфера.

Алгоритм LZ77 выдает коды, состоящие из трех элементов:

  • смещение в словаре относительно его начала подстроки, которая соответствует содержанию буфера;
  • длина подстроки;
  • первый символ в буфере после подстроки.

После этого алгоритм перемещает окно на длину совпадающей подстроки +1 символ влево.

Если совпадение не найдено, алгоритм выдает код <0, 0, первый символ в буфере> и продолжает свою работу. Хотя такое решение неэффективно, оно гарантирует, что алгоритм сможет закодировать любое сообщение.

Пример

Сообщение Подстрока Код
[math]\fbox{kababa}bababz[/math] <0,0,[math]k[/math]>
[math]k\fbox{ababab}ababz[/math] <0,0,[math]a[/math]>
[math]ka\fbox{bababa}babz[/math] <0,0,[math]b[/math]>
[math]kab\fbox{ababab}abz[/math] [math]ab[/math] <2,2,[math]a[/math]>
[math]kababa\fbox{bababz}[/math] [math]babab[/math] <2,5,[math]z[/math]>

LZ78

Описание алгоритма

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

  • если последовательность находится в словаре, то на выход подается код для этой записи
  • если последовательность - дополненная версия последовательности из словаря, то эта последовательность добавляется в словарь

Например, если в словаре уже хранится последовательность ABC, и программа встречает последовательность ABCA, то на выход сначала подается код из словаря для ABC, затем символ A, а затем последовательность ABCA будет добавлена в словарь. Если потом встретится последовательность ABCAB, на выход подастся код для ABCA, символ B, и в словарь добавится ABCAB. Каждый раз, когда программа встречает последовательность из словаря, она выдает код и добавляет в словарь новую последовательность, которая на один байт длиннее.

Пример

Сообщение Код Новая последовательность в словаре
[math]\ abracadabra[/math] <0,[math]a[/math]> [math]1.\ a[/math]
[math]a\ bracadabra[/math] <0,[math]b[/math]> [math]2.\ b[/math]
[math]ab\ racadabra[/math] <0,[math]r[/math]> [math]3.\ r[/math]
[math]abr\ acadabra[/math] <1,[math]c[/math]> [math]4.\ ac[/math]
[math]abrac\ adabra[/math] <1,[math]d[/math]> [math]5.\ ad[/math]
[math]abracad\ abra[/math] <1,[math]b[/math]> [math]6.\ ab[/math]
[math]abracadab\ ra[/math] <3,[math]a[/math]> [math]7.\ ra[/math]

Ссылки