Алгоритм LZSS
Эта версия алгоритма LZ77 была разработана Сторером (Storer) и Сжимански (Szymanski) в 1982. Базовый алгоритм был улучшен по трем направлениям:
- буфер, содержащий еще не закодированные символы, сохраняется в циклической очереди
- буфер поиска (словарь) хранитсяся в виде двоичного дерева поиска
- метки имеют два поля, а не три
Содержание
Модель данных
Реализация "скольжения"
Как и в алгоритме LZ77,в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
Организация поиска в словаре
Скорость кодирования LZ77 сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
Порядок изменения дерева поиска
Кодер изучает буфер поиска, создавая строк с числом символов , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями. На дереве все время находится одинаковое число узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, .
Если во время кодирования случается совпадение длины , то дерево надо перестроить путем удаления строк и добавления строк.
Удаляться будут первые строк буфера поиска до его сдвига, а добавляться будут последние строк этого буфера после сдвига.
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних символов буфера поиска и добавить ее на дерево. Это следует повторить раз.
Для определения смещения уславливаемся, что:
- нулевое смещение зарезервировали для обозначения конца кодирования;
- если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.
Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.
Пример
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного буфера, содержащего еще не закодированные символы. После ввода первых символов скользящее окно выглядит так:
| sid_eastman_clum | sily_ | teases_sea_sick_seals |
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как ), которые помещены на двоичное дерево поиска вместе с их смещениями.
|
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||
Таблицы 1 и 2. Строки по пять символов.
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть .)
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку . Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
| 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 строку "КРАСНАЯ КРАСКА". (В данном примере один символ кодируется восемью битами).
Декодер LZSS
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара . Если это символ, то следующие бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
Пример декодирования
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.
