Домашняя страничка Чьезо

Сжатие по методу LZW

Объяснение метода сжатия, используемого в картинках GIF


Скрипт

Чтобы наглядно объяснить метод сжатия LZW, я написал скрипт (иначе говоря, сценарий) на языке JavaScript.

Чтобы скрипт нормально работал, в браузере Internet Explorer должны быть разрешены "сценарии для обозревателя", а если при этом у вас Windows XP, должен быть еще разрешен "запуск активного содержимого файлов". В браузере Mozilla Firefox надо включить (Enable) JavaScript, а в окошке "дополнительно (Advanced) разрешить заменять картинки (Change images). Всё это настраивается в свойствах (Options) браузеров.

В связи с ограничениями языка JavaScript (потому, кстати, он и самый безопасный в интернете) мы не можем просто взять какую-нибудь картинку BMP и считывать ее пиксел за пикселом. Три тестовых картинки пришлось вставить в саму программу в виде строк, каждый символ которых - номер цвета пиксела (то есть картинка уже индексирована). Не применяю я здесь и метод плотной упаковки, используемый в GIF, когда в один байт пакуется нецелое число пикселов, а со временем код удлиняется. Но это не имеет прямого отношения к самой LZW-компрессии, которую я хотел показать в первую очередь.

  Словарь LZW-код  
Исходные картинки  
Исходные картинки
Исходные картинки  
 
  

Вначале нажмите кнопку "Сжать". Одна из картинок слева будет сжата, и в окошках "Словарь" и "LZW-код" появятся строки заполненного словаря и LZW-код сжатой картинки. Если затем нажать кнопку "Восстановить", картинка будет восстановлена и показана в квадрате справа. Кнопка "Выбор картинки" позволяет выбрать между тремя картинками, предназначенными для сжатия.

Если вы хотите более подробно узнать, как всё это работает, можете посмотреть "изнанку" этой странички - сам код HTML. Сделать это можно с помощью меню "Вид->Просмотр HTML-кода" или "View->Page Source", или подобных им, в зависимости от браузера. Скрипт находится в самом начале странички. Почти к каждой строчке скрипта есть комментарий на русском языке. Там же находятся и сами картинки в виде массивов bmp[]. Если поменять в них цифры, картинки изменят свой вид (одна цифра соответствует одному пикселу).

Сжатие

Сначала создается словарь (его еще называют таблицей символов или просто таблицей, но я предпочитаю слово "словарь" - по-моему, оно лучше объясняет его функцию). Это главное действующее лицо как процесса сжатия, так и восстановления картинки.

Небольшое отступление. При сжатии файлов GIF его размер всегда 4096 строк - ни больше, ни меньше. От этого зависит правильность восстановления картинки (переполнение словаря должно наступать всегда в один момент, при сжатии после этого в LZW-поток добавляется код очистки CC). Длина строк в словаре ничем не ограничена. В некоторых случаях строки могут быть длиной с саму картинку (например, если там один фон без изображения). Поэтому, для экономии места, прямую запись строк в словарь не используют. У меня она применена только для наглядности. Обычно же вместо нее используют запись первого символа строки и ссылки на остальную часть строки в словаре. По этому адресу опять находится первый символ и ссылка на следующий символ, и т.д. (рекурсивная запись). Если ссылка пустая, это означает конец строки. Поскольку поиск и сравнение строк в словаре размером 4096 строк занимает много времени, а делать это приходится с каждым пикселом, то для ускорения поиска применяют хеширование. Рядом с каждой строкой записывают хеш-код - число, созданное по некоторой хитрой формуле, и зависящее от содержания строки. При поиске сравниваются хеш-коды, а когда они совпадают - сравниваются сами строки, чтобы убедиться, что они действительно совпали. У меня это тоже нет. Сравниваются сразу сами строки.

После создания словарь пустой, и его надо заполнить символами данного алфавита (номерами цветов). Например, если у нас 8 цветов, то первые 8 строк словаря получают значения от "0" до "7". Очистка и заполнение словаря называются инициализацией. После нее начинается само сжатие картинки (кроме словаря есть еще "текущая строка" - вначале она тоже пустая).

