Объяснение LZW и GIF


	Сайт о сжатии >> Новинки \| О сервере (Compression Catalog! \| ENGLISH) Книга "Методы сжатия данных" >> Без потерь \| Изображений \| Видео Разделы >> Cтатьи \| Видео \| Arctest \| Ссылки \| Ru.compress \| Форум Проекты >> Д.Ватолина \| А.Ратушняка \| М.Смирнова \| В.Юкина \| Е.Шелвина \| Д.Шкарина

Объяснение 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. Поток символов выглядит как ABACABA. Давайте сожмем его. Сначала мы инициализируем нашу таблицу цепочек: #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
перевод - А.Самотохин

Объяснение LZW и GIF

Steve Blackstock перевод - А.Самотохин

Steve Blackstock
перевод - А.Самотохин