Odyssey Magazine #01
05 марта 1997

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

<b>Система</b> - 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



Другие статьи номера:

Вступление - Oб авторах журнала и о журнале.

Вступление - Oб авторах журнала

Вступление - Инструкция к оболочке журнала.

Отдохнем - GLODING PROGRAMMING (Программирование снизу вверх наискосок)

Ассемблер - Как вычислить синус на ассемлере.

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

Разное - о компьютерных проблемах: ПРОФИ и СКОРПИОН, IBM...

Отдохнем - "Приколы со стороны".

Деморынок - Хит-парад музыкальных демонстраций.

История - Хакеры - статья "ОНО" - об истории появления хакерства.

История - Классификация хакеров.

Отдохнем - "Как ломаются полуоси?".

Письма - Отзывы читателей о журнале.

Конкурс - Конкурс на лучшую головоломку !

Ассемблер - Быстрый расчет адреса по двум координатам.

IS DOS - Проблемы и решения

Новости - новости города.

Разборка - Описание игры THE DOOBLE.

Разборка - Описание игры BLOOD WYCH.

Обзор - новые игры: RETURN TO HOME 4, CITADEL, KLADEMINER, BRIDGE PLAYER, CRUSHER, AMERICAN TURBO KING, RAD RAMP RACER, KUNG FU MASTER, CHOY LEE, SIDERAL WAR, ARKARUM, DIRT TRACK RACER, DOUBLE DRAGON 2, NIGHT BREED, THE CYCLES, MOONTORC, KOMMANDO 2.

Система - Описание системных программ : UNIVERSAL SPRATE STUDIO (USS)

Гости - Старые знакомые:О истории создания краснодарской группа UNIT-5

Система - Описание системных программ : ACCEPT PROTECTION SYSTEM V1.0.


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Сaтaнинcкaя Библия - Книгa Люцифeрa VIII. O Чeлoвeчecкom Жeртвoпринoшeнии.
Белый_попугай - Советы молодожёнам.
Презентация - Авторские программы: Installer to AUTORUN DISK v2. 0, адвентюрная игра Diamond.

В этот день...   21 июня