Алгоритм LZW

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

Алгоритм LZW построен вокруг так называемой таблицы фраз (словаря), которая отображает строки символов сжимаемого сообщения в коды фиксированной длины, равные 12 бит. Таблица обладает свойством предшествования, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже содержится в словаре.

Алгоритм работы кодера LZW следующий:

Проинициализировать словарь односимвольными фразами, соответствующими символам входного алфавита;

Прочитать первый символ сообщения в текущую фразу *г;

Шаг алгоритма:

Прочитать очередной символ сообщения К:

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

Выдать ход »;

ВЫХОД;

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

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

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

Иначе

Выдать ход w;

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

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

Конец Если;

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

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

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

Символ	wK	Выход	Добавление в словарь (фраза — позиция)
а	1
6	6	1	16(4)
а	2а	2	2а(5)
6	16
в	4в	4	4в(6)
б	36	3	36(7)
а	2а
6	56	5	56(8)
а	2а
6	56
а	8а	8	8а(9)
а	1а	1	1а(10)
а	1a
а	10a	10	10a (11)
а	1a
а	10a		'•
а	11a	11	11a (12)
		1

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

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

Фразы, добавленные в словарь при инициализации
а	1
6	2
в	3
Фразы, добавленные пр	и разборе сообщения
16	4
2а	5
4в	6
36	7
56	8
8а	9
la	10
10a	11
11a	12

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

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

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

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

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

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

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

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

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

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

Конец Если;

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

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

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

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

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

КОД = код(к) ;

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

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

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

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

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

Конец Пока;

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

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

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

Конец Если;

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