Алгоритм LZW

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

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

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

Применение

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

В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.

В настоящее время алгоритм содержится в стандарте PDF.

Описание

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

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

Алгоритм

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

Конец

Пример

< text=right > Изначальный словарь:

Символ	Битовый код
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 бита короче.

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

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

Данные		На выходе	Новая запись				Комментарии
Биты	Код		Полная		Частичная
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		7:	ABC	8:	CA?
101	5	BC	8:	CAB	9:	BC?
111	7	ABC	9:	BCA	10:	ABC?

Патенты

На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. К настоящему времени, сроки всех патентов истекли.

Unisys, GIF и PNG

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

К настоящему сроку патенты истекли, поэтому спор утих.

Источники

• Wikipedia | LZW (рус)

• Wikipedia | LZW (англ)

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