Изменения

Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям: упреждающий *буфер сохранялся , содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди]], *буфер поиска (словарь) хранился хранитсяся в виде [http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0 [Дерево поиска, наивная реализация|двоичного дерева поиска] и ]*метки имели имеют два поля, а не три.

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

Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность. ===Организация поиска в словаре=== Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части размером длины буфера. ====Порядок изменения дерева поиска====Кодер изучает буфер поиска, создавая <tex>T </tex> строк с числом символов <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.На дереве все время находится одинаковое число <tex>T </tex> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <tex>T=S-L+1</tex>. Если во время кодирования случается совпадение длины <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". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из <tex>16</tex>-байтного буфера поиска и <tex>5</tex>-байтного буфера, содержащего еще не закодированные символы. После ввода первых <tex>16+5</tex> символов скользящее окно выглядит так: {| class="wikitable" |style="background:#FFCC00" |sid_eastman_clum |style="background:#FFCC00"|sily_ |teases_sea_sick_seals |}   причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе. Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями. '''Таблицы 1 и 2. Строки по пять символов.'''{| |{| class="wikitable" ! colspan="2" |Таблица 1 |- | sid_e |16 |- |id_ea |15 |- |d_eas |14 |- |_east |13 |- |eastm |12 |- |astma |11 |- |stmаn |10 |- |tman_ |09 |- |man_c |08 |- |an_cl |07 |- |n_clu |06 |- |_clum |05 |} | || |{| class="wikitable" ! colspan="2" |Таблица 2 |- |d_eas |16 |- |_east |15 |- |eastm |14 |- |astma |13 |- |stmаn |12 |- |tman_ |11 |- |man_c |10 |- |an_cl |09 |- |n_clu |08 |- |_clum |07 |- | clums |06 |- | lumsi |05 |}|} Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <tex>L-1</tex>. В нашем примере длина совпадения равна <tex>2</tex>, поэтому кодер выдает метку <tex>\langle</tex><tex>16,2</tex><tex>\rangle</tex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом: {| class="wikitable" |si |style="background:#FFCC00"|d_eastman_clumsi |style="background:#FFCC00"|ly_te |ases_sea_sick_seals |} С дерева необходимо удалить строки 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" для кодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении.== Модель данных ==Как и Такая техника позволяет записывать символы в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]]явном виде, в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности «скольжения» окна по содержимому сообщения доступ к нему организован как к кольцевомукогда соответствующий им код имеет большую длину, и размер окна кратен степени двойкиа также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

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

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

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

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