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

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

Простая программа, приведенная ниже, работает с 12-битными кодами. Значения кодов 0 - 255 соответствуют отдельным байтам, а коды 256 - 4095 соответствуют подстрокам.

Сжатие.

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

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

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

Этот процесс повторяется до тех пор, пока вторая подстрока, состоящая из прочитанных символов "/" и "W", не сопоставится со строковым номером 256. В этом случае система выводит код 256 и добавляет трехсимвольную подстроку в таблицу. Этот процесс продолжается до тех пор, пока не исчерпается входной поток и все коды не будут выведены.