142
правки
Изменения
→Пример
===Пример===
Пусть входной файл содержит следующую последовательность: «sid_eastman_clumsily_teases_sea_sick_seals». Для простоты предположим, что окно (желтые ячейки в таблице) состоит из 16-байтного буфера поиска и 5-байтного упреждающего буфера, содержащего еще не закодированные символы. После ввода первых <math>16+5</math> символов скользящее окно выглядит так:
{| border="1"
Кодер изучает буфер поиска, создавая двенадцать строк по пять символов (см. табл.) (их двенадцать, так как <math>12=16-5+1</math> ), которые помещены на двоичное дерево поиска вместе с их смещениями.
{| border="1"
|-
|05
|}
'''Табл. Строки по пять символов.'''
На дереве все время находится одинаковое число 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 строк этого буфера после сдвига.
Простейшая процедура обновления дерева состоит в приготовлении строк из начала буфера, их поиска и удаления. Потом необходимо сдвинуть буфер на одну позицию вправо (или переместить данные на одну позицию влево), приготовить строку из последних 5 символов буфера поиска и добавить ее на дерево. Это следует повторить k раз.
== Кодер LZSS ==
