КОМПЬЮТЕРНАЯ ЛИТЕРАТУРА - Объяснение LZW и GIF

Индекс материала
Объяснение LZW и GIF
Стр. 2
Все страницы
                              - 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, до  тех
 не
входит в таблицу цепочек. Вернемся обратно к сжатию и  постараемся