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

Метод LZW-сжатия данных

Каждый программист имеет хотя бы некоторое представление о сжатии (упаковке) данных. Такие программы, как "ARC" (System Enhancement Associates, Wayne, N. J.) и "PkZip" (PKWARE, Glendale, Wisc.) вездесущи в мире MS-DOS. "ARC", к тому же, используется в ряде других операционных систем, таких как Unix, CP/M и т. д. Пользователи CP/M долгое время использовали также "SQ" и "USQ" для сжатия и распаковки программ. Пользователи Unix имеют утилиты "COMPRESS" и "COMPACK". Однако техника сжатия данных используется этими программами только двумя способами: пересылка файлов по линиям связи и архивация. Сжатие данных имеет незаслуженную репутацию трудного для освоения, тяжелого в реализации и тем не менее существующего явления. Фактически техника, использованная в выше упомянутых программах, относительно проста и может быть реализована в виде стандартных утилит, содержащих довольно мало строк кода. В этой статье обсуждается Lempel-Ziv-Welch (LZW) сжатие, хорошая, повсеместно используемая техника.
LZW, к примеру, сжимая экранные формы, может легко "снять" 50K байт с программы, основную часть которой составляют хэлповые экраны. При использовании LZW-сжатия 500K байт программного обеспечения могут быть поставлены конечному пользователю на 360Kб дискете. Чрезмерно разбухшие файлы базы данных могут быть сжаты до десяти процентов их исходного размера.

Основы LZW

Собственно исходный Lempel/Ziv подход к сжатию данных был впервые обнародован в 1977г., а усовершенствованный (Terry Welch) вариант был опубликован в 1984г. Алгоритм на удивление прост. Если в двух словах, то LZW-сжатие заменяет строки символов некоторыми кодами. Это делается без какого-либо анализа входного текста. Вместо этого при добавлении каждой новой строки символов просматривается таблица строк. Сжатие происходит, когда код заменяет строку символов. Коды, генерируемые LZW-алгоритмом, могут быть любой длины, но они должны содержать больше бит, чем единичный символ. Первые 256 кодов (когда используются 8-битные символы) по умолчанию соответствуют стандартному набору символов. Остальные коды соответствуют обрабатываемым алгоритмом строкам.
Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 - 255 соответствуют отдельным байтам, а коды 256 - 4095 соответствуют подстрокам.

Сжатие

Алгоритм LZW-сжатия в простейшей форме приведен на рис.1. Каждый раз, когда генерируется новый код, новая строка добавляется в таблицу строк. LZW постоянно проверяет, является ли строка уже известной, и, если так, выводит существующий код без генерации нового.

Процедура LZW-сжатия:

СТРОКА = очередной символ из входного потока
WHILE входной поток не пуст DO
СИМВОЛ = очередной символ из входного потока
IF СТРОКА+СИМВОЛ в таблице строк THEN
СТРОКА = СТРОКА+СИМВОЛ
ELSE
вывести в выходной поток код для СТРОКА
добавить в таблицу строк СТРОКА+СИМВОЛ
СТРОКА = СИМВОЛ
END of IF
END of WHILE
вывести в выходной поток код для СТРОКА

Рис. 1 Алгоритм сжатия

Простая строка, использованная для демонстрации алгоритма, приведена на рис.2. Входная строка является кратким списком английских слов, разделенных символом "/". Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки "/W" в таблице. Когда он не находит эту строку, то генерирует код для "/" и добавляет в таблицу строку "/W". Т. к. 256 символов уже определены для кодов 0 - 255, то первой определенной строке может быть поставлен в соответствие код 256. После этого система читает следующую букву ("E"), добавляет вторую подстроку ("WE") в таблицу и выводит код для буквы "W".
Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов "/" и "W", не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.

Входная строка : /WED/WE/WEE/WEB/WET

