Изменения

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

Быстродействие кодера [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. Если искать совпадение полным перебором всех возможных вариантов, то очевидно, что сжатие будет очень медленным. Поэтому в LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу (как внутреннему, так и листовому) соответствует определенная строка словаря длины <math>M</math> (максимальная длина совпадения). Поиск осуществляется путем последовательного сравнения кодируемой строки со строками, соответствующими узлам дерева, проходимым при движении по дереву от корневого узла до некоторого листового узла.Направление движения всегда определяется лексикографическим отношением сравниваемых строк. В процессе кодирования дерево поиска трансформируется. Трансформация производится посредством удаления и добавления строк. Такая организация модели == Модель данных позволяет добиться существенного увеличения скорости поиска совпадения, которая, в отличие от [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]], становится пропорциональна не произведению размеров окна и подстроки, а его двоичному логарифму. Это позволяет экспериментировать с большими окнами, не теряя скорости сжатия.==

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

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

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

Если во время кодирования случается совпадение длины <tex>k</tex>, то дерево надо перестроить путем удаления <tex>k</tex> строк и добавления <tex>k</tex> строк. Удаляться будут первые <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> байт (символов). Коды сжатого сообщения —