2.4. LZW

Это весьма популярный вариант алгоритма LZ78, который был разработан Терри Уэлчем (Terry Welch) в 1984 ([Welch 84] и [Phillips 92]). Его главной особенностью является удаление второго поля из метки. Метка LZW состоит только из указателя на место в словаре. Для лучшего понимания алгоритма LZW мы временно забудем, что словарь является деревом и будем предполагать, что словарь - это просто массив, состоящий из строк разной длины. Метод LZW начинается инициализацией словаря всеми символами исходного алфавита. В общем случае 8-битного алфавита, первые 256 записей (отдельные символы с номерами от 0 до 255) заносятся в словарь до поступления сжимаемых данных. Поскольку словарь уже частично заполнен, первые поступившие символы всегда будут обнаружены в словаре, поэтому метка может состоять всего лишь из указателя, и нет надобности дополнительно хранить код символа, как в алгоритмах LZ77 и LZ78.

(Алгоритм LZW запатентован и для его использования необходима лицензия. Издание патентов для программного обеспечения обсуждается в [Salomon 00].)

Метод LZW накапливает поступающие на вход символы в строке I. После каждого нового символа, добавленного в строку I, кодер ищет I в словаре. Если строка обнаружена, то процесс удлинения I продолжается. В некоторый момент добавление нового символа х приводит к необнаружению строки Iх (символ х был добавлен к I). Тогда кодер (1) записывает в выходной файл указатель в словаре на строку I, (2) сохраняет строку Iх (которая теперь будет называться фразой) в словаре на следующей допустимой позиции и (3) инициализирует (присваивает) строке I новое значение х. Чтобы проиллюстрировать процесс кодирования, мы еще раз воспользуемся последовательностью «sir_sid_eastman_easily_teases_sea_sick_seals». Получаем следующие шаги.

Табл. 2.6. Кодирование строки «sir_sid_eastman_...»

0. Инициализируем словарь записями от 0 до 255 всеми 8-битовыми символами.

1. Первый входной символ s обнаруживается в словаре под номером 115 (это его код ASCII). Следующий входной символ i, но строки si нет в словаре. Кодер делает следующее: (1) он выдает на выход ссылку 115, (2) сохраняет si в следующей доступной позиции словаря (запись номер 256) и (3) инициализирует I строкой i.

2. На вход поступает символ r, но строки ir нет в словаре. Кодер (1) записывает на выход 105 (ASCII код i), (2) сохраняет в словаре ir (запись 257) и (3) инициализирует I строкой r.

Табл. 2.7. Словарь LZW.

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

115 (s), 105 (i), 114 (r), 32 (_), 256 (si), 100 (d), 32 (_), 101 (е), 97 (а), 115 (s), 116 (t), 109 (m), 97 (a), 110 (n), 262 (_e), 264 (as), 105 (i), 108 (1), 121 (y), 32 (_), 116 (t), 263 (ea), 115 (s), 101 (e), 115 (s), 259 (_s), 263 (ea), 259 (_s), 105 (i), 99 (c), 107 (k), 280 (_se), 97 (a), 108 (1), 115 (s), eof.

На рис. 2.8 приведена запись этого алгоритма на псевдокоде. Через  обозначается пустая строка, а через  - конкатенация (соединение) двух строк  и .

Инструкция алгоритма «добавить  в словарь» будет обсуждаться особо. Ясно, что на практике словарь может переполниться, поэтому эта инструкция должна также содержать тест на переполнение словаря и некоторые действия при обнаружении переполнения.

Поскольку первые 256 записей занесены в словарь в самом начале, указатели на словарь должны быть длиннее 8 бит. В простейшей реализации указатели занимают 16 бит, что допускает 64К записей в словаре (). Такой словарь, конечно, быстро переполнится. Такая же проблема возникает при реализации алгоритма LZ78, и любое решение, допустимое для LZ78, годится и для LZW. Другое интересное свойство этого алгоритма заключается в том, что строки в словаре становятся длиннее на один символ на каждом шаге. Это означает, что требуется много времени для появления длинных строк в словаре, а значит и эффект сжатия будет проявляться медленно. Можно сказать, что LZW медленно приспосабливается к входным данным.

Рис. 2.8. Алгоритм LZW.

Пример: Применим алгоритм LZW для кодирования строки символов «alf_eats_alfalf а». Последовательность шагов отображена в табл. 2.9. Кодер выдает на выход файл:

97 (а), 108 (1), 102 (f), 32 (_), 101 (е), 97 (а), 116 (t), 115 (s), 32 (_), 256 (al), 102 (f), 265 (alf), 97 (a),

а в словаре появляются следующие новые записи:

(256: al), (257: lf), (258: f_), (259: _е), (260: ea), (261: at), (262: ts), (263: s_), (264: _a), (265: alf), (266: fa), (267: alfa).

Пример: Проанализируем сжатие строки «аааа...» алгоритмом LZW. Кодер заносит первую «а» в I, ищет и находит а в словаре. Добавляет в I следующую а, находит, что строки Iх (=аа) нет в словаре. Тогда он добавляет запись 256: аа в словарь и выводит метку 97 (а) в выходной файл. Переменная I инициализируется второй «а», вводится третья «а», Iх вновь равна аа, которая теперь имеется в словаре. I становится аа, появляется четвертая «а». Строка Iх равна ааа, которых нет в словаре. Словарь пополняется этой строкой, а на выход идет метка 256 (аа). I инициализируется третьей «а», и т.д. и т.п. Дальнейший процесс вполне ясен.

В результате строки а, аа, ааа, аааа... добавляются в словарь в позиции 256, 257, 258, ..., а на выход подается последовательность

97 (а), 256 (аа), 257 (ааа), 258 (аааа), ....

Значит, выходной файл состоит из указателей на все более и более длинные последовательности символов а, и к указателей обозначают строку, длина которой равна .

Табл. 2.9. Кодирование LZVV для «alf_eats_alfalfa»

Предположим, что входной файл состоит из 1 миллиона символов а. Мы можем найти длину сжатого файла, решив квадратное уравнение  относительно неизвестной . Решение будет . Выходит, что файл длиной 8 миллионов бит будет сжат в 1414 указателей длины не менее 9 бит (а на самом деле, 16 бит). Фактор сжатия или  или .

Результат потрясающий, но такие файлы попадаются весьма редко (заметим, что этот конкретный файл можно сжать, просто записав в выходной файл «1000000 а» без использования LZW).