Главная Промышленная автоматика.

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

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

program spell ( input, output, dictionary); type

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

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

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

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

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

nextKord: 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 (Л) ;

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 (Л)

end; { spell ]

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



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

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

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


Рис. 5.4. Нагруженное дерево

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

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

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

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

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

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

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

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

Здесь предполагается, что алгоритм работает только с английским алфавитом. - Прим. ред.

Эта функция является версией функции COMPUTER из раздела 2.5. 154 ГЛАВА 5. СПЕЦИАЛЬНЫЕ МЕТОДЫ ПРЕДСТАВЛЕНИЯ МНОЖЕСТВ



3. Процедура GETNEW(node, с) делает значение узла node с символом с указателем на новый узел.

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

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

type

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

TRIENODE = array [chars] of Т TRIENODE;

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

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

procedure MAKENULL ( var node: TRIENODE );

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

С: chars; begin

for c:= A to $ do

nodetc] : = nil

end; { MAKENULL }

procedure ASSIGN { var node: TRIENODE; C: chars; p: TtRIENODE );

begin

node[c] : = p

end; { ASSIGN }

function VALUEOF ( var node: TRIENODE; c: chars ): tTRIENODE; begin

return {node [ c])

end; { VALUEOE }

procedure GETNEW ( var node: TRIENODE; C: chars ); begin

newinode[c] ) ; MAKENULL(node[c])

end; { GETNEW }

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

TRIE = tTRIENODE;

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





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 [47] 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.0038