Изменения

*буфер поиска (словарь) хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева поиска]];*метки имеют два поля, а не три.

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

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

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

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

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

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

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

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

'''Таблицы 1 и 2. Строки по пять символов.'''  Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, нашем примере длина совпадения может быть равна <mathtex>L-12</mathtex> .) В нашем примере длина совпадения равна 2, поэтому кодер выдает метку <mathtex>\langle</mathtex><mathtex>16,2</mathtex><mathtex>\rangle</mathtex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

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

# Считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» "старые" строки из словаря.

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

(В данном примере один символ кодируется восемью битами).Поэтому после префикса <tex>0</tex> декодер считывает следующие <tex>8</tex> бит.После префикса <tex>1</tex> хранится пара <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex>. Так как смещение и длина не превосходят длины словаря, то размер пары <tex>\langle</tex><tex>offset,length</tex><tex>\rangle</tex> равен удвоенному количеству бит, требуемых для хранения длины словаря.Длина словаря в данном примере <tex>8</tex>. Поэтому после префикса <tex>1</tex> декодер считывает <tex>6</tex> бит. 

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

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