Алгоритм LZW

Непосредственным предшественником LZW является алгоритм LZ78, опубликованный Абрахамом Лемпелем (Abraham Lempel) и Якобом Зивом (Jacob Ziv) в 1978 г. Этот алгоритм воспринимался как математическая абстракция до 1984 г., когда Терри Уэлч (Terry A. Welch) опубликовал свою работу с модифицированным алгоритмом, получившим в дальнейшем название LZW (Lempel—Ziv—Welch).

Применение

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

Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других, а также отчасти во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Описание

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

Например, если сжимают байтовые данные (текст), то строк в таблице окажется [math]256[/math] (от [math]"0"[/math] до [math]"255"[/math]). Если используется [math]10[/math]-битный код, то под коды для строк остаются значения в диапазоне от [math]256[/math] до заносится первый символ сообщения.

Шаг 2. Считать очередной символ [math]Y[/math] из сообщения.
Шаг 3. Если [math]Y[/math] — это символ конца сообщения, то выдать код для [math]X[/math], иначе:
- Если фраза [math]XY[/math] уже имеется в словаре, то присвоить входной фразе значение [math]XY[/math] и перейти к Шагу 2,
- Иначе выдать код для входной фразы [math]X[/math], добавить [math]XY[/math] в словарь и присвоить входной фразе значение [math]Y[/math]. Перейти к Шагу 2.
Конец.

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

Начало.
Шаг 1. Все возможные символы заносятся в словарь. Во входную фразу [math]X[/math] заносится первый код декодируемого сообщения.
Шаг 2. Считать очередной код [math]Y[/math] из сообщения.
Шаг 3. Если [math]Y[/math] — это конец сообщения, то выдать символ, соответствующий коду [math]X[/math], иначе:
- Если фразы под кодом [math]XY[/math] нет в словаре, вывести фразу, соответствующую коду [math]X[/math], а фразу с кодом [math]XY[/math] занести в словарь.
- Иначе присвоить входной фразе код [math]XY[/math] и перейти к Шагу 2.
Конец.

Пример

Рассмотрим пример сжатия и декодирования сообщения. Сначала создадим начальный словарь единичных символов. В стандартной кодировке ASCII имеется [math]256[/math] различных символов, поэтому, для того, чтобы все они были корректно закодированы (если нам неизвестно, какие символы будут присутствовать в исходном файле, а какие - нет), начальный размер кода будет равен 8 битам. Если нам заранее известно, что в исходном файле будет меньшее количество различных символов, то вполне разумно уменьшить количество бит. Чтобы инициализировать таблицу, мы установим соответствие кода 0 соответствующему символу с битовым кодом [math]00000000[/math], тогда [math]1[/math] соответствует символу с кодом [math]00000001[/math], и т.д., до кода [math]255[/math]. На самом деле мы указали, что каждый код от [math]0[/math] до [math]255[/math] является корневым.

Символ	Битовый код
a	000
b	001
c	010
d	011
e	100

Больше в таблице не будет других кодов, обладающих этим свойством.
По мере роста словаря, размер групп должен расти, с тем, чтобы учесть новые элементы. [math]8[/math]-битные группы дают [math]256[/math] возможных комбинации бит, поэтому, когда в словаре появится [math]256[/math]-е слово, алгоритм должен перейти к [math]9[/math]-битным группам. При появлении [math]512[/math]-ого слова произойдет переход к [math]10[/math]-битным группам, что дает возможность запоминать уже [math]1024[/math] слова и т.д.

В нашем примере алгоритму заранее известно о том, что будет использоваться всего [math]5[/math] различных символов, следовательно, для их хранения будет использоваться минимальное количество бит, позволяющее нам их запомнить, то есть [math]3[/math] ([math]8[/math] различных комбинаций).

Кодирование

Пусть мы сжимаем последовательность [math]abacabadabacabae[/math].

Шаг 1: Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке [math]a[/math] и проверим, есть ли строка [math]a[/math] в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка [math]a[/math] есть в таблице.
Шаг 2: Далее мы читаем следующий символ [math]b[/math] из входного потока и проверяем, есть ли строка [math]ab[/math] в таблице. Такой строки в таблице пока нет.

Добавляем в таблицу [math]\langle5\rangle[/math] [math]ab[/math]. В поток: [math]\langle0\rangle[/math];

