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

Я надеюсь, что этот маленький документ поможет просветить тех, кто хочет знать немного больше об алгоритме сжатия 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 должна быть следующей цепочкой вывода.
Таким образом, псевдо-код декодирования можно представить следующим образом: