Алгоритм сжатия LZW

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

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

СТРОКА = очередной символ из входного потока

WHILE входной поток не пуст DO

СИМВОЛ = очередной символ из входного потока

IF СТРОКА+СИМВОЛ в таблице строк THEN

СТРОКА = СТРОКА+СИМВОЛ

ELSE

вывести в выходной поток код для СТРОКА

добавить в таблицу строк СТРОКА+СИМВОЛ

СТРОКА = СИМВОЛ

END of IF

END of WHILE

вывести в выходной поток код для СТРОКА

Рассмотрим работу алгоритма на примере обработки входной строки /WED/WE/WEE/WEB/WET , которая является кратким списком английских слов, разделенных символом “/”. Как вы можете заметить, анализируя алгоритм, его работа начинается с того, что на первом шаге цикла он выполняет проверку на наличие строки “/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

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

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

читать СТАРЫЙ_КОД

вывести СТАРЫЙ_КОД

СИМВОЛ = СТАРЫЙ_КОД

WHILE входной поток не пуст DO

читать НОВЫЙ_КОД

IF NOT в таблице перевода НОВЫЙ_КОД THEN

СТРОКА = перевести СТАРЫЙ_КОД

СТРОКА = СТРОКА+СИМВОЛ

ELSE

СТРОКА = перевести НОВЫЙ_КОД

END of IF

вывести СТРОКУ

СИМВОЛ = первый символ СТРОКИ

добавить в таблицу перевода СТАРЫЙ_КОД+СИМВОЛ

СТАРЫЙ_КОД = НОВЫЙ_КОД

END of WHILE

Входные коды : / 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

Концепции, использованные в алгоритме сжатия, настолько просты, что весь алгоритм может быть записан в несколько строк. Но так как управление построением таблицы требует некоторых специальных действий, реализация несколько более сложна. В демонстрационной программе, приведенной ниже, использовались коды длиной 12, 13 и 14 бит. При длине кода 12 бит потенциально возможно хранить до 4096 строк в таблице. Каждый раз, когда читается новый символ, таблица строк должна просматриваться для сопоставления. Если сопоставление не найдено, новая строка должна быть добавлена в таблицу.

Здесь возникают две проблемы. Во-первых, таблица строк может достаточно быстро стать очень большой. Даже если длина строк в среднем ограничивается 3 или 4 символами каждая, верхний предел длин строк может легко превысить 7 или 8 байт на код. К тому же количество памяти, необходимой для хранения строк, заранее не известно, так как оно зависит от общей длины строк. Вторая проблема заключается в организации поиска строк. Каждый раз, когда читается новый символ, необходимо организовать поиск для новой строки вида СТРОКА+СИМВОЛ. Это означает поддержку отсортированного списка строк. В этом случае поиск для каждой строки включает число сравнений порядка log2 от общего числа строк.

Использование 12-битных слов потенциально позволяет выполнять не более 12 сравнений для каждого кода. Первая проблема может быть решена хранением строк как комбинаций код/символ. Так как каждая строка в действительности является представлением комбинации уже существующего кода и добавочного символа, можно хранить каждую строку как отдельный код плюс символ. Например в разобранном выше примере строка “/WEE” хранится как код 260 и символ “E”. Это позволяет использовать для хранения только 3 байта вместо 5 (включающих дополнительный байт для конца строки). Идя назад, можно определить, что код 260 хранится как код 256 плюс добавочный символ “E”. Наконец, код 256 хранится как “/” плюс “W”.

Выполнение сравнения строк является немного более трудным. Новый метод хранения увеличивает время, необходимое для сравнения строк, но он не влияет на число сравнений. Эта проблема решается использованием алгоритма хэширования для хранения строк. Это означает, что код 256 не хранится в каком-либо массиве по адресу 256, а хранится в массиве по адресу, сформированному на основе самой строки. При определении места хранения данной строки можно использовать тестовую строку для генерации хэшадреса и затем найти целевую строку однократным сравнением. Так как код для любой данной строки нельзя узнать в дальнейшем иначе как по его позиции в массиве, необходимо хранить код для данной строки совместно с данными строки.