Probiere mal das Attachment.

0.) ZIP entpacken
1.) Project1.exe starten
2.) Button "Dawg laden" klicken
3.) Test.dawg auswählen
4.) in Edit "Kombinatorische Suche" deine Buchstaben eingeben (Groß/Kleinschreibung irrelevant)
5.) in Edit "min. Länge" zb. 5 eingeben
6.) Checkbox "Suche anzeigen" anhacken
7.) Button "Wörter erzeugen" anklicken

Nun zur Theorie:

Die Basis ist eine ganz spezielle Form einer Baumstruktur -> Directed Acyclic Word Graph -> DAWG in der dann ca. 200.000 deutsche Wörter gespeichert sind. Eine solche Liste als Textdatei würde ungefähr 3 Mb benötigen und ist als DAWG nur noch 800 Kb groß. Zusätzlich kann man in diesem DAWG Tree nun sehr schnell und effizient suchen. Neben der Komprimierung des Wörterbuches und der vollständigen Entfernung der redundanten Prefixes und Suffixe der Wörter ist die schnelle Suche die Hauptaufgabe dieses DAWG.

Das Program demonstriert nun wie man in einem solchen DAWG schnell suchen kann. Einerseits ein Pattern-Matching das Wildcards unterstützt, zb. für Rechtschreibprüfungen etc.pp. Und eine weitere Suchfunktion ist die kombinatorische Suche (Permutationen), wie zb. beim Scrabble, Kreuzworträtseln oder eben 9Live nötig.

Ich benutze dieses kleine Projekt immer wenn ich mal interessante Rätsel auf 9Live (beim Durch-Zappen wohlgemerkt ) sehe.

Die Organisation solcher Wortlisten in einem DAWG ist der/die beste und effizienteste Algorithmus/Datenstruktur die ich für diese Aufgabe kenne. Die Zielsetzung meinerseits für die Entwicklung dieses Source war es eben die performanteste Lösung zu kreieren. Ich kenne keine andere Tree-Implementierung die schneller ist. Und bei der weiteren Entwicklung von zb. Kreuzworträtseln oder meiner Scrabble Engine benötigte ich eben eine enorm schnelle Suche, auch kombinatorisch, über sehr große Wortlisten.

Der DWAG Source demonstriert

- Konstruktion eines DWAG Tree, als azyklische Datenstrukturen, Nodebäume mit multiplen Verlinkungen
- die dynamische und sequientielle "just in time" Erzeugung solcher Tree's
- Verwendung eines eigenen inplaced Speichermanagers für die Node Strukturen
- Verwendung simpler boolscher Algebra innerhalb der Nodes für deren hierarischem Aufbau, dh. die Treenodes sind keine dynaisch allozierten Datenstrukturen wie Records oder Objekte
- Verwendung von Hashfunktionen (nicht die kryptographischen Hashfunktion) bei der Komprimierung eines solchen Tree's -> entfernen der redundanten Wort Suffixe, dh. Wörter mit gleichen Endungen werden zusammengefasst
- Suche per multiplem Patternmatching und Wildcards
- Suche per Kombinatorik -> Permutation von Buchstaben
- sowohl iterative wie auch rekusive Algorithmen
- Enumeration per Callbacks in einem solchen Tree

Essentiell geht es, im Sinne dieses Threads, darum das man mit Hilfe einer Wörterdatenbank die erzeugten und möglichen Permutationen der Buchstaben auf sinnvolle Weise einschränkt. Man erzeugt also nur die Wörter die es auch in einer jeweiligen Sprache gibt. Technologisch wäre ein DAWG wie in meinem Beispiel nun eine Lösung die effizient in der algorithmischen Komplexität und im Speicherverbrauch ist.


Gruß Hagen


PS: hier ein Auszug aus dem Source
PPS: Tippfehler beseitigt