Метод LZW-сжатия данных (стр. 5 )

[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
перевод - А. Самотохин