Алгоритм LZW

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

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

Пример:

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

· – есть в таблице;

· – нет. Добавляем в таблицу . В поток: ;

· – нет. В таблицу: . В поток: ;

· – нет. В таблицу: . В поток: ;

· – нет. В таблицу: . В поток: ;

· – есть в таблице;

· – нет. В таблицу: . В поток: ;

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

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

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

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

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

Класс изображений: Ориентирован LZW на -битные изображения, построенные на компьютере. Сжимает за счет одинаковых подцепочек в потоке.

Симметричность: Почти симметричен, при условии оптимальной реализации операции поиска строки в таблице.

Характерные особенности: Ситуация, когда алгоритм увеличивает изображение, встречается крайне редко. LZW универсален – именно его варианты используются в обычных архиваторах.