Odyssey Magazine #01 05 марта 1997

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

Система - IBM:Об алгаритме сжатия Lempel-Ziw Welch и его реализации для формата GIF.

  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