Алгоритм LZSS
Эта версия алгоритма LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982. Базовый алгоритм был улучшен по трем направлениям:буфер, содержащий еще не закодированные символы, сохранялся в циклической очереди, буфер поиска (словарь) хранился в виде двоичного дерева поиска и метки имели два поля, а не три.
Содержание
Оптимизации
В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу (как внутреннему, так и листовому) соответствует определенная строка словаря длины М (максимальная длина совпадения). Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк. Такая организация модели данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от алгоритма LZ77, становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.
Проблема отсутствия совпадений в словаре решается путем введения дополнительного служебного бита, значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении.
Модель данных
Как и в алгоритме LZ77, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части. Размер окна кратен степени двойки.
Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
Кодер LZSS
Инициализация
Для того чтобы кодер мог начать работать, необходимо загрузить буфер очередными символами сообщения и проинициализировать дерево. Для этого в дерево вставляется содержимое буфера.
Основной цикл работы
Алгоритм последовательно выполняет следующие действия:
- кодирует содержимое буфера;
- считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» строки из словаря;
- вставляет в дерево новые строки, соответствующие считанным символам.
Завершение работы
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
Пример кодирования
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
Декодер LZSS
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара <смещение, длина>. Если это символ, то следующие бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
Пример декодирования
LZSS, длина словаря — 8 байт (символов). Коды сжатого сообщения —
Практическое использование алгоритма LZSS
Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода (Алгоритм Хаффмана, алгоритм Шеннона-Фано (Shannon-Fano)) например в PKZIP V.1.0 использован LZSS в комбинации с алгоритмом Шеннона-Фано, а в ARJ — LZSS с алгоритмом Хаффмана.
Источники информации
- Д.Сэломон. Сжатие данных, изображений и звука - Москва: Техносфера, 2004. - с.368, стр. 88.
- Семенюк В. В. Экономное кодирование дискретной информации. – СПб.: СПбГИТМО (ТУ), 2001. – 115 с., стр.60-62.
