Алгоритм LZW

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

Пример работы кодера LZW при преобразовании трехсимвольного алфавита приведен в табл. 8.6 и 8.7.
Описанный алгоритм кодера не оптимизирует выбор фразы для добавления в словарь или разбор сообщения. Однако в силу его простоты он может быть эффективно использован.
Таблица 8.6. Работа кодера LZW на примере трехсимвольного алфавита (а, б, в)

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

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