Изменения

Эта версия [[Алгоритмы LZ77 и LZ78|алгоритма LZ77]] была разработана Сторером (''Storer'') и Сжимански (''Szymanski'') в 1982. Базовый алгоритм был улучшен по трем направлениям: упреждающий *буфер сохранялся , содержащий еще не закодированные символы, сохраняется в циклической [[Очередь|очереди, ]]*буфер поиска (словарь) хранился хранитсяся в виде [[Дерево поиска, наивная реализация|двоичного дерева двоичного поиска и ]]*метки имели имеют два поля, а не три.

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

Кодер LZSS использует однобитовый префиксРазмер циклического буфера равен степени двойки, и стандартная для того чтобы отличать незакодированные символы от пар <циклического буфера операция "смещениепо модулю размер", длина>. Такие коды позволяют получить существенный выигрыш в размере сжатого сообщенияможет быть заменена побитовой логической операцией, что еще больше повышает эффективность.

Скорость кодирования [[Алгоритмы 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" для хранения содержимого окнакодовых комбинаций), значение которого определяет, является ли следующая за ним кодовая комбинация кодовой парой или она представляет собой незакодированный символ в его исходном представлении. В целях повышения эффективности «скольжения» окна по содержимому сообщения доступ к нему организован как к кольцевомуТакая техника позволяет записывать символы в явном виде, когда соответствующий им код имеет большую длину, и размер окна кратен степени 2а также позволяет обрабатывать ни разу не встреченные до текущего момента символы.

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

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

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

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

Так как алгоритм LZSS не является запатентованным, он широко используется. LZSS можно удачно скомбинировать с методами сжатия, основанными на переменной длине кода ([[Алгоритм Хаффмана]], алгоритм Шеннона-Фано(''Shannon-Fano''))

== Литература См.также ==* [[Алгоритмы LZ77 и LZ78]]* [[Алгоритм LZW]] == Источники информации ==

==Ссылки==* Лидовский В.В. Теория информации: учебное пособие. – Москва: 2003. – 112 с., с. 37-38.