Алгоритм 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.
Конец
Пример
Рассмотрим пример сжатия и декодирования изображения.
Первой вещью, которую мы делаем при LZW-сжатии, является инициализация нашей цепочки символов. Чтобы сделать это, нам необходимо выбрать код размера (количество бит) и знать, сколько возможных значений могут принимать наши символы. Давайте положим код размера равным 12 битам, что означает возможность запоминания 4096 элементов в нашей таблице цепочек. Давайте также предположим, что мы имеем 32 возможных различных символа. ( Это соответствует, например, картинке с 32 возможными цветами для каждого пиксела ) Чтобы инициализировать таблицу, мы установим соответствие кода 0 символу 0, кода 1 символу 1, и т.д., до кода 31 и символа 31. На самом деле мы указали, что каждый код от 0 до 31 является корневым. Больше в таблице не будет других кодов, обладающих этим свойством.
Изначальный словарь:
| Символ | Битовый код |
|---|---|
| 0 | 00 |
| 1 | 01 |
| 2 | 10 |
| 3 | 11 |
| .. | .. |
| 31 | 11111 |
Кодирование
Пусть мы сжимаем последовательность 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 | 10111 | 33: | 25, 25 | |
| 25 | 17 | 25 | 10111 | 34: | 25, 17 | |
| 17 | 25 | 17 | 10001 | 35: | 17, 25 | |
| 25 | 25 | - | - | - | ||
| 25 | 25 | 33 | 100001 | 36: | 25, 25, 25 | |
| 25 | - | 25 | 10111 | - | выводим текущую последовательность | |
| и останавливаем кодирование | ||||||
Декодирование
Теперь представим что мы получили закодированное сообщение, приведённое выше, и нам нужно его декодировать. Прежде всего, нам нужно знать начальный словарь, а последующие записи словаря мы можем реконструировать уже на ходу, поскольку они являются просто конкатенацией предыдущих записей.
| Данные | На выходе | Новая запись | Комментарии | ||||
|---|---|---|---|---|---|---|---|
| Биты | Код | Полная | Частичная | ||||
| 01 | 1 | A | 4: | A? | |||
| 10 | 2 | B | 4: | AB | 5: | B? | |
| 11 | 3 | C | 5: | BC | 6: | C? | |
| 100 | 4 | AB | 6: | CA | 7: | AB? | |
| 110 | 6 | CA | 7: | ABC | 8: | CA? | |
| 101 | 5 | BC | 8: | CAB | 9: | BC? | |
| 111 | 7 | ABC | 9: | BCA | 10: | ABC? | |
| 1010 | 10 | ABCA | 10: | ABCA | 11: | ABCA? | Решение проблемы см. ниже |
| 101 | 5 | BC | 11: | ABCAB | 12: | BC? | |
| 000000 | 0 | # | |||||
Единственная небольшая трудность может возникнуть, если новое слово словаря пересылается немедленно. В приведённом выше примере декодирования, когда декодер встречает первый символ, ABC?, он знает, что слово 10 начинается с ABC, но чем оно заканчивается? Проиллюстрируем проблему следующим примером. Мы декодируем сообщение ABABA:
Данные: На выходе: Новая запись:
Полная: Частичная:
.
.
.
011101 = 29 AB 46: (word) 47: AB?
101111 = 47 AB? <--- что нам с этим делать?
На первый взгляд, для декодера это неразрешимая ситуация. Мы знаем наперёд, что словом 47 должно быть ABA, но как декодер узнает об этом? Заметим, что слово 47 состоит из слова 29 плюс символ идущий следующим. Таким образом, слово 47 заканчивается на «символ идущий следующим». Но, поскольку это слово посылается немедленно, то оно должно начинаться с «символа идущего следующим», и поэтому оно заканчивается тем же символом что и начинается, в данном случае — A. Этот трюк позволяет декодеру определить, что слово 47 это ABA.
В общем случае, такая ситуация появляется, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре.
Патенты
На алгоритм LZW и его вариации был выдан ряд патентов, как в США, так и в других странах. К настоящему времени, сроки всех патентов истекли.
Unisys, GIF и PNG
Компания Unisys приобрела патент на этот алгоритм. Поэтому использование формата GIF, в котором он используется, было раскритиковано из-за лицензионных отчислений. Был предложен альтернативный формат PNG (PNG not GIF).
К настоящему сроку патенты истекли, поэтому спор утих.
