Если КОНЕЦ_СООВЩЕНИЯ

Выдать ход »;

ВЫХОД;

Конец Коли Коли фрааа »К уже есть в словаре,

Заменить х на код фравы wK;

Повторить Шаг алгоритма;

Иначе

Выдать ход w;

Добавить wK в словарь ;

Повторить Шаг алгоритма;

Конец Если;

Пример работы кодера LZW при преобразовании трехсимвольного алфавита приведен в табл. 8.6 и 8.7.

Описанный алгоритм кодера не оптимизирует выбор фразы для добавления в словарь или разбор сообщения. Однако в силу его простоты он может быть эффективно использован.

Таблица 8.6. Работа кодера LZW на примере трехсимвольного алфавита (а, б, в)

Символ	wK	Выход	Добавление в словарь (фраза — позиция)
а
			16(4)
а	2а		2а(5)

в	4в		4в(6)
б			36(7)
а	2а
			56(8)
а	2а

а	8а		8а(9)
а	1а		1а(10)
а	1a
а	10a		10a (11)
а	1a
а	10a		'•
а	11a		11a (12)

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

Таблица 8.7. Словарь, построенный кодером LZW, для примера из табл. 8.6

Фразы, добавленные в словарь при инициализации
а

в
Фразы, добавленные пр	и разборе сообщения

2а
4в


8а
la
10a
11a

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

Алгоритм декодирования LZW описывается следующим образом:

КОД 8 Прочитать первый ход сообщения( );

ПредмдущийКОД = КОД;

Выдать символ К, у которого код(К) == КОД;

Последний символ = К;

Следующий ход:

КОД = Прочитать очередной код сообщения( );

ВходнойКОД = КОД ;

Если КОНЕЦ_СООБЩЕНИЯ ВЫХОД;

Конец Если;

Если Неизвестен(КОД) // Обработка исключительной //ситуации

Видать(ПоследнийСимаол) КОД = ПредыдущийКОД

ВходнойКОД = код(ПредыдущийКОД, ПоследнийСимвол) Конец Если;

Следующий символ:

Если КОД == ход(wK) В СТЕК (К);

КОД = код(к) ;

Повторить Следующий символ;

Иначе если КОД == код(К) Выдать К;

По еле днийСимвол в JC;

Пока стек не пуст

Выдать (ИЗ_СТЕКА( )) ;

Конец Пока;

Добавить в словарь (ПредыдущийКОД, К);

Предыдущий КОД а Входной КОД;

Повторить СледующийКОД;

Конец Если;

Обычно декодирование LZW намного быстрее процесса кодирования. Автор LZW Терри Уэлч в свое время сумел запатентовать свой алгоритм в США. В настоящее время патент принадлежит компании Unisys. Алгоритм LZW определяется как часть стандарта ITU-T V.42bis, но Unisis установила жесткие условия лицензирования алгоритма для производителей модемов.