Steve Blackstock
Стиву Блэкстоку помог заговорить по-
русски сотрудник Института прикладной
математики AH CCCP А.Самотохин
Мusic by Phantom Lord
ОБЪЯСНЕНИЕ LZW И GIF
Я надеюсь, что этот маленький доку-
мент поможет просветить тех, кто хочет
знать немного больше об алгоритме сжатия
Lempel-Ziv Welch и, конкретно, о его реа-
лизации для формата GIF.
Перед тем, как мы начнем, немного о
терминологии в свете данного документа:
"Символ": фундаментальный элемент дан-
ных. В обычных текстовых файлах это от-
дельный байт. В растровых изображениях,
которыми вы заинтересовались, это индекс,
который указывает цвет данного пиксела. Я
буду ссылаться на произвольный символ как
на "K".
"Поток символов": поток символов такой,
как файл данных.
"Цепочка": несколько последовательных
символов. Длина цепочки может изменяться
от 1 до очень большого числа символов. Я
могу указывать произвольную цепочку как
"[...]K".
"Префикс": почти то же самое, что це-
почка, но подразумевается, что префикс
непосредственно предшествует символу, и
префикс может иметь нулевую длину. Я буду
ссылаться на произвольный префикс, как на
"[...]".
"Корень": односимвольная цепочка. Для
большинства целей это просто символ, но
иногда это может быть иначе. Это [...]K,
где [...] пуста.
"Код": число, определяемое известным
количеством бит, которое кодирует цепоч-
ку.
"Поток кодов": выходной поток кодов,
таких как "растровые данные".
"Элемент": код и его цепочка.
"Таблица цепочек": список элементов
обычно, но не обязательно, уникальных.
Этого должно быть достаточно для по-
нимания документа.
LZW - это способ сжатия данных, ко-
торый извлекает преимущества при повторя-
ющихся цепочках данных. Поскольку растро-
вые данные обычно содержат довольно много
таких повторений, LZW является хорошим
методом для их сжатия и раскрытия.
В данный момент давайте рассмотрим
обычное кодирование и декодирование с по-
мощью LZW-алгоритма. В GIF используется
вариация этого алгоритма.
При сжатии и раскрытии LZW манипули-
рует тремя объектами: потоком символов,
потоком кодов и таблицей цепочек. При
сжатии поток символов является входным и
поток кодов - выходным. При раскрытии
входным является поток кодов, а поток
символов - выходным. Таблица цепочек по-
рождается и при сжатии и при раскрытии,
однако она никогда не передается от сжа-
тия к раскрытию и наоборот.
Первой вещью, которую мы делаем при
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] и в входном пото-
ке не остается больше символов, вы выво-
дите код для [.c.] и покидаете таблицу.
Все сделано.
Хотите пример? Давайте предположим,
что мы имеем 4-символьный алфавит:
A,B,C,D. Поток символов выглядит как ABA-
CABA. Давайте сожмем его. Сначала мы ини-
циализируем нашу таблицу цепочек: #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.
Это все, о чем следует заботиться
при сжатии. Раскрытие, возможно более
сложно концептуально, однако программная
реализация его проще.
Опишем как это делается. Мы опять
начинаем с инициализации таблицы цепочек.
Эта таблица образуется исходя из тех зна-
ний, которыми мы располагаем о порождае-
мом в конце концов потоке символов, нап-
ример, о возможных значениях символов. В
GIF-файлах эта информация находится в за-
головке, как число возможных значений
пикселов. Однако, прелесть LZW состоит в
том, что это все, что нам нужно. Сжатие
было выполнено таким образом, что мы ни-
когда не встретим в потоке кодов код, ко-
торый мы не могли бы преобразовать в це-
почку.
Нам необходимо определить нечто,
называемое "текущим кодом", на что мы бу-
дем ссылаться как "<code>", и "старым ко-
дом", на который будем ссылаться как
"<old>". Чтобы начать распаковку возьмем
первый код. Теперь он становится <code>.
Этот код будет инициализировать таблицу
цепочек в качестве корневого. Выводим ко-
рень в поток символов. Делаем этот код
старым кодом <old>.
(*) Теперь берем следующий код и
присваиваем его <code>. Возможно, что
этот код не входит в таблицу цепочек, но
давайте пока предположим, что он там
есть. Выводим цепочку, соответствующую
<code> в поток символов. Теперь найдем
первый символ в цепочке, которую вы
только что получили. Назовем его K. Доба-
вим его к префиксу [...], сгенерированно-
му посредством <old>, чтобы получить но-
вую цепочку [...]K. Добавим эту цепочку в
таблицу цепочек и установим старый код
<old> равным текущему коду <code>. Повто-
ряйте от того места, которое я обозначил
звездочкой и вы все сделаете. Прочтите
этот абзац еще раз, если вы только "про-
бежались" по нему!!!
Теперь давайте рассмотрим ту возмож-
ность, что <code> не входит в таблицу це-
почек. Вернемся обратно к сжатию и поста-
раемся понять, что происходит, если во
входном потоке появляется цепочка типа
P[...]P[...]PQ. Предположим, что P[...]
уже находится в таблице, а P[...]P - нет.
Кодировщик выполнит грамматический разбор
P[...], и обнаружит, что P[...]P от-
сутствует в таблице. Это приведет к выво-
ду кода для P[...] и добавлению P[...]P в
таблицу цепочек. Затем он возьмет P[...]P
для следующей цепочки и определит, что
P[...]P есть в таблице и выдаст выходной
код для P[...]P, если окажется, что
P[...]PQ в таблице отсутствует.
Декодировщик всегда находится "на
один шаг сзади" кодировщика. Когда деко-
дировщик увидит код для P[...]P, он не
добавит этот код к своей таблице сразу,
поскольку ему нужен начальный символ
P[...]P для добавления к цепочке для пос-
леднего кода P[...], чтобы сформировать
код для P[...]P. Однако, когда декодиров-
щик найдет код, который ему еще неизвес-
тен, он всегда будет на 1 больше послед-
него добавленного к таблице. Следова-
тельно, он может догадаться что цепочка
для этого кода должна быть и, фактически,
всегда будет правильной.
Если я декодировщик, и я увидел код
#124, а моя таблица цепочек содержит пос-
ледний код только с #123, я могу считать,
что код с #124 должен быть, добавить его
к моей таблице цепочек и вывести саму це-
почку. Если код #123 генерирует цепочку,
на которую я сошлюсь здесь как на префикс
[...], то код #124 в этом особом случае
будет [...] плюс первый символ [...]. По-
этому я должен добавить первый символ
[...] к ней самой. Не так плохо.
В качестве примера (довольно часто
встречающегося) давайте предположим, что
мы имеем растровое изображение в котором
первые три пиксела имеют одинаковый цвет.
Т.е. мой поток символов выглядит как :
QQQ.... Для определенности давайте ска-
жем, что мы имеем 32 цвета и Q соот-
ветствует цвету #12. Кодировщик сгенери-
рует последовательность кодов 12,32,....
(если вы не поняли почему, возьмите мину-
ту, чтобы понять.) Вспомним, что код #32
не входит в начальную таблицу, которая
содержит коды от #0 до #31. Декодировщик
увидит код #12 и транслирует его как цвет
Q. Затем он увидит код #32, о значении
которого он пока не знает. Но если он по-
думает о нем достаточно долго, он сможет
понять, что QQ должно быть элементом #32
в таблице и QQ должна быть следующей це-
почкой вывода.
Таким образом, псевдо код декодиро-
вания можно представить следующим обра-
зом:
[1] Инициализация строки цепочек;
[2] взять первый код: <code>;
[3] вывести цепочку для <code> в
поток символов;
[4] <old> = <code>;
[5] <code> <- следующий код в по-
токе кодов;
[6] существует ли <code> в табли-
це цепочек? (да: вывод цепоч-
ки для <code> в поток симво-
лов;[...] <- трансляция для
<old>;K<- первый символ тран-
сляции для <code>; добавить
[...]K в таблицу цепочек;
<old> <- <code>; )(нет: [...]
<- трансляция для <old>; K
<- первый символ [...]; вывод
[...]K в поток символов и до-
бавление его к таблице цепо-
чек; <old> <- <code> )
[7] go to [5];
Опять же, если вы обнаружите на ша-
ге [5], что нет больше символов, вы
должны закончить. Вывод цепочек и нахож-
дение начальных символов в них ставят са-
ми по себе проблемы эффективности, но я
не собираюсь здесь предлагать способы их
решения. Половина удовольствия от прог-
раммирования состоит в разрешении подоб-
ных штук!
А теперь вариации GIF'а на эту те-
му. В части заголовка GIF-файла существу-
ет поле, называемое в потоке растровых
данных "кодом размера". Это весьма запу-
тывающее название для этого поля, но мы
должны с ним смириться. На самом деле это
"размер корня". Фактический размер (в би-
тах) кодов сжатия в действительности из-
меняется в процессе сжатия/раскрытия, и я
буду ссылаться на него здесь, как на
"размер сжатия".
Начальная таблица, как обычно, со-
держит коды для всех корней, но к ее
верхней части добавляются два специальных
кода. Предположим, мы имеем "размер ко-
да", который обычно равен числу битов на
пиксел. Обозначим его N. Если число битов
на пиксел равно 1, N должно равняться 2:
корни занимают ячейки #0 и #1 в начальной
таблице и два специальных кода будут за-
нимать ячейки #4 #5. В любом другом слу-
чае N равно числу битов на пиксел, корни
занимают ячейки от #0 до #(2**N-1), а
специальные коды равны (2**N) и (2**N +
1).
Начальный размер сжатия будет равен
N+1 биту на код. Если вы ведете кодирова-
ние, вы выводите сначала коды длиной
(N+1) бит и, если вы ведете декодирова-
ние, вы выбираете сначала (N+1) бит из
потока кодов. В качестве специальных ко-
дов используются: <CC> или код очистки,
равный (2**N), и <EOI> или конец информа-
ции, равный (2**N + 1). <CC> говорит ко-
дировщику, что нужно снова инициализиро-
вать таблицу цепочек и переустановить
размер сжатия равным (N+1). <EOI> означа-
ет что кодов больше нет. Если вы ведете
кодирование или декодирование, вы должны
начать добавление элементов в таблицу це-
почек с <CC> + 2. Если вы ведете кодиро-
вание, вам следует вывести <CC> в ка-
честве самого первого кода, и затем опять
каждый раз, как только вы достигните кода
#4095 (шестнадцатиричное FFF), поскольку
GIF не допускает размера сжатия большего
12 бит. Если вы ведете раскрытие, вам
следует реинициализировать вашу таблицу
цепочек, как только вы обнаружите <CC>.
Переменный размер сжатия на самом
деле не доставляет особых хлопот. Если вы
ведете кодирование вы начинаете с размера
сжатия в (N+1) битов, и, как только вы
выведете код (2**(размер сжатия)-1), вы
увеличиваете размер сжатия на один бит.
Следовательно, следующий код вашего выво-
да будет на один бит длиннее. Помните,
что наибольший размер сжатия равен 12 би-
там, что соответствует коду 4095. Если вы
достигли этого предела, вы должны вывести
<CC> в качестве следующего кода и начать
сначала. Если вы ведете декодирование, вы
должны увеличить ваш размер сжатия КАК
ТОЛЬКО ВЫ запишите элемент #(2**(размер
сжатия) - 1) в таблицу цепочек. Следующий
код, который вы ПРОЧИТАЕТЕ будет на один
бит длиннее. Не делайте ошибки, дожида-
ясь, пока вам будет нужно добавить к таб-
лице код (2**размер сжатия). Вы уже про-
пустили бит из последнего кода.
Упаковка кодов в битовый поток
растровых данных также является потенци-
альным камнем преткновения для новичков
кодирования и декодирования. Младший бит
кода должен совпадать с младшим доступным
битом первого доступного байта в потоке
кодов. Например, если вы начали с 5-бит-
ного кодов сжатия, и ваши три первых ко-
да, скажем, <abcde>, <fghij>, <klmno>,
где e, j, и o биты #0, ваш поток кодов
начнется как:
byte#0: hijabcde
byte#1: .klmnofg
Таким образом различие между обыч-
ным LZW и LZW для GIF заключаются в нали-
чии двух дополнительных специальных кодов
и переменном размере сжатия. Если вы по-
няли LZW, и вы поняли эти различия, вы
поняли все!
В качестве P.S. Вы могли заметить,
что кодировщик имеет небольшую битовую
гибкость во время сжатия. Я описал "жад-
ный" способ, выбирающий перед выводом ко-
да настолько много символов, насколько
это возможно. Фактически такой способ яв-
ляется стандартным для LZW и дает в ре-
зультате наилучшую степень сжатия. Одна-
ко, нет никакого правила, которое запре-
щало бы вам остановиться и вывести код
для текущего префикса, вне зависимости от
того, есть ли он уже в таблице или нет, и
добавить эту цепочку плюс следующий сим-
вол в таблицу цепочек. Существуют различ-
ные причины, чтобы пожелать это сделать,
особенно, если цепочка слишком длинна и
порождает трудности при хешировании. Если
вам это нужно, сделайте это.
Надеюсь, это поможет вам.
__________________________________________ Steve Blackstock
