Алгоритм LZW

Название алгоритм получил по первым буквам фамилий его разработчи­ков - Lempel, Ziv и Welch. Сжатие в нем, в отличие от RLE, осуществляется уже за счет одинаковых цепочек байтов. Алгоритм LZW является самым из­вестным представителем семейства словарных методов LZ78 (см. гл. 3 под-разд. 1).

Алгоритм LZ

Существует довольно большое семейство LZ-подобных алгоритмов, раз­личающихся, например, методом поиска повторяющихся цепочек. Один из достаточно простых вариантов этого алгоритма, например, предполагает, что в выходном потоке идет либо пара <длина совпадения, смещение отно­сительно текущей позиции>, либо просто <длина совпадения> "пропуска­емых" байтов и сами значения байтов (как во втором варианте алгоритма RLE). При разжатии для пары <длина совпадения, смещение> копируются <длина совпадения> байт из выходного массива, полученного в результате разжатия, на <смещение> байт раньше, а <длина совпадения> (т. е. число, равное длина совпаденияу) значений "пропускаемых" байтов просто копи­руются в выходной массив из входного потока. Данный алгоритм является несимметричным по времени, поскольку требует полного перебора буфера (скользящего окна) при поиске одинаковых подстрок. В результате нам сложно задать большой буфер из-за резкого возрастания времени компрес­сии. Однако потенциально построение алгоритма, в котором на <длина сов-падения> и на <смещение> будет выделено по 2 байта (старший бит стар­шего байта длины совпадения - признак повтора строки / копирования по­тока), даст нам возможность сжимать все повторяющиеся подстроки размером до 32Кб в буфере размером 64Кб.

При этом мы получим увеличение размера файла в худшем случае на 32770/32768 (в 2 байтах записано, что нужно переписать в выходной поток следующие 2¹⁵ байт), что совсем неплохо. Максимальная степень сжатия составит в пределе 8192 раза. В пределе, поскольку максимальное сжатие мы получаем, превращая 32 Кб буфера в 4 байта, а буфер ("словарь" в тер­минах LZ) такого размера мы накопим не сразу. Однако минимальная под­строка, для которой нам выгодно проводить сжатие, должна состоять в об­щем случае минимум из 5 байт, что и определяет малую ценность данного алгоритма. К достоинствам этого варианта LZ можно отнести чрезвычай­ную простоту алгоритма декомпрессии.

Упражнение. Предложите другой вариант алгоритма LZ, в котором на пару <счетчик, смещение> будет выделено 3 байта, и подсчитайте основные харак­теристики своего алгоритма.

Алгоритм LZW

Рассматриваемый нами ниже вариант алгоритма будет использовать де­рево для представления и хранения цепочек (фраз словаря в терминах разд. 1). Очевидно, что это достаточно сильное ограничение на вид цепочек и далеко не все одинаковые подцепочки в нашем изображении будут ис­пользованы при сжатии. Однако в предлагаемом алгоритме выгодно сжи­мать даже цепочки, состоящие из 2 байт.

Процесс сжатия выглядит достаточно просто. Мы считываем последова­тельно символы входного потока и проверяем, есть ли в созданной нами таблице строк такая строка. Если строка есть, то мы считываем следующий символ, а если строки нет, то мы заносим в поток код для предыдущей най­денной строки, заносим строку в таблицу и начинаем поиск снова.

Функция InitTable() очищает таблицу и помещает в нее все строки еди­ничной длины.

InitTableO;

CoinpressedFile. WriteCode (ClearCode) ;

CurStr=nycTaH строка;

while (не ImageFile.EOFO){ //Пока не конец файла

C=ImageFile.ReadNextByte(); if(CurStr+C есть в таблице)

CurStr=CurStr+C;//Приклеить символ к строке else {

code=CodeForString(CurStr);//code-не байт!
CompressedFile.WriteCode(code);
AddStringToTable (CurStr+C);
CurStr=C; // Строка из одного символа

) }

code=CodeForString(CurStr) ; CompressedFile.WriteCode(code) ; CompressedFile.WriteCode(CodeEndOfInformation);

