yandex rtb 1
ГоловнаЗворотній зв'язок
yande share

Алгоритмы структуры данных

Загрузка...

5.3. Нагруженные деревья

В этом разделе мы рассмотрим специальную структуру для представления множеств, состоящих из символьных строк. Некоторые из описанных здесь методов могут работать и со строками объектов другого типа, например со строками целых чисел. Эта структура называется нагруженными деревьями (tries). Рассмотрим их применение к символьным строкам.

Пример 5.2. Как описывалось в главе 1, возможная реализация проверки орфографии состоит из следующей последовательности действий: сначала читается слово из текстового файла с остановкой после каждого слова (слова отделяются друг от друга пробелом или символом новой строки), далее проверяется, есть ли это слово в стандартном словаре наиболее употребительных слов. Слова, отсутствующие в словаре, распечатываются как возможные ошибки. В листинге 5.5 приведен эскиз возможной программы spell (правописание). Здесь использована процедура getword(x, f), которая читает следующее слово в текстовом файле f и присваивает его переменной х, имеющей тип wordtype (мы определим его позже). Еще одна используемая переменная А имеет знакомый нам тип SET. Реализация этого АТД использует операторы INSERT, DELETE, MAKENULL и PRINT. Последний оператор распечатывает элементы множества.

 

Листинг 5.5. Программа проверки орфографии

program spell   (   input,   outputdictionary ) ;

type

wordtype =  {  надо определить  }

SET =  {  надо определить,   используя структуру

нагруженного дерева  }

var

A:   SET;   {   хранит  считанное  слово,   пока  оно

не найдено в словаре  }

nextword:   wordtype;

dictionary:   file of char;

procedure  getword   (  var x:   wordtype;   f:   file of  char   );

{ читает следующее слово в файле  f и присваивает его переменной х }

procedure  INSERT   (   х:   wordtype;   var  S:   SET   );

{  надо определить   }

procedure DELETE   (   x:   wordtype;   var  S:   SET  );

{  надо определить   }

procedure MAKENULL   (  var  S:   SET   );

{  надо определить   }

procedure  PRINT   (  var  S:   SET   );

{  надо определить   }

begin

MAKENULL(A);

while not eof(input)   do begin

getword(nextword,   input);

INSERT(nextword.   A)

end;

while not eof(dictionary)   do begin

getword(nextword,   dictionary) ;

DELETE(nextword,   A)

end;

PRINT(A)

end;    {   spell   }

Структура нагруженных деревьев поддерживает операторы множеств, у которых элементы являются словами, т.е. символьными строками. Удобно, когда большинство слов начинается с одной и той же последовательности букв или, другими словами, когда количество различных префиксов значительно меньше общей длины всех слов множества.

В нагруженном дереве каждый путь от корня к листу соответствует одному слову из множества. При таком подходе узлы дерева соответствуют префиксам слов множества. Чтобы избежать коллизий слов, подобных THE и THEN, введем специальный символ $, маркер конца, указывающий окончание любого слова. Тогда только слова будут словами, но не префиксы.

Пример 5.3. На рис. 5.4 показано нагруженное дерево слов {THE, THEN, THIN, THIS, TIN, SIN, SING}. Здесь корень соответствует пустой строке, а два его сына — префиксам Т и S. Самый левый лист представляет слово THE, следующий лист — слово THEN и т.д.

На основании рис. 5.4 можно сделать следующие выводы.

1.    Каждый узел может иметь до 27 сыновей, которые могут быть буквами или символом $.

2.    Большинство узлов имеет значительно меньше 27 сыновей.

3.    Листом может быть только окончание ребра, помеченного символом $.

Узлы нагруженного дерева как АТД

Мы можем рассматривать узел нагруженного дерева как отображение, где областью определения будет множество {А, В, .... Z, $} (или другой выбранный алфавит), а множеством значений — множество элементов типа "указатель на узел нагруженного дерева". Более того, так как дерево можно идентифицировать посредством его корня, то АТД TRIE (Нагруженное дерево) и TRIENODE (Узел нагруженного дерева) имеют один и тот же тип данных, хотя операторы, используемые в рамках этих АТД, имеют существенные различия. Для реализации АТД TRIENODE необходимы следующие операторы.

1.    Процедура ASSIGN(node, с, р),  которая  задает  значение р (указатель на узел) символу с в узле node,

2.    Функция VALUEOF(node, с) — возвращает значение (указатель на узел), ассоциированное с символом с в узле node,

3.   Процедура GETNEW(node, с) делает

значение узла node с символом с указателем на новый узел.

Нам также будет необходима процедура MAKENULL(node), делающая узел node пустым отображением.

Самой простой реализацией узлов нагруженного дерева будет массив node указателей на узлы с индексным множеством {А, В, .... Z, $}. Таким образом, АТД TRIENODE можно определить следующим образом:

type

chars =  {'А',   'В',   ...,   'Z',   '$'};

TRIENODE  =  array[chars]   of ↑ TRIENODE;

Если node — массив узлов, то node\c\ совпадает с VALUEOF(node, с) для любого символа с. Чтобы избежать создания многочисленных листьев, являющихся потомками '$', примем соглашение, что node['$'] имеет значение nil или указателя на самого себя. (При формировании дерева node не может иметь сына, соответствующего '$', но после возможных преобразований может появиться такой сын, которого мы никогда не создавали.) Теперь можно написать процедуры, выполняемые над узлами нагруженного дерева. Их код приведен в следующем листинге.

Листинг 5.6. Операторы узлов нагруженного дерева

procedure MAKENULL ( var node: TRIENODE );

{ делает node листом, т.е. пустым отображением }

var

с: chars;

begin

for c:= 'A' to '$' do

node[с]:= nil

end; { MAKENULL }

 

procedure ASSIGN ( var node: TRIENODE; c: chars; p: ↑TRIENODE );

begin

node[c]:= p

end; { ASSIGN }

 

function VALUEOF ( var node: TRIENODE; c: chars ): ↑TRIENODE;

begin

return(node[c])

end; { VALUEOF }

 

procedure GETNEW ( var node: TRIENODE; c: chars );

begin

new(node[c]);

MAKENULL(node[o])

end; { GETNEW }

Теперь определим АТД TRIE:

type

trie = ↑trienode;

Мы можем определить тип wordtype как массив символов фиксированной длины. Предполагается, что среди значений такого массива обязательно есть по крайней мере один символ '$'. Считаем, что концу слова соответствует первый символ '$', независимо от того, что за ним следует. При выполнении этих предположений написана процедура INSERT(*, words), которая вставляет слово ж в множество words (слова), представленное посредством нагруженного дерева. Код этой процедуры показан в листинге 5.7. Написание процедур MAKENULL, DELETE и PRINT для данной реализации нагруженных деревьев оставляем в качестве упражнений для читателей.

 

70

yandex rtb 4