Алгоритм LZSS

Эта версия алгоритма LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982. Базовый алгоритм был улучшен по трем направлениям:

• буфер, содержащий еще не закодированные символы, сохраняется в циклической очереди
• буфер поиска (словарь) хранитсяся в виде двоичного дерева поиска
• метки имеют два поля, а не три

Модель данных

Реализация "скольжения"

Как и в алгоритме LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.

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

Организация поиска в словаре

Скорость кодирования LZ77 сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины [math]M[/math] (максимальная длина совпадения). В дереве хранятся все подстроки словарной части размером длины буфера.

Порядок изменения дерева поиска

Кодер изучает буфер поиска, создавая [math]T [/math] строк с числом символов [math]L[/math] , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями. На дереве все время находится одинаковое число [math]T [/math] узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, [math]T=S-L+1[/math].

Если во время кодирования случается совпадение длины [math]k[/math], то дерево надо перестроить путем удаления [math]k[/math] строк и добавления [math]k[/math] строк.

Удаляться будут первые [math]k[/math] строк буфера поиска до его сдвига, а добавляться будут последние [math]k[/math] строк этого буфера после сдвига.

Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних [math]L[/math] символов буфера поиска и добавить ее на дерево. Это следует повторить [math]k[/math] раз.

Для определения смещения уславливаемся, что:

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

Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.

Пример

Пусть входной файл содержит следующую последовательность: "sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из [math]16[/math]-байтного буфера поиска и [math]5[/math]-байтного буфера, содержащего еще не закодированные символы. После ввода первых [math]16+5[/math] символов скользящее окно выглядит так:

sid_eastman_clum

sily_

teases_sea_sick_seals

причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.

Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как [math]12=16-5+1[/math]), которые помещены на двоичное дерево поиска вместе с их смещениями.

Таблицы 1 и 2. Строки по пять символов.

Таблица 1 sid_e 16 id_ea 15 d_eas 14 _east 13 eastm 12 astma 11 stmаn 10 tman_ 09 man_c 08 an_cl 07 n_clu 06 _clum 05

Таблица 2 d_eas 16 _east 15 eastm 14 astma 13 stmаn 12 tman_ 11 man_c 10 an_cl 09 n_clu 08 _clum 07 clums 06 lumsi 05

Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями [math]16[/math] и [math]10[/math], но первая из них, sid_e, имеет более длинное совпадение. Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть [math]L-1[/math].

В нашем примере длина совпадения равна [math]2[/math], поэтому кодер выдает метку [math]\langle[/math][math]16,2[/math][math]\rangle[/math]. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

si

d_eastman_clumsi

ly_te

ases_sea_sick_seals

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2). Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения. В данном примере длина буфера — [math]5[/math] символов, часть совпадения — [math]2[/math] символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит [math]2[/math]. Это смещения [math]5[/math] и [math]6[/math]. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.

Оптимизация памяти

У алгоритма LZ77 возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма.

Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением "0" для незакодированных символов и "1" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

Кодер LZSS

Инициализация

Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.

Основной цикл работы

Алгоритм последовательно выполняет следующие действия:

1. Кодирует содержимое буфера.
2. Считывает очередные символы в буфер, удаляя при необходимости наиболее "старые" строки из словаря.
3. Вставляет в дерево новые строки, соответствующие считанным символам.

Завершение работы

Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения.

Пример кодирования

Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА". В данном примере один символ кодируется восемью битами. Поэтому после префикса [math]0[/math] декодер считывает следующие [math]8[/math] бит. После префикса [math]1[/math] хранится пара [math]\langle[/math][math]offset,length[/math][math]\rangle[/math]. Так как смещение и длина не превосходят длины словаря, то размер пары [math]\langle[/math][math]offset,length[/math][math]\rangle[/math] равен удвоенному количеству бит, требуемых для хранения длины словаря. Длина словаря в данном примере [math]8[/math]. Поэтому после префикса [math]1[/math] декодер считывает [math]6[/math] бит.

Декодер LZSS

Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.

Декодер читает один бит сжатой информации и решает — это символ или пара [math]\langle[/math][math]offset,length[/math][math]\rangle[/math]. Если это символ, то следующие [math]8[/math] бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

Пример декодирования

LZSS, длина словаря — [math]8[/math] байт (символов). Коды сжатого сообщения —

Практическое использование алгоритма LZSS

Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода (Алгоритм Хаффмана, алгоритм Шеннона-Фано (Shannon-Fano)) например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в ARJ — LZSS с алгоритмом Хаффмана.

См.также

• Алгоритмы LZ77 и LZ78
• Алгоритм LZW

Источники информации

• Д.Сэломон. Сжатие данных, изображений и звука - Москва: Техносфера, 2004. - с.368, стр. 88.

• Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. – 115 с., стр.60-62.

• Лидовский В.В. Теория информации: учебное пособие. – Москва: 2003. – 112 с., с. 37-38.

• Обзор алгоритмов сжатия без потерь. Алгоритм LZSS

• Подстановочные или словарно-ориентированные алгоритмы сжатия информации. Методы Лемпела-Зива