Главная Промышленная автоматика. Пример 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.0018 |