142
правки
Изменения
Нет описания правки
===Завершение работы===
Для того чтобы декодер смог вовремя остановиться, декодируя сжатое сообщение, кодер помещает в сжатый файл специальный символ «КОНЕЦ ФАЙЛА» после того, как он обработал все символы сообщения.
===Добавление новой строки в дерево===
Вся работа по поиску расположения и установлению длины максимального совпадения содержимого словаря с буфером происходит в процессе добавления в дерево новой строки.
При добавлении строки в дерево алгоритм последовательно перемещается от корня дерева к его листу, каждый раз осуществляя лексикографическое сравнение новой строки и узла дерева. В зависимости от результата сравнения выбирается больший или меньший потомок этого узла и запоминается длина совпадения строк и положение текущего узла.
Если в результате сравнения оказывается, что содержимое буфера и строка, на которую ссылается текущий узел, в точности совпадают, то ссылки в текущем узле обновляются так, чтобы они указывали на буфер, и процедура добавления строки в дерево завершается.
Если потомок текущего узла, выбранный для очередного шага, отмечен как несуществующий, остается заполнить его соответствующей ссылкой и завершить работу.
Нужно отметить, что при окончании работы процедуре добавления строки известны и смещение, и длина наибольшего совпадения, и для этого не потребовался полный перебор всех возможных вариантов совпадения.
===Удаление строки из дерева===
При удалении узла из дерева возможны два варианта. Если узел имеет не более одного потомка, то удаление узла осуществляется простым исправлением ссылок “родитель-потомок”. Если узел имеет два потомка, то необходимы другие действия. Для этого найдем следующий меньший узел в дереве, удалим его из дерева и заменим им текущий удаляемый узел. Следующий меньший узел находится выбором меньшего потомка и последующим перемещением от него по дереву до листа по большим ветвям.
===Пример кодирования===
