Алгоритмы 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]

Ссылки

• Визуализатор алгоритма LZ78
• Соответствующая статья в википедии(Алгоритм LZ77 описан по-другому)
• Семенюк В.В. - Экономное кодирование дискретной информации