1632
правки
Изменения
м
'''Таблицы 1 и 2. Строки по пять символов.''' Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16 </tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
(В данном примере один символ кодируется восемью битами).Поэтому после префикса <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> бит.
rollbackEdits.php mass rollback
===Реализация "скольжения"===
Как и в [[Алгоритмы LZ77 и LZ78|алгоритме LZ77]],в этом алгоритме используется обычный символьный буфер для хранения содержимого окна. В целях повышения эффективности "скольжения" окна по содержимому сообщения используется циклический буфер, размер которого идентичен размеру скользящего окна. Такой буфер организован на физически сплошном участке памяти, а не на реальном сдвиге содержимого окна, как в LZ77. Скольжение окна в таком буфере сводится к циклическому перемещению границы между его задней и передней частями (текущей обрабатываемой позиции) в пределах буфера. При этом добавление новой порции информации в переднюю часть окна автоматически означает удаление идентичной по длине порции из его задней части.
Размер циклического буфера равен степени двойки, и стандартная для циклического буфера операция "смещение по модулю размер", может быть заменена побитовой логической операцией, что еще больше повышает эффективность.
===Организация поиска в словаре===
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
====Порядок изменения дерева поиска====
Кодер изучает буфер поиска, создавая <tex>T </tex> строк с числом символов <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
На дереве все время находится одинаковое число <mathtex>T </mathtex> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <tex>T=S-L+1</tex>.
Если во время кодирования случается совпадение длины <tex>k</tex>, то дерево надо перестроить путем удаления <tex>k</tex> строк и добавления <tex>k</tex> строк.
Удаляться будут первые <mathtex>k</mathtex> строк буфера поиска до его сдвига, а добавляться будут последние <mathtex>k</mathtex> строк этого буфера после сдвига.
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <tex>L</tex> символов буфера поиска и добавить ее на дерево. Это следует повторить <tex>k</tex> раз.
====Пример====
Пусть входной файл содержит следующую последовательность: "sid_eastman_clumsily_teases_sea_sick_seals". Для простоты предположим, что окно (желтые ячейки в таблице) состоит из <tex>16</tex>-байтного буфера поиска и <tex>5</tex>-байтного буфера, содержащего еще не закодированные символы. После ввода первых <tex>16+5</tex> символов скользящее окно выглядит так:
{| class="wikitable"
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
'''Таблицы 1 и 2. Строки по пять символов.'''
{|
|
|}
Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <tex>L-1</tex>.
В нашем примере длина совпадения равна <tex>2</tex>, поэтому кодер выдает метку <tex>\langle</tex><tex>16,2</tex><tex>\rangle</tex>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
{| class="wikitable"
|}
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.
В данном примере длина буфера {{---}} <tex>5</tex> символов, часть совпадения {{---}} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
===Оптимизация памяти===
# Кодирует содержимое буфера.
# Считывает очередные символы в буфер, удаляя при необходимости наиболее «старые» "старые" строки из словаря.
# Вставляет в дерево новые строки, соответствующие считанным символам.
===Пример кодирования===
Закодировать по алгоритму LZSS строку "КРАСНАЯ КРАСКА".
[[Файл:540e164e73fca7dcfc2b6c970b135e24.png]]
Алгоритм LZSS, вообще говоря, является очень асимметричным. Если процедура сжатия достаточно сложна и совершает большой объем работы при обработке каждого символа сжимаемого сообщения, то декодер LZSS тривиально прост и может работать со скоростью, приближающейся к скорости процедуры обычного копирования информации.
Декодер читает один бит сжатой информации и решает — это символ или пара <mathtex>\langle</mathtex><mathtex>offset,length</mathtex><mathtex>\rangle</mathtex>. Если это символ, то следующие <mathtex>8</mathtex> бит выдаются как раскодированный символ и помещаются в скользящее окно. Иначе, если это не закодированный конец файла, то соответствующее количество символов словаря помещается в окно и выдается в раскодированном виде. Поскольку это все, что делает декодер, понятно, почему процедура декодирования работает так быстро.
===Пример декодирования===
LZSS, длина словаря — <tex>8 </tex> байт (символов). Коды сжатого сообщения —
[[Файл:Кодисходного_сообщения_png.png ]]
