Изменения

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

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

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

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

У алгоритма Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляютсясильно зависит от того, когда кодер не может найти совпадающую подстроку каким образом осуществляется поиск совпадающей подстроки в словаре и выдает стандартный 3-компонентный код. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, пытаясь закодировать один символв котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). Если словарь имеет длину 4 Кб, а В дереве хранятся все подстроки словарной части размером длины буфера. ====Порядок изменения дерева поиска====Кодер изучает буфер — 16 байтовпоиска, то кодсоздавая <mathtex>\langleT </mathtex> 0, 0, символстрок с числом символов <mathtex>\rangleL</mathtex> будет занимать 3 байта. Кодирование одного байта , которые помещены в три имеет мало общего со сжатием и существенно понижает производительность алгоритмадвоичное лексикографически упорядоченное дерево поиска вместе с их смещениями. Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (со значением «0» для незакодированных символов и «1» для кодовых комбинаций)На дереве все время находится одинаковое число <tex>T </tex> узлов или строк, значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в поскольку при его исходном представлении. Такая техника позволяет записывать символы в явном видеобновлении удаляется и добавляется одно и то же число строк, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы<tex>T=S-L+1</tex>.

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

Дерево Удаляться будут первые <tex>k</tex> строк буфера поискадо его сдвига, как упоминалось выше, представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных а добавляться будут последние <tex>k</tex> строкэтого буфера после сдвига. Покажем на примере, как двоичное дерево способно ускорить поиск в словаре.===Пример===

Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <tex>L</tex> символов буфера поиска и добавить ее на дерево. Это следует повторить <tex>k</tex> раз. Для определения смещения уславливаемся, что:* нулевое смещение зарезервировали для обозначения конца кодирования; * если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.  Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь. ====Пример====Пусть входной файл содержит следующую последовательность: «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. Строки по пять символов.'''{| |

'''Табл. Строки по пять символов.''' На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число <math>T </math> равно: длина буфера поиска минус длина буфера,содержащего еще не закодированные символы, плюс 1 <math>(T=S-L+1)</math>. Первым символом в буфере, содержащем еще не закодированные символы, является 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> символов, часть совпадения {{---}} <mathtex>k2</mathtex>символа, то дерево надо было бы перестроить путем удаления поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <mathtex>k2</mathtex>. Это смещения <tex>5</tex> строк и добавления <mathtex>k6</mathtex> строк. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.

Простейшая процедура обновления дерева У алгоритма [[Алгоритмы LZ77 и LZ78|LZ77]] возникают проблемы с самим сжатием. Они появляются, когда кодер не может найти совпадающую подстроку в словаре и выдает стандартный 3-компонентный код, пытаясь закодировать один символ. Такое кодирование существенно понижает производительность алгоритма. Метка LZSS состоит в приготовлении строк только из начала буфера, их поиска смещения и удалениядлины. Потом необходимо сдвинуть буфер на одну позицию вправо Проблема отсутствия совпадений в словаре в алгоритме LZSS решается путем введения дополнительного служебного бита (или переместить данные на одну позицию влевосо значением "0" для незакодированных символов и "1" для кодовых комбинаций), приготовить строку из последних 5 символов буфера поиска и добавить ее на деревозначение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. Это следует повторить <math>k</math> разТакая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

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

Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» "КОНЕЦ ФАЙЛА" после того, как он обработал все символы сообщения. ===Добавление новой строки в дерево===Вся работа по поиску расположения и установлению длины максимального совпадения содержимого словаря с буфером происходит в процессе добавления в дерево новой строки. При добавлении строки в дерево алгоритм последовательно перемещается от корня дерева к его листу, каждый раз осуществляя лексикографическое сравнение новой строки и узла дерева. В зависимости от результата сравнения выбирается больший или меньший потомок этого узла и запоминается длина совпадения строк и положение текущего узла. Если в результате сравнения оказывается, что содержимое буфера и строка, на которую ссылается текущий узел, в точности совпадают, то ссылки в текущем узле обновляются так, чтобы они указывали на буфер, и процедура добавления строки в дерево завершается. Если потомок текущего узла, выбранный для очередного шага, отмечен как несуществующий, остается заполнить его соответствующей ссылкой и завершить работу. Нужно отметить, что при окончании работы процедуре добавления строки известны и смещение, и длина наибольшего совпадения, и для этого не потребовался полный перебор всех возможных вариантов совпадения. ===Удаление строки из дерева===При удалении узла из дерева возможны два варианта. Если узел имеет не более одного потомка, то удаление узла осуществляется простым исправлением ссылок “родитель-потомок”. Если узел имеет два потомка, то необходимы другие действия: найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего потомка и последующим перемещением от него по дереву до листа по большим ветвям.

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

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