Алгоритм LZW
| Определение: |
| Алгори́тм Ле́мпеля — Зи́ва — Ве́лча (Lempel-Ziv-Welch, LZW) — это универсальный алгоритм сжатия данных без потерь |
Он был создан Абрахамом Лемпелем(Abraham Lempel), Якобом Зивом (Jacob Ziv) и Терри Велчем (Terry Welch). Опубликован Велчем в 1984 году, в качестве улучшенной реализации алгоритма LZ78, опубликованного Лемпелем и Зивом в 1978 году. Алгоритм не проводит анализ входных данных поэтому не оптимален, но быстро реализуем.
Применение
LZW - это способ сжатия данных, который извлекает преимущества при повторяющихся цепочках данных. Поскольку растровые данные обычно содержат довольно много таких повторений, LZW является хорошим методом для их сжатия и раскрытия.
В 1987 году алгоритм стал частью стандарта на формат изображений GIF. Он также может (опционально) использоваться в формате TIFF.
В настоящее время алгоритм содержится в стандарте PDF.
Описание
Процесс сжатия выглядит достаточно просто. Считываются последовательно символы входного потока и проверяется, есть ли в таблице такая строка. Если строка есть, то считывается следующий символ, а если строки нет, то заносится в поток код для предыдущей найденной строки, далее строка заносится в таблицу и снова начинается поиск.
Алгоритму декодирования на входе требуется только закодированный текст, поскольку он может воссоздать соответствующую таблицу преобразования непосредственно по закодированному тексту.
Алгоритм
- Инициализация словаря всеми возможными односимвольными фразами. Инициализация входной фразы ω первым символом сообщения.
- Считать очередной символ K из кодируемого сообщения.
- Если КОНЕЦ_СООБЩЕНИЯ, то выдать код для ω, иначе
- Если фраза ω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
Компания Unisys приобрела патент на этот алгоритм. Поэтому использование формата GIF, в котором он используется, было раскритиковано из-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).
К настоящему сроку патенты истекли, поэтому спор утих.
