Изменения
→Порядок изменения дерева поиска
===Порядок изменения дерева поиска===
Кодер изучает буфер поиска, создавая <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> строк.
Покажем на примере, как в алгоритме LZSS происходит трансформация двоичного дерева, в виде которого хранится словарь.
===Пример===
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного буфера, содержащего еще не закодированные символы. После ввода первых <math>16+5</math> символов скользящее окно выглядит так:
