1632
правки
Изменения
м
'''Таблицы 1 и 2. Строки по пять символов.'''
rollbackEdits.php mass rollback
===Организация поиска в словаре===
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <tex>M</tex> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
====Порядок изменения дерева поиска====
Кодер изучает буфер поиска, создавая <tex>T </tex> строк с числом символов <tex>L</tex> , которые помещены в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.1) (их двенадцать, так как <tex>12=16-5+1</tex>), которые помещены на двоичное дерево поиска вместе с их смещениями.
'''Таблицы 1 и 2. Строки по пять символов.'''
{|
|
|}
|}
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями <tex>16</tex> и <tex>10</tex>, но первая из них, sid_e, имеет более длинное совпадение.
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi (см. табл.2).
Для того чтобы найти эти строки, можно просмотреть все вершины дерева и выбрать те пары, где разница между смещением и длиной буфера не превосходит длины части совпадения.
В данном примере длина буфера {{- --}} <tex>5</tex> символов, часть совпадения {{--- }} <tex>2</tex> символа, поэтому нужно найти смещения где разница между ним и длиной буфера не превосходит <tex>2</tex>. Это смещения <tex>5</tex> и <tex>6</tex>. Теперь для каждой строки в дереве нужно удалить первые два символа и прибавить следующие два символа.
===Оптимизация памяти===
===Пример декодирования===
LZSS, длина словаря — <tex>8 </tex> байт (символов). Коды сжатого сообщения —
[[Файл:Кодисходного_сообщения_png.png ]]
