142
правки
Изменения
→Пример
'''Табл. Строки по пять символов.'''
На дереве все время находится одинаковое число <math>T </math> узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число <math>T </math> равно: длина буфера поиска минус длина буфера,содержащего еще не закодированные символы, плюс 1 <math>(T=S-L+1)</math>.
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <math>L-1</math> .)
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку (<math>\langle</math>16,2)<math>\rangle</math>. Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
si
|ases_sea_sick_seals
|}
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины <math>k </math>, то дерево надо было бы перестроить путем удаления <math>k </math> строк и добавления <math>k</math> k строк.
Удаляться будут первые <math>k </math> строк буфера поиска до его сдвига, а добавляться будут последние <math>k </math> строк этого буфера после сдвига.
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних 5 символов буфера поиска и добавить ее на дерево. Это следует повторить k раз.
