Изменения
→Модель данных
===Реализация "скольжения"===
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]],в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
===Организация поиска в словаре===
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <mathtex>M</mathtex> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
====Порядок изменения дерева поиска====
Кодер изучает буфер поиска, создавая <mathtex>T </mathtex> строк с числом символов <mathtex>L</mathtex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <mathtex>T=S-L+1</mathtex>.
Если во время кодирования случается совпадение длины <mathtex>k</mathtex>, то дерево надо перестроить путем удаления <mathtex>k</mathtex> строк и добавления <mathtex>k</mathtex> строк.
Удаляться будут первые <math>k</math> строк буфера поиска до его сдвига, а добавляться будут последние <math>k</math> строк этого буфера после сдвига.
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <mathtex>L</mathtex> символов буфера поиска и добавить ее на дерево. Это следует повторить <mathtex>k</mathtex> раз.
Для определения смещения уславливаемся, что:
====Пример====
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals»"sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного буфера, содержащего еще не закодированные символы. После ввода первых <mathtex>16+5</mathtex> символов скользящее окно выглядит так:
{| class="wikitable"
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <mathtex>12=16-5+1</mathtex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
{|
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку <mathtex>\langle</mathtex><mathtex>16,2</mathtex><mathtex>\rangle</mathtex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
{| class="wikitable"
У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма.
Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением «0» "0" для незакодированных символов и «1» "1" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Такая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.
== Кодер LZSS ==
