2.4. LZW

Это весьма популярный вариант алгоритма LZ78, который был разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя, и нет надобности дополнительно хранить код символа, как в алгоритмах LZ77 и LZ78.

(Алгоритм LZW запатентован и для его использования необходима лицензия. Издание патентов для программного обеспечения обсуждается в [Salomon 00].)

Метод LZW накапливает поступающие на вход символы в строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «sir_sid_eastman_easily_teases_sea_sick_seals». Получаем следующие шаги.

I	В словаре?	Новая запись	Выход	I	В словаре?	Новая запись	Выход
s	да			y	да
si	нет	256-si	115 (s)	y_	нет	274-у_	121 (у)
i	да			_	да
ir	нет	257-ir	105 (i)	_t	нет	275-_t	32 (_)
r	да			t	да
r_	нет	258-r_	114 (r)	te	нет	276-te	116 (t)
_	да			e	да
_s	нет	259-_s	32 (_)	ea	да
s	да			eas	нет	277-eas	263 (ea)
si	да			s	да
sid	нет	260-sid	256 (si)	se	нет	278-se	115 (s)
d	да			e	да
d_	нет	261-d_	100 (d)	es	нет	279-es	101 (e)
_	да			s	да
_e	нет	262-_e	32 (_)	s_	нет	280-s_	115 (s)
e	да			_	да
ea	нет	263-ea	101 (e)	_s	да
a	да			_se	нет	281-_se	259 (_s)
as	нет	264-as	97 (a)	e	да
s	да			ea	да
st	нет	265-st	115 (s)	ea_	нет	282-ea_	263 (ea)
t	да			_	да
tm	нет	266-tm	116 (t)	_s	да
m	да			_si	нет	283-_si	259 (_s)
ma	нет	267-ma	109 (m)	i	да
a	да			ic	нет	284-ic	105 (i)
аn	нет	268-an	97 (a)	с	да
n	да			ck	нет	285-ck	99 (c)
n_	нет	269-n_	110 (n)	k	да
_	да			k_	нет	286-k_	107 (k)
_e	да			_	да
_ea	нет	270-_ea	262 (_e)	_s	да
a	да			_se	да
as	да			_sea	нет	287-_sea	281 (_se)
asi	нет	271-asi	264 (as)	a	да
i	да			al	нет	288-al	97 (a)
il	нет	272-il	105 (i)	l	да
l	да			ls	нет	289-ls	108 (l)
ly	нет	273-ly	108 (l)	s	да		115 (s)
				s ,eof	нет

Табл. 2.6. Кодирование строки «sir_sid_eastman_...»

0. Инициализируем словарь записями от 0 до 255 всеми 8-битовыми символами.

1. Первый входной символ s обнаруживается в словаре под номером 115 (это его код ASCII). Следующий входной символ i, но строки si нет в словаре. Кодер делает следующее: (1) он выдает на выход ссылку 115, (2) сохраняет si в следующей доступной позиции словаря (запись номер 256) и (3) инициализирует I строкой i.

2. На вход поступает символ r, но строки ir нет в словаре. Кодер (1) записывает на выход 105 (ASCII код i), (2) сохраняет в словаре ir (запись 257) и (3) инициализирует I строкой r.

0	NULL	110	n	262	_e	276	te
1	S0H	…		263	ea	277	eas
…		115	s	264	as	278	se
32	SP	116	t	265	st	279	es
…		…		266	tm	280	s_
97	а	121	У	267	ma	281	_se
98	b			268	аn	282	ea_
99	с	255	255	269	n_	283	_si
100	d	256	si	270	_ea	28-1	ic
101	е	257	ir	271	asi	285	ck
…		258	r_	272	il	286	k_
107	k	259	_s	273	ly	287	_sea
108	l	260	sid	274	y_	288	al
109	m	261	d_	275	_t	289	ls

Табл. 2.7. Словарь LZW.

Табл. 2.6 суммирует все шаги процесса. В табл. 2.7 приведены некоторые исходные записи из словаря LZW плюс записи, добавленные в процессе кодирования данной строки. Полный выходной файл имеет следующий вид (входят только числа, но не символы в скобках):

