Алгоритм LZW

Определение:

Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь

Он был создан Абрахамом Лемпелем(Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году.

Применение

LZW отчасти используется во многих популярных программах сжатия данных (ZIP, ARJ, LHA).

Этот метод позволяет достичь одну из наилучших степеней сжатия среди других существующих методов сжатия графических данных, при полном отсутствии потерь или искажений в исходных файлах. В настоящее время испольуется в файлах формата TIFF, PDF, GIF, PostScript и других.

Описание

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

Например, если сжимают байтовые данные (текст), то строк в таблице окажется 256 (от "0" до "255"). Если используется 10-битный код, то под коды для строк остаются значения в диапазоне от 256 до 1023. Новые строки формируют таблицу последовательно, т. е. можно считать индекс строки ее кодом.

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

Алгоритм

1. Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
2. Считать очередной символ K из кодируемого сообщения.
3. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе
4. Если фраза ωK уже есть в словаре, присвоить входной фразе значение ωK и перейти к Шагу 2, иначе выдать код ω, добавить ωK в словарь, присвоить входной фразе значение K и перейти к Шагу 2.

Конец

Пример

Символ	Битовый код
0	00
1	01
2	10
3	11
...	...
31	11111

Рассмотрим пример сжатия и декодирования изображения.

Первой вещью, которую мы делаем при LZW-сжатии, является инициализация нашей цепочки символов. Чтобы сделать это, нам необходимо выбрать код размера (количество бит) и знать, сколько возможных значений могут принимать наши символы. Давайте положим код размера равным 12 битам, что означает возможность запоминания 4096 элементов в нашей таблице цепочек. Давайте также предположим, что мы имеем 32 возможных различных символа. ( Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела ) Чтобы инициализировать таблицу, мы установим соответствие кода 0 символу 0, кода 1 символу 1, и т.д., до кода 31 и символа 31. На самом деле мы указали, что каждый код от 0 до 31 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством.

Кодирование

Пусть мы сжимаем последовательность 15, 25, 25, 17, 25, 25, 25.

Тогда, согласно изложенному выше алгоритму, мы добавим к изначально пустой строке “15” и проверим, есть ли строка “15” в таблице. Поскольку мы при инициализации занесли в таблицу все строки из одного символа, то строка “15” есть в таблице.
Далее мы читаем следующий символ 25 из входного потока и проверяем, есть ли строка “15, 25” в таблице. Такой строки в таблице пока нет.
Добавляем в таблицу <32> “15, 25”. В поток: <15>;
“25, 25” — нет. В таблицу: <33> “25, 25”. В поток: <25>;
“25, 17” — нет. В таблицу: <34> “25, 17”. В поток: <25>;
“17, 25” — нет. В таблицу: <35> “17, 25”. В поток: <17>;
“25, 25” — есть в таблице; “25, 25, 25” — нет. В таблицу: <36> “25, 25, 25”. В поток: <33>;
И, наконец последняя строка “25”, за ней идет конец сообщения, поэтому мы просто выводим в поток <25>.

Текущий символ	Следующий символ	Вывод		Словарь
		Код	Биты
15	25	15	1111	32:	15, 25
25	25	25	11001	33:	25, 25
25	17	25	11001	34:	25, 17
17	25	17	10001	35:	17, 25
25	25	-	-		-
25	25	33	100001	36:	25, 25, 25
25	-	25	11001		-

Итак, мы получаем закодированное сообщение "15, 25, 25, 17, 33, 25", что на 4 бита короче.

Декодирование

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

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

Данные		На выходе	Новая запись
Биты	Код		Полная		Частичная
1111	15	15			32:	15, ?
11001	25	25	32:	15, 25	33:	25, ?
11001	25	25	33:	25, 25	34:	25, ?
10001	17	17	34:	25, 17	35:	17, ?
100001	33	25, 25	35:	17, 25	36:	25, 25, ?
11001	25	25	36:	25, 25, 25

Примечание

Для повышения степени сжатия изображений данным методом часто используется одна «хитрость» реализации этого алгоритма. Некоторые изображения, подвергаемые сжатию с помощью LZW, имеют часто встречающиеся цепочки одинаковых значений, например 12, 12, 12 … или 30, 30, 30 … и т. п. Их непосредственное сжатие будет генерировать выходной код 12, 12, 32 и т.д. Спрашивается, можно ли в этом частном случае повысить степень сжатия? Оказывается, да, если мы оговорим следующие действия по кодированию и декодированию.
Кодирование таких цепочек будем осуществлять следующим образом:
Первый цвет 12 записывает с его же кодом из таблицы 12. Следующий цвет тоже 12, тогда добавляем в таблицу строку 12, 12 с кодом 32 и в выходной поток сразу заносим этот код, то есть 32. Смотрим входной поток дальше. Если на вход опять поступает цвет 12, он есть в таблице, смотрим следующий – 12, последовательность 12, 12 тоже есть в таблице, смотрим дальше – 12, последовательности 12, 12, 12 присваиваем код 33 и заносим его в выходной поток. В результате на выходе получаем последовательность 12, 32, 33 …, которая гораздо короче прямого кодирования стандартным методом LZW.

Можно показать, что такая последовательность будет корректно восстановлена. Декодировщик сначала читает первый код – это 12, которому соответствует цвет 12. Затем читает код 32, но этого кода в его таблице нет. Но мы уже знаем, что такая ситуация возможна только в том случае, когда добавляемый символ равен первому символу только что считанной последовательности, то есть 12. Поэтому он добавит в свою таблицу строку 12, 12 с кодом 32, а в выходной поток поместит 12, 12. И так может быть раскодирована вся цепочка кодов.

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

Достоинства и недостатки

+ Не требует вычисления вероятностей встречаемости символов или кодов.
+ Для выполнения обратного процесса ("распаковки") нет необходимости сохранять таблицу в документе.
+ Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа - монохромных, черно - белых, или полноцветных.
- Алгоритм не проводит анализ входных данных поэтому не оптимален.

Патенты

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах.
Среди обладателей патентов была компания Unisys. Поэтому использование формата GIF, в котором он используется, было раскритиковано из-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).

Когда в 2003 году закончился срок действия патента на метод сжатия данных LZW, он остался востребованным только для формата GIF.

Источники

• Wikipedia | LZW (рус)

• Wikipedia | LZW (англ)

• Семенюк В.В. - Экономное кодирование дискретной информации