Изменения

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

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

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

У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Если словарь имеет длину 4 Кб, а буфер — 16 байтов, то код<math>\langle</math> 0, 0, символ<math>\rangle</math> будет занимать 3 байта. Кодирование одного байта в три имеет мало общего со сжатием и существенно понижает производительность алгоритма. Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением «0» для незакодированных символов и «1» для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

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

Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]], в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения используется циклический буфер, размер которого

Дерево поиска, как упоминалось выше, представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.

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

Кодер изучает буфер поиска, создавая <math>T </math> строк с числом символов <math>L</math> , которые помещены на двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.

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

===Пример===

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

|}

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi.

== Кодер LZSS ==

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

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

Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".

(В данном примере один символ кодируется восемью битами).