home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / spezial / 07 / trie.txt < prev   
Encoding:
Text File  |  1989-03-07  |  10.5 KB  |  270 lines
  1.  
  2.  
  3. Abbildung 1:
  4. Ein Trie mit sieben Worten.
  5.  
  6. Abbildung 2:
  7. Der gleiche Trie wie in Abbildung 1, aber in der
  8. speicherplatzsparenden Repräsentation.
  9.  
  10.  
  11. Der Trie
  12.  
  13. Datenstruktur zur Speicherung von Wörterbüchern
  14.  
  15. von Martin Holzherr
  16.  
  17.  
  18. Wir stellen Ihnen die effizienteste Methode vor, Wörterbücher zu
  19. speichern: Der Trie. Mit den erarbeiteten Algorithmen läßt sich,
  20. quasi als Abfallprodukt, auch ein leistungsfähiger
  21. Crossreferenzer zur Analyse von Prozeduren bauen unter
  22. Berücksichtigung global deklarierter Variable.
  23.  
  24. Unter einem "Trie" versteht man einen Vielwegbaum, in dessen
  25. Knoten einzelne Buchstaben eines Wortes gespeichert sind. Folgt
  26. man von der Wurzel des Trie allen möglichen Pfaden bis zu seiner
  27. Wortendmarke, erhält man alle im Tree gespeicherten Worte.
  28.  
  29. Abbildung 1 zeigt einen Trie, in dem die Worte BALL, BAR, BAU,
  30. BAUM, BIER, BILD und IOD gespeichert sind.
  31.  
  32. Die Datenstruktur des Trie ist schon lange bekannt, wird jedoch
  33. viel zu selten eingesetzt, obwohl der Trie die effizienteste
  34. Datenstruktur ist, um zum Beispiel ein alphabetisches
  35. Verzeichnis aller Worte in einem Textfile zu erhalten. Eine
  36. detailierte Beschreibung des Trie als abstrakter Datentyp findet
  37. sich in dem Buch "Algorithmen und Datenstrukturen" (1).
  38.  
  39. Will man nun diese Datenstruktur in einer Hochsprache wie
  40. Pascal, Modula oder C implementieren, taucht sofort eine
  41. Schwierigkeit auf: Beschränkt man sich auf die Großbuchstaben
  42. des Alphabetes, kann jeder Trie-Knoten bis zu 26 Nachfolger
  43. haben. Praktisch wird dieses Maximum jedoch nie erreicht. Die
  44. folgende Deklaration eines Trieknotens bedeutet deshalb eine
  45. enorme Speicherplatzverschwendung:
  46.  
  47. ,,l
  48.       TYPE TRIE = POINTER TO NODE
  49.            NODE = RECORD
  50.            Buchstabe :CHAR;
  51.            Wortende :BOOLEAN;
  52.            Nachfolger:ARRAY["A".."Z"] OF TRIE
  53.            END;
  54.  
  55. Angenommen ein Pointer benötige vier Byte, dann würde ein
  56. einziger, nach diesem Schema deklarierter Trieknoten 106 Byte
  57. belegen. Der Speicherbedarf der Zeiger ist gegenüber den anderen
  58. Informationen, dem Zeichen mit einem Byte und dem "Wortende" mit
  59. 2 Byte, enorm groß.
  60. Daher ist es zur Einsparung von Speicherplatz günstiger, einen
  61. Binärbaum als Vielwegbaum zu "mißbrauchen". Anstatt einen linken
  62. und einen rechten "Sohn" wie bei einem gewöhnlichen Binärbaum
  63. hat hier jeder Knoten einen Horizontalzeiger zu einem
  64. "Geschwisterknoten" und einen Vertikalzeiger zum ersten
  65. "Nachfolgerknoten". Dazu gehört folgende Deklaration:
  66.  
  67. ,,l
  68.       TYPE TRIE = POINTER TO NODE
  69.            NODE = RECORD
  70.            Buchstabe :CHAR;
  71.            Wortende :BOOLEAN;
  72.            horizontal, vertikal: TRIE
  73.            END;
  74.  
  75.  
  76. ,,z
  77. Der Aufbau eines Trie-Wörterbuches
  78.  
  79.  
  80. Ein naheliegendes Verfahren, um ein alphabetisches Verzeichnis
  81. aller Wörter eines Textfiles zu erhalten, wäre, das File
  82. wortweise zu lesen und immer, wenn der letzte Buchstabe eines
  83. Wortes erkannt ist, dieses in das Wörterbuch einzufügen. Der
  84. Vorteil des Trie gegenüber anderen Datenstrukturen ist es nun
  85. aber gerade, daß eine solche Zwischenspeicherung von ganzen
  86. Worten gar nicht nötig ist. Wir stellen im folgenden eine
  87.  
  88.        PROCEDUREinsert(VAR t:TRIE);
  89.  
  90. vor, die viel effizienter und eleganter arbeitet: Jedesmal, wenn
  91. der erste Buchstabe eines Wortes gelesen wurde, wird insert
  92. aufgerufen und zu dem Trieknoten verzweigt, der diesem ersten
  93. Buchstaben entspricht.
  94.  
  95. Dann erst wird der nächste Buchstabe gelesen und derjenige
  96. Nachfolgerknoten gesucht, der diesem Buchstaben entspricht.
  97. Falls kein solcher Nachfolger existiert, wird ein neuer Knoten
  98. geschaffen. Dieses Verfahren wird so lange weitergeführt, bis
  99. der letzte Buchstabe des Wortes gelesen und das Wort somit an
  100. der richtigen Stelle im Wörterbuch eingetragen ist. Der nun
  101. folgende Pseudocode beschreibt die notwendigen Schritte beim
  102. Einfügevorgang:
  103.  
  104. (* Beim ersten Aufruf von insert sei der
  105.     erste Buchstabe des Wortes bereits gelesen.
  106.     Das gerade aktuell gelesene zeichen sei "ch".
  107.     TRIE ist gemäß der platzsparenden
  108.     Deklaration vereinbart *)
  109.  
  110. Prozedur insert(VAR t:TRIE);
  111. BEGIN
  112.  
  113.  falls t auf NIL zeigt,
  114.         dann alloziere Speicherplatz für einen neuen Knoten,
  115.         speichere darin "ch" und laß t auf diesen neuen Knoten
  116.         zeigen.
  117.         ,,krek lies das nächste Zeichen "ch".
  118.            falls es sich bei "ch" um einen Buchstaben handelt,
  119.            dann plaziere ihn am richtigen Ort im Trie durch
  120.            Aufruf von insert(t^.vertical)
  121.            sonst: t^.Wortende:=TRUE
  122.  
  123.  ,,ffalls t nicht auf NIL zeigt, sondern auf einen Knoten mit
  124.  einem Buchstaben, der alphabetisch nach "ch" kommt
  125.    dann füge "ch" vor diesem Knoten in den Trie ein,
  126.    indem du einen neuen Knoten q bildest, darin "ch"
  127.    abspeicherst und den Horizontalzeiger von q auf
  128.    auf den gleichen Ort richtest auf den t zeigt,
  129.    anschließend soll t neu auf q zeigen.
  130.    führe die gleichen Aktionen aus, wie unter
  131.    ,,krek beschrieben.
  132.  
  133. ,,ffalls t nicht auf NIL zeigt, sondern auf einen
  134.  Knoten mit einem Buchstaben, der alphabetisch vor
  135.  "ch" kommt
  136.    dann füge "ch" nach diesem Knoten in den Trie ein
  137.    durch Aufruf von ,,finsert(t^.horizontal).
  138.  
  139.  ,,ffalls t nicht auf NIL zeigt, sondern auf einen
  140.  Knoten mit demselben Buchstaben wie "ch"
  141.  
  142.    dann führe die Aktionen durch, die unter ,,krek
  143.    beschrieben sind.
  144. END insert;
  145.  
  146. Wie Sie sehen, arbeitet die Prozedur insert rekursiv. Um das
  147. fertige Wörterbuch schließlich alphabetisch auszugeben, bietet
  148. sich ebenfalls eine rekursive Prozedur an.
  149.  
  150. Diese Prozedur mit dem Kopf
  151. ,,l
  152.  PROCEDURE printTrie(t:TRIE;level:INTEGER);
  153.  
  154. verwendet ein global deklariertes Zeichenfeld S um den
  155. Anfangsteil eines Wortes zu speichern. Beim ersten Aufruf von
  156. printTrie muß level = 0 sein. printTrie traversiert den Trie und
  157. speichert die gefundenen Buchstaben im Feld S, so daß
  158. S[0..level] jeweils dem Anfang eines Wortes entspricht. Sobald
  159. eine Wortendmarke gefunden wird, wird S[0..level] ausgedruckt
  160. und anschließend die Traversierung fortgesetzt.
  161.  
  162. Ein Beispiel soll die Arbeitsweise der beiden Prozeduren
  163. verdeutlichen. Der eingegebene Textstring "Welches Wort mit mehr
  164. als sechs Buchstaben kommt in dieser TOOLBOX - Ausgabe mehr als
  165. 50 mal vor" ergibt folgende Bildschirmausgabe:
  166.  
  167.   ALS
  168.   AUSGABE
  169.   BUCHSTABEN
  170.   DIESER
  171.   IN
  172.   KOMMT
  173.   MAL
  174.   MEHR
  175.   MIT
  176.   SECHS
  177.   TOOLBOX
  178.   VOR
  179.   WELCHES
  180.   WORT
  181.  
  182. Implementation       der      Algorithmen      und
  183. Anwendungsbeispiele
  184.  
  185.  
  186. Mit der vorgestellten rekursiven Implementation lassen sich
  187. keine Geschwindigkeitsweltrekorde brechen. Dazu wären eine
  188. iterative Versionen der Prozeduren insert und ,,fprintTrie
  189. besser geignet. Aber eine rekursiv definierte Datenstruktur wie
  190. der Trie wird am einfachsten mit rekursiven Mitteln bearbeitet.
  191. Hier gilt nämlich: iterativ geht meistens schief.
  192.  
  193. Wenn man die gegebene Implementation zum Beispiel verwendet, um
  194. einen Buchindex herzustellen, sollte im Trieknoten noch ein
  195. weiteres Feld vorgesehen sein, um die Seitenzahlen zu speichern.
  196. Noch besser wäre ein Feld mit einem Zeiger auf eine Liste von
  197. Seitenzahlen. Der Algorithmus würde dann zu jedem Wort im Text
  198. automatische eine Liste der Seitenzahlen erstellen, auf denen
  199. die Wörter vorkommen. Natürlich müßte dann eine Selektion
  200. vorgesehen werden, um nur signifikante Wörter zu erfassen. Die
  201. Seitenzahlen, auf denen das Wort "die" auftaucht sind mit
  202. Sicherheit irrelevant.
  203.  
  204. Wir haben noch eine andere Anwendung des Trie ausgearbeitet: Ein
  205. Programm, das Prozeduren von Modula-Programmen analysiert und
  206. alle Bezeichner herausschreibt, die in einer Prozedur verwendet
  207. werden, dort aber nicht deklariert sind. Solche global
  208. deklarierten Bezeichner können nämlich vor allem bei
  209. Programmmodifikationen die Ursache für schwer zu entdeckende
  210. Fehler sein.
  211.  
  212. Das Modul TrieCrossRef schreibt alle Variablen-, Typen-,
  213. Konstanten-, und Prozedurdeklarationen des zu analysierenden
  214. Programms auf ein File. Zusätzlich werden unter jedem
  215. Prozedurkopf die Bezeichner aufgelistet, die nicht im
  216. Deklarationsteil der Prozedur auftauchen.
  217.  
  218. Die Vorgehensweise ist dann folgende: Zuerst werden alle Modula-
  219. Schlüsselwörter, also die reservierten Bezeichner wie zum
  220. Beispiel BEGIN FOR, etc., von dem File in einen Trie eingelesen.
  221. Diese Wörter werden einerseits gebraucht, um sie im Quelltext zu
  222. erkennen und, da uninteressant, einfach überlesen zu können.
  223. Andererseits braucht man sie, um Anfang und Ende von
  224. Prozedurkopf und -körper zu finden und den Verarbeitungsprozeß
  225. an diesen Stellen vom Einsammeln und Markieren von deklarierten
  226. Bezeichnern auf das Suchen von nicht deklarierten Bezeichnern
  227. umzuschalten.
  228.  
  229. Für die eigentliche Programmanalyse benötigt man ein ganzes
  230. Array von Tries. Dieses Array sollte mindestens so viele Felder
  231. besitzen wie die maximale Verschachtelungstiefe der Prozeduren
  232. im zu analysierenden Programm. Der Index "triesPos" zeigt zu
  233. Beginn auf das erste Feld dieses Arrays. Jedesmal, wenn das
  234. Schlüsselwort PROCEDURE erkannt wurde, wird "triesPos" um eins
  235. erhöht und em Feld mit diesem Index wird zur Initialisierung
  236. eine Kopie des Tries mit den Schlüsselwörtern übergeben.
  237.  
  238. Dann werden alle weiteren Worte, die zwischen den
  239. Schlüsselworten PROCEDURE und BEGIN oder PROCEDURE und PROCEDURE
  240. liegen, was einer eingeschachtelten Prozedur entsprechen würde,
  241. in diesen Trie aufgenommen und mit einer Marke versehen. Bei
  242. allen Bezeichnern, die nun zwischen den Schlüsselwörtern BEGIN
  243. und dem Ende der Prozedur gefunden werden, aber nicht im
  244. dazugehörigen Trie vermerkt sind, muß es sich nun um Bezeichner
  245. handeln, die nicht lokal deklariert sind.
  246.  
  247. Diese Analyse wird durch folgende Eigenheiten der Sprache Modula
  248. etwas erschwert: das Schlüsselwort PROCEDURE kann nämlich nicht
  249. nur einen Prozedurkopf einleiten, sondern es kann auch
  250. Bestandteil einer Typendeklaration sein (Prozedurtypen,
  251. Prozedurvariable). TrieCrossRef erkennt diesen fall daran, daß
  252. dem Schlüsselwort PROCEDURE ein "=" beziehungsweise ein ":"
  253. vorrausgeht. Ferner müssen natürlich Kommentare, auch
  254. geschachtelte, und Strings übersprungen werden.
  255.  
  256. Als zusätzliches "Feature" erhält jeder Prozedurkopf auf dem
  257. Ausgabefile eine Laufnummer, die die Position und
  258. Verschachtelungstiefe der Prozedur angibt. "-2-1" zum Beispiel
  259. bedeuted erste Unterprozedur der zweiten Prozedur des Programms.
  260. Natürlich wird auch jede geschachtelte Prozedur eingerückt.
  261. Aus Platzgründe müssen wir uns an dieser Stelle auf Andeutungen
  262. des Algorithmus beschränken, eine konkrete Implementation finden
  263. Sie auf der Spezial-Diskette, die zu dieser Beilage angeboten
  264. wird.
  265.                                               (ms)
  266.  
  267. ,,x
  268. Literatur:
  269. (1) Aho, Hopcroft, Ullman, Data structures and algorithms, 1983
  270.