Шаг 3: [math]ba[/math] — нет. В таблицу: [math]\langle6\rangle[/math] [math]ba[/math]. В поток: [math]\langle1\rangle[/math];
Шаг 4: [math]ac[/math] — нет. В таблицу: [math]\langle7\rangle[/math] [math]ac[/math]. В поток: [math]\langle0\rangle[/math];
Шаг 5: [math]ca[/math] — нет. В таблицу: [math]\langle8\rangle[/math] [math]ca[/math]. В поток: [math]\langle2\rangle[/math];
Шаг 6: [math]ab[/math] — есть в таблице; [math]aba[/math] — нет. В таблицу: [math]\langle9\rangle[/math] [math]aba[/math]. В поток: [math]\langle5\rangle[/math];
Шаг 7: [math]ad[/math] — нет. В таблицу: [math]\langle10\rangle[/math] [math]ad[/math]. В поток: [math]\langle0\rangle[/math];
Шаг 8: [math]da[/math] — нет. В таблицу: [math]\langle11\rangle[/math] [math]da[/math]. В поток: [math]\langle3\rangle[/math];
Шаг 9: [math]aba[/math] — есть в таблице; [math]abac[/math] — нет. В таблицу: [math]\langle12\rangle[/math] [math]abac[/math]. В поток: [math]\langle9\rangle[/math];
Шаг 10: [math]ca[/math] — есть в таблице; [math]cab[/math] — нет. В таблицу: [math]\langle13\rangle[/math] [math]cab[/math]. В поток: [math]\langle8\rangle[/math];
Шаг 11: [math]ba[/math] — есть в таблице; [math]bae[/math] — нет. В таблицу: [math]\langle14\rangle[/math] [math]bae[/math]. В поток: [math]\langle6\rangle[/math];
Шаг 12: И, наконец последняя строка [math]e[/math], за ней идет конец сообщения, поэтому мы просто выводим в поток [math]\langle4\rangle[/math].

Текущая строка	Текущий символ	Следующий символ	Вывод		Словарь
Текущая строка	Текущий символ	Следующий символ	Код	Биты	Словарь
ab	a	b	0	000	5:	ab
ba	b	a	1	001	6:	ba
ac	a	c	0	000	7:	ac
ca	c	a	2	010	8:	ca
ab	a	b	-	-	-	-
aba	b	a	5	101	9:	aba
ad	a	d	0	000	10:	ad
da	d	a	3	011	11:	da
ab	a	b	-	-	-	-
aba	b	a	-	-	-	-
abac	a	c	9	1001	12:	abac
ca	c	a	-	-	-	-
cab	a	b	8	1000	13:	cab
ba	b	a	-	-	-	-
bae	a	e	6	0110	14:	bae
e	e	-	4	0100	-	-

Итак, мы получаем закодированное сообщение [math]0 1 0 2 5 0 3 9 8 6 4[/math].

Каждый символ исходного сообщения был закодирован группой из трех бит, сообщение содержало 16 символов, следовательно длина сообщения составляла [math]3 * 16 = 48[/math] бит.

Закодированное же сообщение так же сначала кодировалось трехбитными группами, а про появлении в словаре восьмого слова - четырехбитными, итого длина сообщения составила [math]7 * 3 + 4 * 4 = 37[/math] бит, что на [math]11[/math] бит короче исходного.

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

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

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

Данные		На выходе	Новая запись
Биты	Код	На выходе	Полная		Частичная
000	0	a	-	-	5:	a?
001	1	b	5:	ab	6:	b?
000	0	a	6:	ba	7:	a?
010	2	c	7:	ac	8:	c?
101	5	ab	8:	ca	9:	ab?
000	0	a	9:	aba	10:	a?
011	3	d	10:	ad	11:	d?
1001	9	aba	11:	da	12:	aba?
1000	8	ca	12:	abac	13:	ca?
0110	6	ba	13:	cab	14:	ba?
0100	4	e	14:	bae	-	-

Примечание

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые файлы, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых символов, например [math]aaaaaa[/math] … или [math]303030[/math] … и т. п. Их непосредственное сжатие будет генерировать выходной код [math]005[/math] и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия?

Оказывается, это возможно, если оговорить некоторые действия:

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

Итак, кодировщик заносит первую [math]a[/math] в строку, ищет и находит [math]a[/math] в словаре. Добавляет в строку следующую [math]a[/math], находит, что [math]aa[/math] нет в словаре. Тогда он добавляет запись [math]\langle5\rangle[/math]: [math]aa[/math] в словарь и выводит метку [math]\langle0\rangle[/math] ([math]a[/math]) в выходной поток.
Далее строка инициализируется второй [math]a[/math], то есть принимает вид [math]a?[/math] вводится третья [math]a[/math], строка вновь равна [math]aa[/math], которая теперь имеется в словаре.
Если появляется четвертая [math]a[/math], то строка [math]aa?[/math] равна [math]aaa[/math], которой нет в словаре. Словарь пополняется этой строкой, а на выход идет метка [math]\langle5\rangle[/math] ([math]aa[/math]).
После этого строка инициализируется третьей [math]a[/math], и т.д. и т.п. Дальнейший процесс вполне ясен.

Текущая строка	Текущий символ	Следующий символ	Вывод		Словарь
Текущая строка	Текущий символ	Следующий символ	Код	Биты	Словарь
aa	a	a	0	000	5:	aa
aa	a	a	-	-	-	-
aaa	a	a	5	101	6:	aaa
a	a	a	-	-	-	-
aa	a	a	-	-	-	-
aaa	a	-	6	110	-	-

В результате на выходе получаем последовательность [math]056 [/math]..., которая короче прямого кодирования стандартным методом LZW.

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это [math]\langle0\rangle[/math], которому соответствует символ [math]a[/math]. Затем читает код [math]\langle5\rangle[/math], но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть [math]a[/math]. Поэтому он добавит в свою таблицу строку [math]aa[/math] с кодом [math]\langle5\rangle[/math], а в выходной поток поместит [math]aa[/math]. И так может быть раскодирована вся цепочка кодов.

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

Преимущества алгоритма LZW

Алгоритм является однопроходным.

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