Zitat:

Ich kannjamal spaßeshalber versuchen, das Konzept des DictTrees zu verdeutlichen. Der witz an der Sache ist, dass die Worte des Wörterbuchs übherhaupt nicht mehr als Strings erkennbar sind, sondern es werden nur noch einzelne Chars betrachtet. Das passt ausgezeichnet zur Matrix, die ja auch keine Worte enthält, sondern 4 * 4 Chars - die Worte sind erst draus zu basteln. Also einzulesen seien die Worte: einer, einerlei, eingegrenzt, esel die werden in chars zerlegt folgendermaßen im Tree abgelegt: s e l / e i n e r l e i \ g e g r e n z t es gibt also 2 Verzweigungen, und "einer" ist gradezu verschwunden, denn es ist vollständig in "einerlei" enthalten. Um diesem "verschwinden" entgegenzuwirken, wird das letzte Zeichen eines Wortes markiert: s e l! / e i n e r! l e i! \ g e g r e n z t! Ich denke, ist intuitiv erkennbar, dass die 4 worte korrekt abgebildet sind (gewissermaßen redundanzfrei). Wenn man das vorwärts durchlaufend durchdenkt, bekommt man aber ein problem, die 4 Worte wieder zurückzubilden. Man läuft mw. das "einerlei" entlang, sammelt die Zeichen auf, und findet bei r!: hier ist ein Wort vollständig. Aber dass es noch weitergeht, bedeutet: wir habens hier mit 2 worten zu tun - aber nur die Zeichen eines Wortes eingesammelt! Eigentlich müsste man nun zurücklaufen, und das Wort "einer" verdoppeln, um dann mit einem der beiden Worte fortzufahren, bis man auch das "einerlei" hat. Kultig wäre doch nun, wenn man statt von links nach rechts, den Baum von rechts nach links durchwandert. Dann kann man bei jeder !-Markierung eine Zeichen-Sammlung beginnen, und endet am Root "e" in 4 Strängen: lese ielrenie renie tznergegnie Jo, das sind genau die 4 worte des Wörterbuchs, was sonst. praktisch ist das in einer Rekursion verblüffend einfach umzusetzen: nämlich anstatt bei der in die Tiefe absteigenden Rekursion kann man ebensogut auch einsammeln bei der aus der Tiefe zurückkehrenden Rekursion. Eine gradezu lächerlich einfache Umstellung im Code implementiert das: Statt: Sub Enumerate(nd) collectChar(nd) For Each ndChild in nd.Children Enumerate(ndChild) Next End Sub schreibe man: Sub Enumerate(nd) For Each ndChild in nd.Children Enumerate(ndChild) Next collectChar(nd) End Sub gesehen? Der NutzCode "collectChar(nd)" des Knoten-Besuchs ist einfach hinter dem Selbst-Aufruf plaziert. Dadurch wird der aktuelle Knoten nicht ausgewertet, bevor die Kinder besucht werden, sondern die Kinder sind bereits besucht und ausgewertet, wenn der aktuelle Knoten zur Auswertung gelangt. Jetzt ist es also ein leichtes, beim Antreffen eines WortEndes einen zusätzlichen Sammel-Strang zu eröffnen, sodass man am Ende 4-strängig im root ankommt (zurückkehrt, um genau zu sein - es ist ja eine "re"kursion). Aber wir packen ja nicht idiotischerweise alle Wörter in den dictTree, nur um sie anschließend wieder rekursiv zu rekonstruieren. Nein, bei Enumerate(ByVal pt As MatrixPoint, ByVal dic As DictNode) handelt es sich um zwei rekursive Durchläufe, die miteinander synchronisiert sind. Das eine ist die Matrix, deren gültige Pfade rekursiv abgelatscht werden. Das andere ist der DictTree, und der gibt der Matrix-Rekursion an "wos lang geht": Nämlich in der Matrix darf nur dahin ein Schritt erfolgen, wo man auch im DictTree einen "parallelen" Schritt tun kann: If dic.TryGetValue(ptChild.Letter, dicChild) Then (Selbstaufruf(ptChild, dicChild)) hier versucht das Dictionary dic, den Schritt nach dicChild zu gehen: es wird geguckt, ob unter dem Schlüssel ptChild.Letter ein Eintrag im Dictionary(of Char, dictNode) vorhanden ist. Ist der Schritt erfolgreich, dann erfolgt der Selbst-Aufruf, mit dem sowohl der dictNode als auch der aktuelle MatrixPoint "ptParent" ihren ChildNode in den Selbstaufruf geben, und die Rekursion also um eine Ebene vertiefen. Der Rest wurde ja oben schon genannt: das einsammeln der Chars im aufsteigenden Rekursions-Ast, und auch das Hinzufügen eines Sammel-Stranges, wenn eine WortEnde-Markierung aufgefunden wird. Ist auch im Source klar erkennbar und kommentiert: 'im wieder-aufstieg: neue Result-Liste eröffnen, wenn Wortende angetroffen If dic.WordEnd Then res.Add(New List(Of Char)) 'aktuellen Char in alle Result-Listen eintraten For Each r In res r.Add(pt.Letter) Next pt.Touched = False '"Betreten"-Markierung aufheben Return res End Function

(Rechtschreibfehler urheberrechtlich geschützt)