Из потока индексированных цветов (в нашем случае это текстовая строка) берется один символ (номер цвета). Он добавляется к текущей строке, и вся строка сравнивается со строками в словаре. Если такая строка уже есть в словаре, то из потока берется следующий символ, и так до тех пор, пока не окажется, что такой строки в словаре нет. Тогда текущая строка добавляется в словарь на первое свободное место (начиная с адреса, равного числу цветов + 3, так как два места занимают спецкоды CC и EOI), а в поток кодов выводится номер строки словаря, которая последней совпала с текущей (то есть строки без символа, добавленного последним). Собственно, в этом и заключается суть LZW-компрессии. После добавления в словарь текущая строка обнуляется, и ею становится символ, добавленный к ней последним.

Блок-схема компрессииПеременные:
bmp[] - массив индексированных цветов (пикселов)
pos - текущее положение в массиве bmp[]
k
- символ из массива bmp[]
str - строка символов
code - готовый LZW-код

Функции:
Add() добавляет строку в словарь
Search() возвращает номер найденной в словаре строки, или -1, если строка не найдена
Write() записывает LZW-код в выходной массив lzw[]

Сжатие продолжается до тех пор, пока в потоке есть символы. Последним к LZW-потоку добавляется завершающий код EOI, но перед ним надо не забыть добавить последний значащий код - адрес последней строки, совпавшей со словарем.

Восстановление

Восстановление картинки из LZW-кода - более сложный процесс. Ведь надо восстановить те символы (номера цветов), которые были пропущены при сжатии. На помощь приходит все тот же словарь. Но воссозданный словарь должен выглядеть точно так же, как словарь, созданный при сжатии, иначе неизбежны ошибки.

Так же, как и при сжатии, вначале производится инициализация. Затем из потока LZW-кодов (в нашем случае это текстовая строка) берется первый код и выводится в поток символов восстанавливаемой картинки (добавляется к строке). Первый код не обрабатывается, а начиная со второго начинается декомпрессия. Каждый LZW-код - это просто адрес строки в словаре.

Есть два варианта обработки кодов:

  1. Если в словаре по этому адресу есть какая-либо строка (даже один символ), то в словарь на первую свободную позицию добавляется строка, состоящая из строки из словаря по адресу предыдущего кода и добавленного к ней первого символа строки из словаря по адресу текущего кода. В поток выводится строка из словаря по адресу текущего кода.
  2. Если строки в словаре нет, то в словарь добавляется строка, состоящая из строки из словаря по адресу предыдущего кода и добавленного к ней в конец первого символа этой же строки. Эта же самая строка выводится и в поток символов восстанавливаемой картинки.

Значение предыдущего кода в обоих случаях сохраняется в переменной "old".

Блок-схема декомпрессииПеременные:
bmp[] - массив индексированных цветов (пикселов)
pos - текущее положение в массиве bmp[]
code
- LZW-код из массива lzw[]
old
- предыдущий LZW-код
k - восстановленный цветовой символ
str - строка символов

Функции:
Read() считывает следующий LZW-код из массива lzw[]
Search()
возвращает номер найденной в словаре строки, или -1, если строка не найдена
Extract() возвращает строку из словаря по ее номеру
First() возвращает первый символ строки
Add() добавляет строку в словарь

Декомпрессия продолжается до тех пор, пока в потоке не встретится код CC или EOI.

Код CC (Clear Code), он равен числу цветов + 1, означает, что необходимо провести инициализацию (очистку и заполнение) словаря. В файлах GIF он всегда стоит первым в потоке, а в дальнейшем встречается при переполнении словаря - когда все 4096 строк заполнены. После него сжатие продолжается.

Код EOI (End Of Information) равен числу цветов + 2, он прекращает процесс сжатия. В файлах GIF он всегда стоит последним в потоке.

Сохранение странички

Cохранить страничку вместе со всеми картинками, использованными в скрипте, можно из браузера Internet Explorer. Как обычно, сохраняете страничку, выбрав "Веб-страница, полностью" и не меняя предложенного имени "LZW". В этом случае папка, куда автоматически сохранятся все картинки, будет называться "LZW.files", а так как на сайте картинки для скрипта хранились в папке с таким же названием, всё будет работать, как и прежде.

Дополнительная информация: