Алгоритм 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
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

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

Первым символом в буфере, содержащем еще не закодированные символы, является 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).

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

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

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

Кодер LZSS

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

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

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

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

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

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

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

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

Закодировать по алгоритму 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, длина словаря — 8 байт (символов). Коды сжатого сообщения —

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

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

См.также

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

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

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

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

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

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