Вход(символы)	Выход(коды)	Новые коды и соответствующие строки
/W	/	256 = /W
E	W	257 = WE
D	E	258 = ED
/	D	259 = D/
WE	256	260 = /WE
/	E	261 = E/
WEE	260	262 = /WEE
/W	261	263 = E/W
EB	257	264 = WEB
/	B	265 = B/
WET	260	266 = /WET
<EOF>	T

Рис. 2 Процесс сжатия

Выходной поток для заданной строки показан на рис. 2, также как и полученная в результате таблица строк. Как вы можете заметить, эта таблица быстро заполняется, т. к. новая строка добавляется в таблицу каждый раз, когда генерируется код. В этом явно вырожденном примере было выведено пять закодированных подстрок и семь символов. Если использовать 9-битные коды для вывода, то 19-символьная входная строка будет преобразована в 13.5-символьная выходную строку. Конечно, этот пример был выбран только для демонстрации. В действительности сжатие обычно не начинается до тех пор, пока не будет построена достаточно большая таблица, обычно после прочтения порядка 100 входных байт.

Распаковка

Алгоритму сжатия соответствует свой алгоритм распаковки. Он получает выходной поток кодов от алгоритма сжатия и использует его для точного восстановления входного потока. Одной из причин эффективности LZW-алгоритма является то, что он не нуждается в хранении таблицы строк, полученной при сжатии. Таблица может быть точно восстановлена при распаковке на основе выходного потока алгоритма сжатия. Это возможно потому, что алгоритм сжатия выводит СТРОКОВУЮ и СИМВОЛЬНУЮ компоненты кода прежде чем он поместит этот код в выходной поток. Это означает, что сжатые данные не обременены необходимостью тянуть за собой большую таблицу перевода.
Алгоритм распаковки представлен на рис. 3. В соответствии с алгоритмом сжатия, он добавляет новую строку в таблицу строк каждый раз, когда читает из входного потока новый код. Все, что ему необходимо сделать в добавок - это перевести каждый входной код в строку и переслать ее в выходной поток.

Процедура LZW-распаковки:

читать СТАРЫЙ_КОД
вывести СТАРЫЙ_КОД
WHILE входной поток не пуст DO
читать НОВЫЙ_КОД
СТРОКА = перевести НОВЫЙ_КОД
вывести СТРОКУ
СИМВОЛ = первый символ СТРОКИ
добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ
СТАРЫЙ_КОД = НОВЫЙ_КОД
END of WHILE

Рис. 3 Алгоритм распаковки

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

Входные коды : / W E D 256 E 260 261 257 B 260 T

Вход	СТАРЫЙ КОД	СТРОКА	СИМВОЛ	Новый вход таблицы
НОВЫЙ КОД		Выход
/	/	/
W	/	W	W	256 = /W
E	W	E	E	257 = WE
D	E	D	D	258 = ED
256	D	/W	/	259 = D/
E	256	E	E	260 = /WE
260	E	/WE	/	261 = E/
261	260	E/	E	262 = /WEE
257	261	WE	W	263 = E/W
B	257	B	B	264 = WEB
260	B	/WE	/	265 = B/
T	260	T	T	266 = /WET

Рис. 4 Процесс распаковки

Выходной поток идентичен входному потоку алгоритма сжатия. Отметим, что первые 256 кодов уже определены для перевода одиночных символов, также как и в алгоритме сжатия.

Ловушка

К несчастью прекрасный, простой алгоритм распаковки, приведенный на рис. 4, является все таким слишком простым. В алгоритме сжатия существуют некоторые исключительные ситуации, которые создают проблемы при распаковке. Если существует строка, представляющая пару (СТРОКА СИМВОЛ) и уже определенную в таблице, а просматриваемый входной поток содержит последовательность СТРОКА СИМВОЛ СТРОКА СИМВОЛ СТРОКА, алгоритм сжатия выведет код прежде, чем распаковщик получит возможность определить его.
Простой пример иллюстрирует это. Предположим, строка "JOEYN" определена в таблице с кодом 300. Когда последовательность "JOEYNJOEYNJOEY" появляется в таблице, выходной поток алгоритма сжатия выглядит подобно тому, как показано на рис. 5.