Алгоритм сжатия LZW

Данный алгоритм, созданный в 1984 году Терри Уэлчем, является модификацией метода сжатия LZ, который впервые разработали А.Лемпель и Я.Зив в 1977 году. Первые буквы фамилий ученых, принявших участие в создании алгоритма, дали ему название LZW.

LZW относится к группе словарных методов сжатия, которые разбивают входной поток данных на слова. Словом называется последовательность символов (байт). Совокупность всех слов называется словарем, в котором каждое слово содержится под своим номером (индексом, ссылкой). В выходной поток записываются только ссылки. Эффект сжатия возникает за счет того, что длина ссылок, как правило, меньше и длины слов. Словарь формируется итеративно, по ходу работы алгоритма сжатия/распаковки.

Алгоритм LZW является симметричным, причем основное время затрачивается на составление словаря. Этот метод особенно хорош для сжатия изображений с пиксельной глубиной до 8 бит/пиксель, содержащих много коротких пиксельных групп. Для таких изображений LZW обычно более эффективен, чем алгоритм группового кодирования RLE, причем эффективность сжатия тем выше, чем длиннее поток входных данных, т.е. чем больше изображение.

Рассмотрим подробнее схему работы алгоритма. Априорно считается, что словарь уже содержит N однобуквенных слов, где N – количество символов в алфавите. Алфавитом называется множество всех возможных символов, которые могут встретиться во входном потоке данных. Выбираем очередной символ из входного потока: если в словаре есть слова, начинающиеся с него, то выбираем следующий символ. Так повторяем до тех пор, пока не окажется, что образовавшегося нет в словаре. Тогда набранная комбинация представима в виде «W + c», где W - слово из словаря, с – отличающийся символ. В выходной (сжатый) поток записывается только номер слова W, а набор новой комбинации начинается с символа с.

Ниже представлено подробное описание алгоритма LZW.

[1] Инициализация словаря символами алфавита;

[2] Слово W = <пусто>;

[3] c = <следующий символ в потоке данных>;

[4] Входит ли слово Wc в словарь?

Да: W = Wc;

Переход к шагу [3].

Нет: Добавить Wс в словарь;

Записать номер слова W в выходной поток.

[5] Есть ли ещё символы во входном потоке?

Да: Переход к шагу [3];