 |
- 1 -
Steve Blackstock
ОБЪЯСНЕНИЕ LZW И GIF
Я надеюсь, что этот маленький документ поможет просветить
тех, кто хочет знать немного больше об алгоритме сжатия Lempel-Ziv
Welch и, конкретно, о его реализации для формата GIF.
Перед тем, как мы начнем, немного о терминологии в свете
данного документа:
"Символ": фундаментальный элемент данных. В обычных текстовых
файлах это отдельный байт. В растровых изображениях,
которыми вы заинтересовались, это индекс, который
указывает цвет данного пиксела. Я буду ссылаться на
произвольный символ как на "K".
"Поток символов": поток символов такой, как файл данных.
"Цепочка": несколько последовательных символов. Длина цепочки
может изменяться от 1 до очень большого числа символов. Я
могу указывать произвольную цепочку как "[...]K".
"Префикс": почти то же самое, что цепочка, но подразумевается,
что префикс непосредственно предшествует символу, и
префикс может иметь нулевую длину. Я буду ссылаться на
произвольный префикс, как на "[...]".
"Корень": односимвольная цепочка. Для большинства целей это просто
символ, но иногда это может быть иначе. Это [...]K, где
[...] пуста.
"Код": число, определяемое известным количеством бит, которое
кодирует цепочку.
"Поток кодов": выходной поток кодов, таких как "растровые
данные".
"Элемент": код и его цепочка.
"Таблица цепочек": список элементов обычно, но не обязательно,
уникальных.
Этого должно быть достаточно для понимания документа.
LZW - это способ сжатия данных, который извлекает
преимущества при повторяющихся цепочках данных. Поскольку
растровые данные обычно содержат довольно много таких повторений,
LZW является хорошим методом для их сжатия и раскрытия.
В данный момент давайте рассмотрим обычное кодирование и
декодирование с помощью LZW-алгоритма. В GIF используется вариация
этого алгоритма.
При сжатии и раскрытии LZW манипулирует тремя объектами:
потоком символов, потоком кодов и таблицей цепочек. При сжатии
поток символов является входным и поток кодов - выходным. При
раскрытии входным является поток кодов, а поток символов -
выходным. Таблица цепочек порождается и при сжатии и при
раскрытии, однако она никогда не передается от сжатия к раскрытию
и наоборот.
- 2 -
Первой вещью, которую мы делаем при LZW-сжатии является
инициализация нашей цепочки символов. Чтобы сделать это, нам
необходимо выбрать код размера (количество бит) и знать сколько
возможных значений могут принимать наши символы. Давайте положим
код размера равным 12 битам, что означает возможность запоминания
0FFF, или 4096, элементов в нашей таблице цепочек. Давайте также
предположим, что мы имеем 32 возможных различных символа. (Это
соответствует, например, картинке с 32 возможными цветами для
каждого пиксела.) Чтобы инициализировать таблицу, мы установим
соответствие кода #0 символу #0, кода #1 to символу #1, и т.д., до
кода #31 и символа #31. На самом деле мы указали, что каждый код
от 0 до 31 является корневым. Больше в таблице не будет других
кодов, обладающих этим свойством.
Теперь мы начнем сжатие данных. Давайте сначала определим
нечто, называемое "текущим префиксом". Этот префикс мы будем
постоянно помнить и проводить сравнение с ним здесь и в
дальнейшем. Я буду обозначать его как "[.c.]". Изначально текущий
префикс ничего не содержит. Давайте также определим также "текущую
цепочку", которая образуется текущим префиксом и следующим
символом в потоке символов. Я буду обозначать текущую цепочку как
"[.c.]K", где K - некоторый символ.
Теперь посмотрите на первый символ в потоке символов. Назовем
его P. Сделаем [.c.]P текущей цепочкой. (В данной точке это,
конечно, корень P.) Теперь выполним поиск в таблице цепочек, чтобы
определить входит ли в нее [.c.]P. Конечно, сейчас это
произойдет, поскольку в нашу таблицу при инициализации были
помещены все корни. В этом случае мы ничего не делаем. Теперь
делаем текущим префиксом [.c.]P.
Берем следующий символ из потока символом. Назовем его Q.
Добавим текущий префикс, чтобы сформировать [.c.]Q, т.е. текущую
цепочку. Выполняем поиск в таблице цепочек, чтобы определить
входит ли в нее [.c.]Q. В данном случае этого, конечно, не будет.
Ага! Вот теперь нам нужно кое-что сделать. Добавим [.c.]Q
(которая в данном случае есть PQ) в таблицу цепочек под кодом #32,
и выведем код для [.c.] в поток кодов. Теперь начнем опять с
текущего префикса, соответствующего корню P. Продолжаем
добавление символов к [.c.], чтобы сформировать [.c.]K, до тех
пор, пока мы не сможем найти [.c.]K в таблице цепочек. Затем
выводим код для [.c.] и добавляем [.c.]K в таблицу цепочек. На
псевдо коде алгоритм будет описан приблизительно так:
[1] Инициализация таблицы цепочек;
[2] [.c.] <- пусто;
[3] K <- следующий символ в потоке символов;
[4] Входит ли [.c.]K в таблицу цепочек?
(да: [.c.] <- [.c.]K;
go to [3];
)
(нет: добавить [.c.]K в таблицу цепочек;
вывести код для [.c.] в поток кодов;
[.c.] <- K;
go to [3];
)
- 3 -
Насколько это просто! Конечно, когда мы выполняем шаг [3] и
в входном потоке не остается больше символов, вы выводите код для
[.c.] и покидаете таблицу. Все сделано.
Хотите пример? Давайте предположим, что мы имеем
4-символьный алфавит: A,B,C,D. Поток символов выглядит как
ABACABA. Давайте сожмем его. Сначала мы инициализируем нашу
таблицу цепочек: #0=A, #1=B, #2=C, #3=D. Первый символ есть A,
который входит в таблицу цепочек, следовательно [.c.] становится
равным A. Далее мы берем AB, которая не входит в таблицу,
следовательно мы выводим код #0 (для [.c.]), и добавляем AB в
таблицу цепочек с кодом #4. [.c.] становится равным B. Далее мы
берем [.c.]A = BA, которая не входит в таблицу цепочек,
следовательно выводим код #1, и добавляем BA в таблицу цепочек с
кодом #5. [.c.] становится равным A. Далее мы берем AC, которая не
входит в таблицу цепочек. Выводим код #0, и добавляем AC в таблицу
цепочек с кодом #6. Теперь [.c.] равно C. Далее мы берем [.c.]A =
CA, которая не входит в таблицу. Выводим #2 для C, и добавляем CA
к таблице под кодом #7. Теперь [.c.]=A. Далее мы берем AB, которая
ВХОДИТ в таблицу цепочек, следовательно [.c.] становится равным
AB, и мы ищем ABA, которой нет в таблице цепочек, поэтому мы
выводим код для AB, который равен #4, и добавляем ABA в таблицу
цепочек под кодом #8. [.c.] равно A. Мы не можем более взять
символов, поэтому мы выводим код #0 для A и заканчиваем.
Следовательно, поток кодов равен #0#1#0#2#4#0.
Несколько слов (три) следует сказать об эффективности:
используйте стратегию хеширования. Поиск в таблице цепочек может
быть сопряжен со значительными вычислениями и хеширование
значительно снижает эти затраты. Обратите внимание, что "прямое
LZW" сжатие работает с риском переполнения таблицы цепочек -
получается код, который не может быть представлен числом битов,
ранее установленных для кодов. Существует несколько путей для
того, чтобы справиться с этой проблемой и GIF реализует самый
простой из них. Мы будем делать также.
Важным моментом, на который стоит обратить внимание,
является то, что в любой точке во время сжатия выполняется
условие: если [...]K входит в таблицу цепочек, то [...] тоже
входит в нее. Это обстоятельство приводит к эффективному методу
запоминания цепочек в таблице. Вместо того, чтобы запоминать в
таблице всю цепочку, используйте тот факт, любая цепочка может
быть представлена как префикс плюс символ: [...]K. Если вы вносите
[...]K в таблицу, вы знаете, что [...] уже находится в ней, и
поэтому вы можете запомнить код для [...] плюс замыкающий символ
K.
Это все, о чем следует заботиться при сжатии. Раскрытие,
возможно более сложно концептуально, однако программная реализация
его проще.
- 4 -
Опишем как это делается. Мы опять начинаем с инициализации
таблицы цепочек. Эта таблица образуется исходя из тех знаний,
которыми мы располагаем о порождаемом в конце концов потоке
символов, например, о возможных значениях символов. В GIF-файлах
эта информация находится в заголовке, как число возможных значений
пикселов. Однако, прелесть LZW состоит в том, что это все, что нам
нужно. Сжатие было выполнено таким образом, что мы никогда не
встретим в потоке кодов код, который мы не могли бы преобразовать
в цепочку.
Нам необходимо определить нечто, называемое "текущим кодом",
на что мы будем ссылаться как "", и "старым кодом", на
который будем ссылаться как "". Чтобы начать распаковку
возьмем первый код. Теперь он становится . Этот код будет
инициализировать таблицу цепочек в качестве корневого. Выводим
корень в поток символов. Делаем этот код старым кодом .
(*) Теперь берем следующий код и присваиваем его .
Возможно, что этот код не входит в таблицу цепочек, но давайте
пока предположим, что он там есть. Выводим цепочку,
соответствующую в поток символов. Теперь найдем первый
символ в цепочке, которую вы только что получили. Назовем его K.
Добавим его к префиксу [...], сгенерированному посредством ,
чтобы получить новую цепочку [...]K. Добавим эту цепочку в таблицу
цепочек и установим старый код равным текущему коду .
Повторяйте от того места, которое я обозначил звездочкой и вы все
сделаете. Прочтите этот абзац еще раз, если вы только
"пробежались" по нему!!!
Теперь давайте рассмотрим ту возможность, что не
входит в таблицу цепочек. Вернемся обратно к сжатию и постараемся
|
BIGLIB
