Описание алгортма LZW. Коментарии по поводу GIF

Раскрытие, возможно более сложно концептуально, однако программная реализация его проще.

Опишем как это делается. Мы опять начинаем с инициализации таблицы цепочек. Эта таблица образуется исходя из тех знаний, которыми мы располагаем о порождаемом в конце концов потоке символов, например, о возможных значениях символов. В GIF-файлах эта информация находится в заголовке, как число возможных значений пикселов. Однако, прелесть LZW состоит в том, что это все, что нам нужно. Сжатие было выполнено таким образом, что мы никогда не встретим в потоке кодов код, который мы не могли бы преобразовать в цепочку.

Нам необходимо определить нечто, называемое "текущим кодом", на что мы будем ссылаться как "<code&gt", и "старым кодом", на который будем ссылаться как "<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) бит из потока кодов. В качестве специальных кодов используются: или код очистки, равный (2**N), и или конец информации, равный (2**N + 1). говорит кодировщику, что нужно снова инициализировать таблицу цепочек и переустановить размер сжатия равным (N+1). означает что кодов больше нет. Если вы ведете кодирование или декодирование, вы должны начать добавление элементов в таблицу цепочек с + 2. Если вы ведете кодирование, вам следует вывести в качестве самого первого кода, и затем опять каждый раз, как только вы достигните кода #4095 (шестнадцатиричное FFF), поскольку GIF не допускает размера сжатия большего 12 бит. Если вы ведете раскрытие, вам следует реинициализировать вашу таблицу цепочек, как только вы обнаружите .

Переменный размер сжатия на самом деле не доставляет особых хлопот. Если вы ведете кодирование вы начинаете с размера сжатия в (N+1) битов, и, как только вы выведете код (2**(размер сжатия)-1), вы увеличиваете размер сжатия на один бит. Следовательно, следующий код вашего вывода будет на один бит длиннее. Помните, что наибольший размер сжатия равен 12 битам, что соответствует коду 4095. Если вы достигли этого предела, вы должны вывести в качестве следующего кода и начать сначала. Если вы ведете декодирование, вы должны увеличить ваш размер сжатия КАК ТОЛЬКО ВЫ запишите элемент #(2**(размер сжатия) - 1) в таблицу цепочек. Следующий код, который вы ПРОЧИТАЕТЕ будет на один бит длиннее. Не делайте ошибки, дожидаясь, пока вам будет нужно добавить к таблице код (2**размер сжатия). Вы уже пропустили бит из последнего кода.

Упаковка кодов в битовый поток растровых данных также является потенциальным камнем преткновения для новичков кодирования и декодирования. Младший бит кода должен совпадать с младшим доступным битом первого доступного байта в потоке кодов. Например, если вы начали с 5-битного кодов сжатия, и ваши три первых кода, скажем, , , , где e, j, и o биты #0, ваш поток кодов начнется как:

       byte#0: hijabcde
       byte#1: .klmnofg

Таким образом различие между обычным LZW и LZW для GIF заключаются в наличии двух дополнительных специальных кодов и переменном размере сжатия. Если вы поняли LZW, и вы поняли эти различия, вы поняли все!

В качестве P.S. Вы могли заметить, что кодировщик имеет небольшую битовую гибкость во время сжатия. Я описал "жадный" способ, выбирающий перед выводом кода настолько много символов, насколько это возможно. Фактически такой способ является стандартным для LZW и дает в результате наилучшую степень сжатия. Однако, нет никакого правила, которое запрещало бы вам остановиться и вывести код для текущего префикса, вне зависимости от того, есть ли он уже в таблице или нет, и добавить эту цепочку плюс следующий символ в таблицу цепочек. Существуют различные причины, чтобы пожелать это сделать, особенно, если цепочка слишком длинна и порождает трудности при хешировании. Если вам это нужно, сделайте это.

Надеюсь, это поможет вам.

1.

52K

07 октября 2009 года

black_engel

1 / / 07.10.2009

8 октября 2009, 12:25:33

Руский перевод очень плох...
(на примере Фразы : "Если вы достигли этого предела, вы должны вывести в качестве следующего кода и начать сначала." - что вывести ??? таких похожих фраз здесь, к сожалению, очень много)

просьба предоставить англоязычные исходники или ссылки на тех документацию по GIF.