Изменения

Дерево поиска, как упоминалось выше, представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.  ===Порядок изменения дерева поиска===Кодер изучает буфер поиска, создавая <math>T </math> строк с числом символов <math>L</math> , которые помещены на двоичное лексикографически упорядоченное дерево поиска вместе с их смещениями.На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число <math>T </math> равно: длина буфера поиска <math>S</math> минус длина буфера, содержащего еще не закодированные символы <math>L</math>, плюс 1 <math>(T=S-L+1)</math>. Если во время кодирования случается совпадение длины <math>k</math>, то дерево надо перестроить путем удаления <math>k</math> строк и добавления <math>k</math> строк. Удаляться будут первые <math>k</math> строк буфера поиска до его сдвига, а добавляться будут последние <math>k</math> строк этого буфера после сдвига. Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних <math>L</math> символов буфера поиска и добавить ее на дерево. Это следует повторить <math>k</math> раз. Для определения смещения уславливаемся, что:* нулевое смещение зарезервировали для обозначения конца кодирования; * символ <math>S_t</math> соответствует единичному смещению относительно символа <math>S_t+_1</math> , с которого начинается буфер; * если имеется несколько фраз с одинаковой длиной совпадения, то выбираем ближайшую к буферу.  Покажем на примере, как двоичное дерево способно ускорить поиск в словареалгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.

С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины <math>k</math>, то дерево надо было бы перестроить путем удаления <math>k</math> строк и добавления <math>k</math> строк. Удаляться будут первые <math>k</math> строк буфера поиска до его сдвига, а добавляться будут последние <math>k</math> строк этого буфера после сдвига. Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних 5 символов буфера поиска и добавить ее на дерево. Это следует повторить <math>k</math> раз.