Алгоритм LZW

Материал из Викиконспекты
Версия от 07:12, 25 октября 2011; Egor (обсуждение | вклад) (Декодирование)
Перейти к: навигация, поиск
Определение:
Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (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 25, 25 35: 17, 25 36: 25, 25, ?
11001 25 25 36: 25, 25, 25 - -

Патенты

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

Unisys, GIF и PNG

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

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

Источники