142
правки
Изменения
→Модель данных
окна автоматически означает удаление идентичной по длине порции из его задней части. Размер окна кратен степени двойки.
Дерево поиска представляет собой двоичное лексикографически упорядоченное дерево. Каждый узел в дереве соответствует одной подстроке словаря и содержит ссылки на родителя и двух потомков: «большего» и «меньшего» в смысле лексикографического сравнения символьных строк.
===Пример===
Покажем, как двоичное дерево способно ускорить поиск в словаре. Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера. После ввода первых <math>16+5</math> символов скользящее окно выглядит так:
{| border="1"
|style="background:#FFCC00" |sid_eastman_clum
|style="background:#FFCC00"|sily_
|teases_sea_sick_seals
|}
причем подпоследовательность teases_sea_sick_seals ждет своей очереди на входе.
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.) (их двенадцать, так как <math>12=16-5+1</math> ), которые помещены на двоичное дерево поиска вместе с их смещениями.
На дереве все время находится одинаковое число T узлов или строк, поскольку при его обновлении удаляется и добавляется одно и то же число строк. Число T равно: длина буфера поиска минус длина буфера,содержащего еще не закодированные символы, плюс 1 <math>(T=S-L+1)</math>.
Первым символом в буфере, содержащем еще не закодированные символы, является s, поэтому кодер ищет на дереве строки, начинающиеся на s. Он находит две строки со смещениями 16 и 10, но первая из них, sid_e, имеет более длинное совпадение.
(Бывают случаи, когда строка на дереве полностью совпадает с содержимым буфера, содержащего еще не закодированные символы. Тогда кодер может искать дальнейшие совпадения. В принципе, длина совпадения может быть <math>L-1</math> .)
В нашем примере длина совпадения равна 2, поэтому кодер выдает метку (16,2). Теперь кодер должен переместить скользящее окно на две позиции вправо и перестроить дерево. Новое окно выглядит следующим образом:
si
{| border="1"
|si
|style="background:#FFCC00"|d_eastman_clumsi
|style="background:#FFCC00"|ly_te_
|ases_sea_sick_seals
|}
С дерева необходимо удалить строки sid_e и id_ea и вставить новые строки clums и lumsi. Если бы случилось совпадение длины k , то дерево надо было бы перестроить путем удаления k строк и добавления k строк.
Удаляться будут первые k строк буфера поиска до его сдвига, а добавляться будут последние k строк этого буфера после сдвига.
== Кодер LZSS ==