Как говорилось выше, функция InitTable() инициализирует таблицу строк так, чтобы она содержала все возможные строки, состоящие из одного символа. Например, если мы сжимаем байтовые данные, то таких строк в таблице будет 256 ("О", "1",..., "255"). Для кода очистки (ClearCode) и кода конца информации (CodeEndOflnfonnation) зарезервированы значения 256 и 257. В рассматриваемом варианте алгоритма используется 12-битовый код, и, соответственно, под коды для строк нам остаются значения от 258 до 4095. Добавляемые строки записываются в таблицу последовательно, при этом индекс строки в таблице становится ее кодом.

Функция ReadNextByte() читает символ из файла. Функция WriteCode() записывает код (не равный по размеру байту) в выходной файл. Функция AddStringToTable () добавляет новую строку в таблицу, приписывая ей код. Кроме того, в данной функции происходит обработка ситуации переполне­ния таблицы. В этом случае в поток записывается код предыдущей найден­ной строки и код очистки, после чего таблица очищается функцией InitTable(). Функция CodeForStringO находит строку в таблице и выдает код этой строки.

Пример

Пусть мы сжимаем последовательность 45, 55, 55, 151, 55, 55, 55. Тогда, согласно изложенному выше алгоритму, мы поместим в выходной поток сначала код очистки <256>, потом добавим к изначально пустой строке "45" и проверим, есть ли строка "45" в таблице. Поскольку мы при инициализа­ции занесли в таблицу все строки длиной в один символ, то строка "45" есть в таблице. Далее мы читаем следующий символ 55 из входного потока и проверяем, есть ли строка "45, 55" в таблице. Такой строки в таблице пока нет. Мы заносим в таблицу строку "45, 55" (с первым свободным кодом 258) и записываем в поток код <45>. Можно коротко представить архивацию так:

"45" - есть в таблице;

"45, 55" - нет. Добавляем в таблицу <258>"45, 55". В поток: <45>;

"55, 55" - нет. В таблицу: <259>"55,55". В поток: <55>;

"55,151" - нет. В таблицу: <260>"55, 151". В поток: <55>;

"151,55" - нет. В таблицу: <261>"151,55". В поток: <151>;

"55, 55" - есть в таблице;

"55,55,55" - нет. В таблицу: "55,55, 55" <262>. В поток: <259>.

Последовательность кодов для данного примера, попадающих в выход­ной поток: <256>, <45>, <55>, <55>, <151>, <259>.

Особенность LZW заключается в том, что для декомпрессии нам не надо сохранять таблицу строк в файл для распаковки. Алгоритм построен таким образом, что мы в состоянии восстановить таблицу строк, пользуясь только потоком кодов.

Мы знаем, что для каждого кода надо добавлять в таблицу строку, со­стоящую из уже присутствующей там строки и символа, с которого начина­ется следующая строка в потоке.

Код этой строки добавляется в таблицу

Коды этих строк идут в выходной поток

Алгоритм декомпрессии, осуществляющий эту операцию, выгладит сле­дующим образом:

code=File.ReadCode() ; while(code != CodeEndOflnformation){ if(code == ClearCode) { InitTableO; code=File.ReadCode(); }

if (code == CodeEndOflnformation) { закончить работу; } else {

if(InTable(code)) {

ImageFile.WriteString(FromTable(code)); AddStringToTable(StrFromTable(old_code)+

FirstChar(StrFromTable(code))); old_code=code; } else {

OutString= StrFromTable(old_code)+

FirstChar(StrFromTable(old_code)); ImageFile.WriteString(OutString); AddStringToTable(OutString); old_code=code; } )

code=File.ReadCode(); )

Здесь функция ReadCode() читает очередной код из декомпрессируемого файла. Функция InitTable() выполняет те же действия, что и при компрес­сии, т. е. очищает таблицу и заносит в нее все строки из одного символа. Функция FirstChar() выдает нам первый символ строки. Функция StrFrom Table() выдает строку из таблицы по коду. Функция AddStringToTableO до­бавляет новую строку в таблицу (присваивая ей первый свободный код). Функция WriteStringO записывает строку в файл.

