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

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

В отличие от LZ77, работающего с уже полученными данными, LZ78 ориентируется на данные, которые только будут получены (LZ78 не использует скользящее окно, он хранит словарь из уже просмотренных фраз). Алгоритм считывает символы сообщения до тех пор, пока накапливаемая подстрока входит целиком в одну из фраз словаря. Как только эта строка перестанет соответствовать хотя бы одной фразе словаря, алгоритм генерирует код, состоящий из индекса строки в словаре, которая до последнего введенного символа содержала входную строку, и символа, нарушившего совпадение. Затем в словарь добавляется введенная подстрока. Если словарь уже заполнен, то из него предварительно удаляют менее всех используемую в сравнениях фразу. Если в конце алгоритма мы не находим символ, нарушивший совпадения, то тогда мы выдаем код в виде <индекс строки в словаре без последнего символа, последний символ>.

Пример [math]kabababababz[/math]

Содержимое словаря	Содержимое считываемой строки	КОД
	[math]k[/math]	<0,[math]k[/math]>
[math]k[/math]	[math]a[/math]	<0,[math]a[/math]>
[math]k[/math], [math]a[/math]	[math]b[/math]	<0,[math]b[/math]>
[math]k[/math], [math]\fbox{a}[/math], [math]b[/math]	[math]ab[/math]	<2,[math]b[/math]>
[math]k[/math], [math]a[/math], [math]b[/math], [math]\fbox{ab}[/math]	[math]aba[/math]	<4,[math]a[/math]>
[math]k[/math], [math]a[/math], [math]\fbox{b}[/math], [math]ab[/math], [math]aba[/math]	[math]ba[/math]	<3,[math]a[/math]>
[math]k[/math], [math]a[/math], [math]b[/math], [math]ab[/math], [math]\fbox{aba}[/math], [math]ba[/math]	[math]abab[/math]	<5,[math]b[/math]>
[math]k[/math], [math]a[/math], [math]b[/math], [math]ab[/math], [math]aba[/math], [math]ba[/math], [math]abab[/math]	[math]z[/math]	<0,[math]z[/math]>

Ссылки

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