3622
правки
Изменения
→Порядок изменения дерева поиска
Скорость кодирования [[Алгоритмы LZ77 и LZ78|LZ77]] сильно зависит от того, каким образом осуществляется поиск совпадающей подстроки в словаре. В LZSS при кодировании поддерживается бинарное лексикографически упорядоченное дерево поиска, в котором каждому узлу соответствует определенная строка словаря длины <math>M</math> (максимальная длина совпадения). В дереве хранятся все подстроки словарной части, размером длины буфера.
====Порядок изменения дерева поиска====
Кодер изучает буфер поиска, создавая <math>T </math> строк с числом символов <math>L</math> , которые помещены на в двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.
На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк, <math>T=S-L+1</math>.
