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

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

LZ77

Можно сказать, что алгоритмы семейства LZ* представляют собой более сложное обобщение простого и интуитивного способа сжатия данных, используемого в RLE.

Принципы работы алгоритма

Основная суть алгоритма - это замена повторно вхождения строки ссылкою на одну из предыдущих позиций вхождения. Для этого используют метод скользящего окна. Скользящее окно можно представить в виде динамической структуры данных который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». В стандартном алгоритме LZ77 совпадения строки кодируются парой:

• длина совпадения (match length)
• смещение (offset) или дистанция (distance)

Кодируемая пара трактуется именно как команда копирования символов из скользящего окна с определенной позиции, или дословно как: «Вернуться в словаре на значение смещения символов и скопировать значение длины символов, начиная с текущей позиции». Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары длина-смещение является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения. Пример с командой копирования не совсем очевиден: «Вернуться на 1 символ назад в буфере и скопировать 7 символов, начиная с текущей позиции». Каким образом можно скопировать 7 символов из буфера, когда в настоящий момент в буфере находится только 1 символ? Однако следующая интерпретация кодирующей пары может прояснить ситуацию: каждые 7 последующих символов совпадают (эквивалентны) с 1 символом перед ними. Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ еще отсутствует в буфере на момент декодирования текущей пары длина-смещение.

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

LZ77 использует "скользящее" по сообщению окно. Допустим на текущей итерации окно зафиксировано. С правой стороны окна наращиваем подстроку пока она есть в строке скользящее окно + наращиваемая строка и начинается в скользящем окне. Назовем наращиваемую строку буфером. После наращивания алгоритм выдает код состоящий из трех элементов:

• смещение в окне;
• длина буфера;
• последний символ буфера.

В конце итерации алгоритм сдвигает окно на длину равную длине буфера+1.

Пример "kabababababz"

Содержимое окна(длина равна 4)	Содержимое буфера	КОД
	'k'	<0,0,'k'>
'k'	'a'	<0,0,'a'>
'ka'	'b'	<0,0,'b'>
'kab'	'aba'	<2,2,'a'>
'baba'	'bababz'	<2,5,'z'>

LZ78

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

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

Пример "kabababababz"

Содержимое словаря	Содержимое считываемая строка	КОД
	'k'	<0,'k'>
'k'	'a'	<0,'a'>
'k','a'	'b'	<0,'b'>
'k','a','b'	'ab'	<2,'b'>
'k','a','b','ab'	'aba'	<4,'a'>
'k','a','b','ab','aba'	'ba'	<3,'а'>
'k','a','b','ab','aba','ba'	'abab'	<'3,'z'>

Ссылки

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

[math] \documentclass[11pt,a4paper,oneside,landscape,twocolumn]{article} \usepackage[T2A]{fontenc} \usepackage[cp1251]{inputenc} \usepackage[english,russian]{babel} \usepackage[russian,landscape]{olymp} \usepackage{graphicx} \usepackage{amsmath,amssymb} %\usepackage{expdlist} %\usepackage{textpos} \contest{% ЛКШ.июль 2009, группа А0% }{% Берендеевы Поляны% }{% 10 июля 2009 года% }% \renewcommand{\t}{\texttt} \renewcommand{\leqslant}{\le} \binoppenalty=10000 \relpenalty=10000 \exhyphenpenalty=10000 \createsection{\Illustration}{Иллюстрация} \createsection{\Scoring}{Система оценки} \begin{document} \raggedbottom \input problems/painter.tex \input problems/numbers.tex \input problems/melkman.tex \end{document}[/math]