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

Выдать ход »;

Иначе

Выдать ход w;

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

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

Конец Если;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

КОД = код(к) ;

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

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

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

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

Конец Пока;

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