3i Замечание 1. Как вы могли заметить, записываемые в поток коды посте­пенно возрастают. До тех пор пока в таблице не появится, например, в первый раз код 512, все коды будут меньше 512. Кроме того, при компрессии и при де­компрессии коды в таблице добавляются при обработке одного и того же сим­вола, т. е. это происходит "синхронно". Мы можем воспользоваться этим свойством алгоритма для того, чтобы повысить степень компрессии. Пока в таблицу не добавлен 512-й символ, мы будем писать в выходной битовый поток коды из 9 бит, а сразу при добавлении 512 - коды из 10 бит. Соответственно декомпрессор также должен будет воспринимать все коды входного потока 9-битовыми до момента добавления в таблицу кода 512, после чего будет вос-

295

Методы сжатия данных принимать все входные коды как ]0-битовые. Аналогично мы будем поступать при добавлении в таблицу кодов 1024 и 2048. Данный прием позволяет примерно на 15% поднять степень компрессии:

Заметим также, что реально нам достаточно хранить в таблице только пару <код предыдущей подстроки, добавленный символ>. Этой информации вполне достаточно для работы алгоритма. Таким образом, массив от 0 до 4095 с элементами <код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки> решает поставленную задачу поиска, хотя и очень медленно.

На практике для хранения таблицы используется такое же быстрое, как в случае списков, но более компактное по памяти решение - хеш-таблица. Табли­ца состоит из 8192 (2^й) элементов. Каждый элемент содержит <код преды­дущей подстроки; добавленный символ; код этой строки>. Ключ для поиска длиной 20 бит формируется с использованием двух первых элементов, хранимых в таблице как одно число (key). Младшие 12 бит этого числа отданы под код, а следующие 8 бит под значение символа. В качестве хеш-функции при этом используется

Index(key)= ((key » 12) ^л key) S 8191;

где » - побитовый сдвиг вправо (key » 12-мы получаем значение символа); ^л-логическая операция побитового исключающего ИЛИ; Алогическое побито­вое И.

Таким образом, за считанное количество сравнений мы получаем искомый код или сообщение, что такого кода в таблице нет.

Подсчитаем лучшую и худшую степень сжатия для данного алгоритма. Лучшее сжатие, очевидно, будет получено для цепочки одинаковых байт большой длины (т. с. для 8-битового изображения, все точки которого име­ют, для определенности, цвет 0). При этом в 258 строку таблицы мы запи шем строку "О, 0", в 259 - "О, О, О", ... в 4095 - строку из 3839 (=4095-256) нулей. При этом в поток попадет (проверьте по алгоритму!) 3840 кодов, включая код очистки. Следовательно, посчитав сумму арифметической про­грессии от 2 до 3839 (т. е. длину сжатой цепочки) и поделив ее на 3840*12/8 (в поток записываются 12-битовые коды), мы получим лучшую степень сжатия.

Упражнение. Вычислить точное значение лучшей степени сжатия. Более сложное задание: вычислить ее с учетом замечания 1.

Худшее сжатие будет получено, если мы ни разу не встретим подстроку, которая уже есть в таблице (в ней не должно встретиться ни одной одинако­вой пары символов).

Упражнение. Составить алгоритм генерации таких цепочек.

В случае, если мы постоянно будем встречать новую подстроку, мы за­пишем в выходной поток 3840 кодов, которым будет соответствовать строка из 3838 символов. Без учета замечания 1 это составит увеличение файла почтив 1.5 раза.

LZW реализован в форматах GIF и TIFF.

Характеристики алгоритма LZW:

Степени сжатия: примерно 1000, 4, 5/7 (лучшее, среднее, худшее | сжатие). Сжатие в 1000 раз достигается только на одноцветных изобра-| жениях размером кратным примерно 7 Мб. (Почему 7 Мб - становится I понятно при расчете наилучшей степени сжатия.)

Класс изображений: ориентирован LZW на 8-битовые изображения, | построенные на компьютере. Сжимает за счет одинаковых подцепочек ! в потоке.

Симметричность: почти симметричен, при условии оптимальной реали-\ зации операции поиска строки в таблице.

Характерные особенности: ситуация, когда алгоритм увеличивает ; изображение, встречается крайне редко. Универсален.