Алгоритм LZW. Описание и характеристики

это универсальный алгоритм сжатия данных без потерь, созданный Абрахамом Лемпелем (англ. Abraham L empel), Якобом Зивом (англ. Jacob Z iv) и Терри Велчем (англ. Terry W elch).

Данный алгоритм при сжатии (кодировании) динамически создаёт таблицу преобразования строк: определённым последовательностям символов (словам) ставятся в соответствие группы бит фиксированной длины (обычно 12-битные). Таблица инициализируется всеми 1-символьными строками (в случае 8-битных символов — это 256 записей). По мере кодирования, алгоритм просматривает текст символ за символом, и сохраняет каждую новую, уникальную 2-символьную строку в таблицу в виде пары код/символ, где код ссылается на соответствующий первый символ. После того как новая 2-символьная строка сохранена в таблице, на выход передаётся код первого символа. Когда на входе читается очередной символ, для него по таблице находится уже встречавшаяся строка максимальной длины, после чего в таблице сохраняется код этой строки со следующим символом на входе; на выход выдаётся код этой строки, а следующий символ используется в качестве начала следующей строки.

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

Пример:

Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, 55. Тогда, согласно изложенному выше алгоритму, мы поместим в выходной поток сначала код очистки <256>, потом добавим к изначально пустой строке “45” и проверим, есть ли строка “45” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “45” есть в таблице. Далее мы читаем следующий символ 55 из входного потока и проверяем, есть ли строка “45, 55” в таблице. Такой строки в таблице пока нет. Мы заносим в таблицу строку “45, 55” (с первым свободным кодом 258) и записываем в поток код <45>. Можно коротко представить архивацию так:

· “45” — есть в таблице;

· “45, 55” — нет. Добавляем в таблицу <258>“45, 55”. В поток: <45>;

· “55, 55” — нет. В таблицу: <259>“55, 55”. В поток: <55>;

· “55, 151” — нет. В таблицу: <260>“55, 151”. В поток: <55>;

· “151, 55” — нет. В таблицу: <261>“151, 55”. В поток: <151>;

· “55, 55” — есть в таблице;

· “55, 55, 55” — нет. В таблицу: “55, 55, 55” <262>. В поток: <259>;

Последовательность кодов для данного примера, попадающих в выходной поток:

<256>, <45>, <55>, <55>, <151>, <259>.

LZW реализован в форматах GIF и TIFF.

Характеристики алгоритма LZW:

- Коэффициенты компрессии: Примерно 1000, 4, 5/7 (Лучший, средний, худший коэффициенты). Сжатие в 1000 раз достигается только на одноцветных изображениях размером кратным примерно 7 Мб.

- Класс изображений: Ориентирован LZW на 8-битные изображения,

построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

- Симметричность: Почти симметричен, при условии оптимальной

реализации операции поиска строки в таблице.

- Характерные особенности: Ситуация, когда алгоритм увеличивает

изображение, встречается крайне редко. LZW универсален — именно его варианты

используются в обычных архиваторах.