5.4.2 Алгоритм lzw

Алгоритм кодирования последовательности неодинаковых символов.

Предложен Дж. Зивом (J.Ziv), А. Лемпелом (A. Lempel) 1977 г., доработан Терри А. Велчем (Terry A.Welch) 1984 г.

Основан на кодировании подстроки в строке.

Создается таблица строк:

Таблица 5.17 – Проинициализированная таблица строк

Элемент	Префикс	Суффикс
0 1 2 … 255	-1 -1 -1 … -1	0 1 2 … 255

Из однобайтных значений в столбце “Суффикс” алгоритм по мере прохождения файла строит многобайтовые образцы.

Пример.

Пусть обрабатывается строка: Going, going, gone!

После инициализации таблицы строк программа сжати читает букву “G” (код 71) из входного файла и записывает 71 в выходной файл.

Затем читается “o” (код 111) и ищется в таблице строк элемент с префиксом 71 и суффиксом 111. Так как такого элемента нет, то он добавляется в таблицу и выводится суффикс 111 в выходной файл. Послде этого суффикс 111 переносится в префикс и читается новое значение суяяикса из входного файла.

Следующая буква “i” (код 105) становится новым суффиксом. Ищется элемент с префиксом 111 и суффиксом 105. Так как такого элемента нет, то он добавляется в таблицу, а суффикс - в выходной файл. Теперь таблица строк содержит 258 элементов, а выходной файл содержит значения 71, 11, 105:

Таблица 5.18 – Таблица из 258 элементов

Элемент	Префикс	Суффикс	Строка
0 1 2 … 255 256 257	-1 -1 -1 … -1 71 111	0 1 2 … 255 111 105	Go oi

Программа будет добалять двух симольные последовательности в балицу, пока не дойдет до 9 – й буквы (“o” во втором слове going ). В этой точке балица содержит 264 элемента:

Таблица 5.19 – Таблица из 264 элементов

Элемент	Префикс	Суффикс	Строка
0 1 2 … 255 256 257 258 259 260 261 262 263	-1 -1 -1 … -1 71 111 105 110 103 44 32 103	0 1 2 … 255 111 105 110 103 44 32 103 111	Go oi in ng g, ,# #g go

Суффикс 111 (из элемента 263) перемещается в префикс и читается новый суффикс “i” (код 105) из входного файла. При поиске элемента с префиксом 111 и суффиксом 105 находится совпадение в элементе 257. Поэтому программа делает сжатие:

- значение 257 назначается префиксу и читается новый суффикс “n” (код 110) из входного файла.

Не найдя в таблице строк элемента с префиксом 257 и суффиксом 110, программа добавляет его в таблицу.

Окончательная таблица будет иметь следующий вид:

Таблица 5.20 – Окончательная таблица после обработки всей строки

Элемент	Префикс	Суффикс	Строка
0 1 2 … 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270	-1 -1 -1 … -1 71 111 105 110 103 44 32 103 257 259 261 263 110 101 33	0 1 2 … 255 111 105 110 103 44 32 103 111 110 44 103 110 101 33 -1	Go oi in ng g, ,# #g go oin ng, ,#g gon ne e! !

Чтобы получить выходной файл нужно просмотреть содрежимое столбца “Префикс”, начиная с элемента 256 и заканчивая последним.

Наш выходной файл будет содержать 15 – ть значений вместо 20 – ти.

Достоинство LZW:

так как при декодировании программа строит таблицу строк идентичную таблице сжатия, то ее хранить отдельно не нужно.