115 (s), 105 (i), 114 (r), 32 (_), 256 (si), 100 (d), 32 (_), 101 (е), 97 (а), 115 (s), 116 (t), 109 (m), 97 (a), 110 (n), 262 (_e), 264 (as), 105 (i), 108 (1), 121 (y), 32 (_), 116 (t), 263 (ea), 115 (s), 101 (e), 115 (s), 259 (_s), 263 (ea), 259 (_s), 105 (i), 99 (c), 107 (k), 280 (_se), 97 (a), 108 (1), 115 (s), eof.

На рис. 2.8 приведена запись этого алгоритма на псевдокоде. Через  обозначается пустая строка, а через  - конкатенация (соединение) двух строк  и .

Инструкция алгоритма «добавить  в словарь» будет обсуждаться особо. Ясно, что на практике словарь может переполниться, поэтому эта инструкция должна также содержать тест на переполнение словаря и некоторые действия при обнаружении переполнения.

Поскольку первые 256 записей занесены в словарь в самом начале, указатели на словарь должны быть длиннее 8 бит. В простейшей реализации указатели занимают 16 бит, что допускает 64К записей в словаре (). Такой словарь, конечно, быстро переполнится. Такая же проблема возникает при реализации алгоритма LZ78, и любое решение, допустимое для LZ78, годится и для LZW. Другое интересное свойство этого алгоритма заключается в том, что строки в словаре становятся длиннее на один символ на каждом шаге. Это означает, что требуется много времени для появления длинных строк в словаре, а значит и эффект сжатия будет проявляться медленно. Можно сказать, что LZW медленно приспосабливается к входным данным.

Рис. 2.8. Алгоритм LZW.

Пример: Применим алгоритм LZW для кодирования строки символов «alf_eats_alfalf а». Последовательность шагов отображена в табл. 2.9. Кодер выдает на выход файл:

97 (а), 108 (1), 102 (f), 32 (_), 101 (е), 97 (а), 116 (t), 115 (s), 32 (_), 256 (al), 102 (f), 265 (alf), 97 (a),

а в словаре появляются следующие новые записи:

(256: al), (257: lf), (258: f_), (259: _е), (260: ea), (261: at), (262: ts), (263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).

Пример: Проанализируем сжатие строки «аааа...» алгоритмом LZW. Кодер заносит первую «а» в I, ищет и находит а в словаре. Добавляет в I следующую а, находит, что строки Iх (=аа) нет в словаре. Тогда он добавляет запись 256: аа в словарь и выводит метку 97 (а) в выходной файл. Переменная I инициализируется второй «а», вводится третья «а», Iх вновь равна аа, которая теперь имеется в словаре. I становится аа, появляется четвертая «а». Строка Iх равна ааа, которых нет в словаре. Словарь пополняется этой строкой, а на выход идет метка 256 (аа). I инициализируется третьей «а», и т.д. и т.п. Дальнейший процесс вполне ясен.

В результате строки а, аа, ааа, аааа... добавляются в словарь в позиции 256, 257, 258, ..., а на выход подается последовательность

97 (а), 256 (аа), 257 (ааа), 258 (аааа), ....

Значит, выходной файл состоит из указателей на все более и более длинные последовательности символов а, и к указателей обозначают строку, длина которой равна .

I	В словаре ?	Новая запись	Выход	I	В словаре?	Новая запись	Выход
а	да			s_	нет	263-s_	115 (s)
al	нет	256-а1	97 (а)	_	да
1	да			_а	нет	264-_а	32 (_)
lf	нет	257-lf	108 (1)	а	да
f	да			al	да
f_	нет	258-f_	102 (f)	alf	нет	265-alf	256 (al)
_	да			f	да
_e	нет	259-_е	32 (w)	fa	нет	266-fa	102 (f)
e	да			a	да
ea	нет	260-еа	101 (е)	al	да
a	да			alf	да
at	нет	261-at	97 (а)	alfa	нет	267-alfa	265 (alf)
t	да			a	да
ts	нет	262-ts	116 (t)	a,eof	нет		97 (a)
s	да

Табл. 2.9. Кодирование LZVV для «alf_eats_alfalfa»

Предположим, что входной файл состоит из 1 миллиона символов а. Мы можем найти длину сжатого файла, решив квадратное уравнение  относительно неизвестной . Решение будет . Выходит, что файл длиной 8 миллионов бит будет сжат в 1414 указателей длины не менее 9 бит (а на самом деле, 16 бит). Фактор сжатия или  или .

Результат потрясающий, но такие файлы попадаются весьма редко (заметим, что этот конкретный файл можно сжать, просто записав в выходной файл «1000000 а» без использования LZW).