Изменения

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

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

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

Дерево поиска, как упоминалось выше, представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.===Порядок изменения дерева Организация поискав словаре===Кодер изучает буфер поиска, создавая <math>T </math> строк с числом символов <math>L</math> , которые помещены на двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <math>T=S-L+1</math>.

Если во время Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве случается совпадение хранятся все подстроки словарной части размером длины буфера. ====Порядок изменения дерева поиска====Кодер изучает буфер поиска, создавая <tex>T </tex> строк с числом символов <mathtex>kL</mathtex>, то которые помещены в двоичное лексикографически упорядоченное дерево надо перестроить путем удаления поиска вместе с их смещениями.На дереве все время находится одинаковое число <mathtex>kT </mathtex> узлов или строк , поскольку при его обновлении удаляется и добавляется одно и добавления то же число строк, <mathtex>kT=S-L+1</mathtex> строк.

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

Удаляться будут первые <tex>k</tex> строк буфера поиска до его сдвига, а добавляться будут последние <tex>k</tex> строк этого буфера после сдвига. Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <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><tex>16,2<math/tex><tex>\rangle</mathtex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:

|style="background:#FFCC00"|ly_te_ly_te

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi(см.табл.2).Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.В данном примере длина буфера {{---}} <tex>5</tex> символов, часть совпадения {{---}} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа. ===Оптимизация памяти=== У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма. Метка LZSS состоит только из смещения и длины. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением "0" для незакодированных символов и "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>смещение<tex>offset, длинаlength</tex><mathtex>\rangle</mathtex>. Если это символ, то следующие <mathtex>8</mathtex> бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.

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