Алгоритм lzw

Еще один распространенный алгоритм кодирования получил название LZW — по первым буквам фамилий его разработчиков: Lempel, Ziv и Welch (алгоритм Лемпеля—Зива—Велча).

Алгоритм был опубликован Велчем в 1984 году в качестве улучшенной реализации алгоритма LZ78, представленного Лемпелем и Зивом в 1978 году, и был запатентован фирмой Sperry.

Алгоритм LZW использует идею расширения информационного алфавита. Вместо традиционного 8-битного представления 256 символов ASCII-таблицы обычно используется 12-битное, что позволяет определить таблицу на 4096 записей.

Идея алгоритма LZW заключается в том, чтобы заменять строки символов некоторыми кодами, для чего и используется таблица на 4096 записей. Это делается без какого-либо анализа входной последовательности символов. При добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда строка символов заменяется кодом. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов, то есть значения кодов 0-255 соответствуют отдельным байтам. Остальные коды (256-4095) соответствуют строкам обрабатываемым алгоритмом.

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

Рассмотрим в качестве примера входную последовательность ABCABCABCABCABCABC#. Маркер # будет символизировать конец исходного сообщения.

Для простоты будем считать, что используются только заглавные буквы английского алфавита (26 букв) и маркер # конца сообщения. Соответственно для перебора всех букв нашего алфавита достаточно 5 бит (25 = 32). Теперь предположим, что символы нашего алфавита кодируются по номеру буквы в алфавите от 1 до 26 следующим образом:

#=00000 (0₁₀)

A=00001 (1₁₀)

B=00010 (2₁₀)

C=00011 (3₁₀)

Последний символ Z будет иметь код 11010 (2610).

Отметим, что когда в нашей таблице кодов появится символ с кодом 32, то алгоритм должен перейти к 6-битным группам.

В нашем примере первый символ — это «A». Поскольку при инициализации в таблицу были занесены все односимвольные строки, то строка, соответствующая символу «A», в таблице есть (код символа 00001).

Далее считывается следующий символ «B» из входного потока и проверяется, есть ли строка «AB» в таблице. Такой строки в таблице пока нет. Поэтому данная строка заносится в таблицу с первым свободным кодом 100 000 (3210), а в выходной поток записывается код 00001, соответствующий предыдущему символу («A»).

Далее начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть с символа «B». Поскольку символ «B» есть в таблице, то считываем следующий символ «C». Строки «BC» в таблице нет, поэтому заносим эту строку в таблицу под кодом 100 001 (3310), а в выходной поток записывается код 00010, соответствующий предыдущему символу ( «В»).

Далее начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть с символа «С». Поскольку символ «С» есть в таблице, то считываем следующий символ «A». Строки «CA» нет в таблице, поэтому заносим эту строку в таблицу под кодом 100 010 (3410), а в выходной поток записывается код 00011, соответствующий предыдущему символу (символу «C»).

Затем начинаем с символа, которым оканчивается последняя занесенная в таблицу строка, то есть, с символа «A». Поскольку символ «A» есть в таблице, то считываем следующий символ «B». Строка «AB» уже есть в таблице, поэтому считываем следующий символ «C». Строки «ABC» нет в таблице, поэтому заносим эту строку в таблицу под кодом 100 011 (3510), а в выходной поток записывается код 100 000, соответствующий предыдущему символу в таблице (строке «AB»).

Далее начинаем с символа «C». Поскольку он уже есть в таблице, считываем следующий символ «A». Строка «CA» уже есть в таблице, поэтому считываем следующий символ «B». Строки «CAB» нет в таблице, поэтому заносим ее туда, а в выходной поток записываем код 100 010, соответствующий строке «CA».

Продолжая подобным образом, построим таблицу кодов для всего сообщения ABCABCABCABCABCABC# (табл. 1).

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

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