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

Описание алгортма 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.

Это все, о чем следует заботиться при сжатии.