Sehen wir uns zunächst die Einschränkungen des Problems an. Sie möchten eine Wortliste für ein Spiel in einer Datenstruktur speichern, die das "Anagramm"-Problem effizient unterstützt. Das heißt, bei einem "Rack" von n Buchstaben, was sind alle Wörter mit n oder weniger Buchstaben in der Wortliste, die aus diesem Rack erstellt werden können. Die Wortliste wird ungefähr 400.000 Wörter umfassen, und das sind wahrscheinlich ungefähr 1 bis 10 Megabyte an String-Daten, wenn sie unkomprimiert sind.
Ein Trie ist die klassische Datenstruktur, die zur Lösung dieses Problems verwendet wird, da sie sowohl Speichereffizienz als auch Sucheffizienz kombiniert. Mit einer Wortliste von etwa 400.000 Wörtern angemessener Länge sollten Sie in der Lage sein, den Versuch im Gedächtnis zu behalten. (Im Gegensatz zu einer Art B-Tree-Lösung, bei der Sie den größten Teil des Baums auf der Festplatte behalten, weil er zu groß ist, um auf einmal in den Speicher zu passen.)
Ein Trie ist im Grunde nichts anderes als ein 26-stelliger Baum (vorausgesetzt, Sie verwenden das lateinische Alphabet), bei dem jeder Knoten einen Buchstaben und ein zusätzliches Bit an jedem Knoten hat, das angibt, ob es sich um das Ende des Wortes handelt.
Skizzieren wir also die Datenstruktur:
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Dies ist natürlich nur eine Skizze; Sie möchten wahrscheinlich, dass diese über geeignete Eigenschaftszugriffsmethoden und Konstruktoren und so weiter verfügen. Außerdem ist eine flache Liste vielleicht nicht die beste Datenstruktur; Vielleicht ist eine Art Wörterbuch besser. Mein Rat ist, es zuerst zum Laufen zu bringen und dann seine Leistung zu messen, und wenn es nicht akzeptabel ist, dann mit Änderungen zu experimentieren, um seine Leistung zu verbessern.
Sie können mit einem leeren Versuch beginnen:
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
Das heißt, dies ist der "Wurzel"-Trie-Knoten, der den Anfang eines Wortes darstellt.
Wie fügt man das Wort „AA“, das erste Wort im Scrabble-Wörterbuch, hinzu? Nun, machen Sie zuerst einen Knoten für den ersten Buchstaben:
root.Children.Add('A', false, new List<TrieNode>());
OK, unser Versuch ist jetzt
^
|
A
Fügen Sie nun einen Knoten für den zweiten Buchstaben hinzu:
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Unser Versuch ist jetzt
^
|
A
|
A$ -- we notate the end of word flag with $
Toll. Nehmen wir nun an, wir wollen AB hinzufügen. Wir haben bereits einen Knoten für „A“, fügen Sie also den Knoten „B$“ hinzu:
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
und jetzt haben wir
^
|
A
/ \
A$ B$
Mach weiter so. Anstatt "root.Children[0]..." zu schreiben, schreiben Sie natürlich eine Schleife, die den Trie durchsucht, um zu sehen, ob der gewünschte Knoten existiert, und wenn nicht, erstellen Sie ihn.
Um Ihren Trie auf der Festplatte zu speichern - ehrlich gesagt würde ich die Wortliste einfach als reine Textdatei speichern und den Trie bei Bedarf neu erstellen. Es sollte nicht länger als etwa 30 Sekunden dauern, und dann können Sie den Trie im Speicher wiederverwenden. Wenn Sie den Trie in einem Format speichern möchten, das eher einem Trie ähnelt, sollte es nicht schwer sein, ein Serialisierungsformat zu finden.
Um den Trie nach einem passenden Rack zu durchsuchen, besteht die Idee darin, jeden Teil des Trie zu untersuchen, aber die Bereiche auszuschneiden, in denen das Rack unmöglich passen kann. Wenn Sie keine "A"s auf dem Rack haben, müssen Sie keinen "A"-Knoten hinuntergehen. Ich habe den Suchalgorithmus in Ihrer vorherigen Frage skizziert.
Ich habe eine Implementierung eines dauerhaften Versuchs im funktionalen Stil, über den ich schon seit einiger Zeit bloggen wollte, aber nie dazu gekommen bin. Wenn ich das irgendwann poste, werde ich diese Frage aktualisieren.
