Faultless #09 24 мая 1998

Программирование

LZW and GIF - Описание графических форматов .LZW и .GIF.

Тема: Графические форматы .LZW и .GIF
Автор: Steve Blackstock
----------------------------------------

                 - 1 -
 Я надеюсь, что  этот маленький документ
поможет просветить тех, кто хочет  знать
немного больше об алгоритме  сжатия Lem-
pel-Ziv Welch и,конкретно, о его реализа
ции для формата GIF.
 Перед тем, как мы начнем, немного о тер
минологии в свете данного документа:
"Символ":фундаментальный элемент данных.
В обычных текстовых файлах это отдельный
байт.В растровых изображениях,  которыми
вы заинтересовались, это индекс, который
указывает  цвет данного пиксела. Я  буду
ссылаться  на произвольный символ как на
"K".
"Поток символов": поток  символов такой,
как файл данных. "Цепочка": несколько по
следовательных  символов.  Длина цепочки
может  изменяться от 1 до очень большого
числа символов. Я могу указывать произво
льную цепочку как "[...]K".
"Префикс": почти то  же самое, что цепоч
ка, но  подразумевается, что префикс не-
посредственно  предшествует   символу, и
префикс может иметь нулевую длину. Я бу-
ду ссылаться на произвольный префикс,как
на "[...]".
"Корень": односимвольная цепочка.
Для большинства целей это просто символ,
но  иногда  это  может  быть иначе. Это
[...]K, где [...] пуста.
"Код": число, определяемое известным ко-
личеством бит, которое кодирует цепочку.
"Поток  кодов": выходной поток кодов,та-
ких как "растровые данные".
"Элемент": код и его цепочка.
"Таблица цепочек": список элементов обыч
но, но не обязательно, уникальных. Этого
должно быть достаточно для понимания до-
кумента.
 LZW - это способ сжатия данных, который
извлекает преимущества при повторяющихся
цепочках данных. Поскольку растровые дан
ные обычно содержат довольно много таких
повторений, LZW является хорошим методом
для их сжатия и раскрытия.
 В данный момент давайте рассмотрим обыч
ное  кодирование  и  декодирование с по-
мощью LZW-алгоритма.  В GIF используется
вариация  этого  алгоритма. При сжатии и
раскрытии LZW манипулирует тремя объекта
ми: потоком символов,потоком кодов и таб
лицей цепочек. При сжатии поток символов
является входным и поток кодов -  выход-
ным.При раскрытии входным является поток
кодов, а поток символов - выходным.Табли
ца  цепочек  порождается и при  сжатии и
при раскрытии, однако она никогда не пе-
редается  от сжатия к раскрытию и наобо-
рот.
                 - 2 -
 Первой вещью,которую мы делаем при LZW-
сжатии  является инициализация нашей це-
почки  символов. Чтобы  сделать это, нам
необходимо выбрать код размера (количест
во бит) и знать сколько возможных значе-
ний могут принимать наши символы. Давай-
те положим код размера равным 12  битам,
что  означает  возможность  запоминания
0FFF,или 4096, элементов в нашей таблице
цепочек.  Давайте также предположим, что
мы имеем 32 возможных различных символа.
(Это соответствует, например, картинке с
32 возможными цветами для каждого пиксе-
ла.) Чтобы инициализировать  таблицу, мы
установим  соответствие кода  #0 символу
#0,  кода  #1  то символу #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 состоит  в том, что
это  все, что нам нужно. Сжатие было вы-
полнено таким образом, что мы никогда не
встретим в потоке кодов код, который  мы
не могли бы преобразовать в цепочку.
 Нам необходимо определить нечто, называ
емое  "текущим  кодом", на  что мы будем
ссылаться как "<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 в этом особом случае
будет  [...]  плюс  первый символ [...].
Поэтому я должен добавить первый  символ
[...] к ней самой. Не так плохо.
                 - 5 -
В качестве примера (довольно часто встре
чающегося)  давайте  предположим, что мы
имеем  растровое  изображение  в котором
первые три пиксела имеют одинаковый цвет
Т.е. мой поток символов выглядит как: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],
что нет больше символов, вы должны закон
чить. Вывод цепочек и нахождение началь-
ных  символов  в них ставят сами по себе
проблемы эффективности,но я не собираюсь
здесь предлагать способы их решения. По-
ловина удовольствия от  программирования
состоит в разрешении подобных штук!
                 - 6 -
                  ---
А теперь  вариации  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, ваш по-
ток кодов начнется как:
                  - 7 -
             byte#0: hijabcde
             byte#1: .klmnofg
 Таким  образом  различие  между обычным
LZW и LZW для GIF заключаются  в наличии
двух дополнительных специальных кодов и
переменном размере сжатия. Если вы поня-
ли LZW, и вы поняли эти различия, вы по-
няли все! В качестве P.S. Вы могли заме-
тить, что кодировщик имеет небольшую би-
товую гибкость во время сжатия. Я описал
"жадный" способ,выбирающий перед выводом
кода настолько много символов, насколько
это возможно. Фактически такой способ яв
ляется стандартным для  LZW и дает в ре-
зультате наилучшую степень сжатия. Одна-
ко,нет никакого правила, которое запреща
ло бы вам остановиться и вывести код для
текущего префикса, вне зависимости от то
го, есть  ли он уже в таблице или нет, и
добавить эту цепочку плюс следующий сим-
вол в таблицу цепочек. Существуют различ
ные причины, чтобы пожелать это  сделать,
особенно, если цепочка слишком длинна  и
порождает трудности при хешировании.Если
вам это нужно, сделайте это. Надеюсь,это
поможет вам.
                        Steve Blackstock

P.S Стиву Блэкстоку помог заговорить по-
русски  сотрудник  Института  прикладной
математики AH CCCP А.Самотохин