Алгоритм LZW

Определение:

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь

Он был создан Абрахамом Лемпелем(Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Он был опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм не проводит анализ входных данных поэтому не оптимален, но быстро реализуем.

Применение

В свое время LZW был лучшим алгоритмом сжатия. Он стал первым широко используемым на компьютерах методом сжатия данных.

Алгоритм был реализован в программе compress, которая стала более или менее стандартной утилитой Unix-систем приблизительно в 1986 году. Многие другие утилиты-архиваторы также используют этот метод или близкие к нему.

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.

PDF содержит этот алгоритм.

Описание

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

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

Алгоритм

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
2. Считать очередной символ K из кодируемого сообщения.
3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе
4. Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.

Конец

Пример

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

ABCABCABCABCABCABC#

Маркер # используется для обозначения конца сообщения. Тем самым, в нашем алфавите 4 символа. Компьютер представляет это в виде групп бит, для представления каждого символа алфавита нам достаточно группы из 2 бит на символ. По мере роста словаря, размер групп должен расти, с тем чтобы учесть новые элементы. 2-битные группы дают 2² = 4 возможные комбинации бит, поэтому, когда в словаре появится 5-е слово, алгоритм должен перейти к 3-битным группам. Заметим, что, поскольку используется группа из всех нолей 00, то 5-я группа имеет код 4. Начальный словарь будет содержать:

Символ	Битовый код	Номер
#	00	0
A	01	1
B	10	2
C	11	3

Кодирование

Без использования алгоритма LZW, при передаче сообщения как оно есть — 18 символов по 2 бит на каждый — оно займёт 36 бит. Сравним это с тем, что получается при использовании LZW:

Текущий символ	Следующий символ	Вывод		Расширенный словарь		Комментарии
		Код	Биты
NULL	A
A	B	1	01	4:	AB
B	C	2	10	5:	BC
C	A	3	11	6:	CA
AB	C	4	100	7:	ABC
CA	B	6	110	8:	CAB
BC	A	5	101	9:	BCA
ABC	A	7	111	10:	ABCA
ABCA	B	10	1010	11:	ABCAB
BC	#	5	101			выводим текущую последовательность
		0	000000			и останавливаем кодирование

Длина закодированного текста = 25 битов.

Таким образом, используя LZW мы сократили сообщение на 11 бит из 36 — это почти 30 %. Если сообщение будет длиннее, то элементы словаря будут представлять всё более и более длинные части текста, благодаря чему повторяющиеся слова будут представлены очень компактно.

Декодирование

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

Данные		На выходе	Новая запись				Комментарии
Биты	Код		Полная		Частичная
01	1	A			4:	A?
10	2	B	4:	AB	5:	B?
11	3	C	5:	BC	6:	C?
100	4	AB	6:	CA	7:	AB?
110	6	CA	7:	ABC	8:	CA?
101	5	BC	8:	CAB	9:	BC?
111	7	ABC	9:	BCA	10:	ABC?
1010	10	ABCA	10:	ABCA	11:	ABCA?	Решение проблемы см. ниже
101	5	BC	11:	ABCAB	12:	BC?
000000	0	#

Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, ABC?, он знает, что слово 10 начинается с ABC, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA:

Данные:     На выходе:     Новая запись:
                        Полная:      Частичная:
.
.
.
011101 = 29     AB      46: (word)   47: AB?
101111 = 47     AB?  <--- что нам с этим делать?

На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на «символ идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа идущего следующим», и поэтому оно заканчивается тем же символом что и начинается, в данном случае — A. Этот трюк позволяет декодеру определить, что слово 47 это ABA.

В общем случае, такая ситуация появляется, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре.

Патенты

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. К настоящему времени, сроки всех патентов истекли.

Unisys, GIF и PNG

Компания Unisys приобрела патент на этот алгоритм. Поэтому использование формата GIF, в котором он используется, было раскритиковано из-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).

К настоящему сроку патенты истекли, поэтому спор утих.

Источники

• Wikipedia | LZW (рус)

• Wikipedia | LZW (англ)

• Семенюк В.В. - Экономное кодирование дискретной информации