LZ77

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

Оба алгоритма относятся к словарным методам, в отличие от других методов уменьшения избыточности, таких как RLE и арифметическое сжатие. LZ77 является алгоритмом со «скользящим окном», что эквивалентно неявному использованию словарного подхода, впервые предложенного в LZ78.

LZ77

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

Принцип скользящего окна

Метод кодирования, согласно принципу скользящего окна, учитывает уже ранее встречавшуюся информацию, то есть информацию, которая уже известна для кодировщика и декодировщика (второе и последующие вхождения некоторой строки символов в сообщении заменяются ссылками на её первое вхождение).

Благодаря этому принципу алгоритмы LZ* иногда называются методами сжатия с использованием скользящего окна. Скользящее окно можно представить в виде буфера (или более сложной динамической структуры данных), который организован так, чтобы запоминать «сказанную» ранее информацию и предоставлять к ней доступ. Таким образом, сам процесс сжимающего кодирования согласно LZ77 напоминает написание программы, команды которой позволяют обращаться к элементам «скользящего окна», и вместо значений сжимаемой последовательности вставлять ссылки на эти значения в «скользящем окне». Размер скользящего окна может динамически изменяться и составлять 2, 4 или 32 килобайта. Следует также отметить, что размер окна кодировщика может быть меньше или равен размеру окна декодировщика, но не наоборот.

Приведенное выше сравнение процесса кодирования с «программированием» может натолкнуть на преждевременный вывод о том, что алгоритм LZ77 относится к методам контекстного моделирования. Поэтому следует отметить, что алгоритм LZ77 принято классифицировать как метод словарного сжатия данных, когда вместо понятия «скользящего окна» используется термин «динамического словаря».

Механизм кодирования совпадений

Перед тем, как перейти к рассмотрению механизма кодирования, уточним понятие совпадения (от англ. match). Рассмотрим последовательность из N элементов. Если все элементы последовательности уникальны, то такая последовательность не будет содержать ни одного повторяющегося элемента, или, иначе говоря, в последовательности не найдется хотя бы двух равных друг другу или совпадающих элементов.

В стандартном алгоритме LZ77 совпадения кодируются парой:

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

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

Хотя для приверженцев императивного программирования такая интерпретация может показаться интуитивно понятной, она мало говорит о сущности алгоритма LZ77 как метода сжатия. Особенность данного алгоритма сжатия заключается в том, что использование кодируемой пары длина-смещение является не только приемлемым, но и эффективным в тех случаях, когда значение длины превышает значение смещения.

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

Это означает, что каждый символ можно однозначно определить, переместившись назад в буфере — даже если данный символ ещё отсутствует в буфере на момент декодирования текущей пары длина-смещение. Такая кодируемая пара будет представлять собой многократное (определяемое значением смещения) повторение последовательности (определяемой значением длины) символов, что представляет собой более общую форму RLE.

Недостатки

• невозможность кодирования подстрок, отстоящих друг от друга на расстоянии, большем длины словаря
• длина подстроки, которую можно закодировать, ограничена размером буфера
• малая эффективность при кодировании незначительного объёма данных

Пример «abracadabra»

              Поз.  Длина    Симв.
 abracadabra    0      0      a
a bracadabra    0      0      b
ab racadabra    0      0      r
abr acadabra    3      1      ac
abrac adabra    2      1      ad	
abracad abra    7      4      abra

Выделенные символы отсутствуют в кодирующей последовательности.

LZ78

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

Пример

Пусть задана строка ACAGAATAGAGA.

Словарь	Содержимое считываемой строчки	Код
	A	<0, A>
A = 1	C	<0, C>
A = 1 C = 2	AG	<1, G>
A = 1, C = 2 AG = 3	AA	<1, A>
A = 1, C = 2 AG = 3, AA = 4	T	<0, T>
A = 1, C = 2, AG = 3 AA = 4, T = 5	AGA	<3, A>
A = 1, C = 2, AG = 3 AA = 4, T = 5, AGA = 6	G	<0, G>
A = 1, C = 2, AG = 3, AA = 4 T = 5, AGA = 6, G = 7	A	<1, EOF>

Результатом работы будет последовательность: <0, A><0, C><1, G><1, A><0, T><3, A><0, G><1, EOF>.

Ссылки

• Jacob Ziv, Abraham Lempel. A Universal Algorithm for Sequential Data Compression IEEE Transactions on Information Theory, 23(3), pp. 337—343, May 1977.
• Пример работы алгоритма LZ77 (см. example «abracadabra»)
• Владимир Лидовский, Лекция 7: Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива (LZ78) в курсе лекций «Основы теории информации и криптографии» // Интуит.ру, 11.04.2007