Назад в раздел
Объяснение LZW И GIF.
- 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.]
|
|
 |
|
