Trie Implementierung Frage

Question

Ich implementiere einen Trie für prädiktive Texteingabe in VB.NET - grundsätzlich Autovervollständigung, was die Verwendung des Trie betrifft. Ich habe meinem Trie eine rekursive Datenstruktur basierend auf der generischen Wörterbuchklasse gemacht.

Es ist im Grunde:

class WordTree Inherits Dictionary(of Char, WordTree) 

Jeder Buchstaben in einem Wort (alle oberen verrohrten) als Schlüssel zu einer neuen WordTrie verwendet wird. Ein Nullzeichen auf einem Blatt zeigt die Beendigung eines Wortes an. Um ein Wort zu finden, das mit einem Präfix beginnt, laufe ich den Trie so weit, wie mein Präfix geht, dann sammle alle Kinderwörter.

Meine Frage ist im Grunde auf die Implementierung des Trie selbst. Ich verwende die Wörterbuch-Hash-Funktion, um meinen Baum zu verzweigen. Ich könnte eine Liste verwenden und eine lineare Suche über die Liste durchführen oder etwas anderes tun. Was ist der reibungslose Umzug hier? Ist das ein vernünftiger Weg, meine Verzweigung zu machen?

Danke.

Update:

Nur um zu klären, ich frage im Grunde, wenn das Wörterbuch Ansatz Verzweigung offensichtlich schlechter als eine andere Alternative. Die Anwendung, in der ich diese Datenstruktur verwende, verwendet nur Großbuchstaben, also ist der Array-Ansatz vielleicht der beste. Ich könnte die gleiche Datenstruktur für eine komplexere Art-Ahead-Situation in der Zukunft verwenden (mehr Zeichen). In diesem Fall klingt es nach dem richtigen Ansatz - bis zu dem Punkt, an dem ich etwas Komplexeres verwenden muss.

Answer 1

Wenn es nur die 26 Buchstaben sind, als ein 26-Eintrag-Array. Dann wird nach Index gesucht. Es benötigt wahrscheinlich weniger Speicherplatz als das Dictionary, wenn die Bucket-Liste länger als 26 ist.

Answer 2

Eine gute Datenstruktur, die effizient im Raum ist und möglicherweise sublineare Präfix-Lookups bietet, ist der ternäre Suchbaum. Peter Kankowski has a fantastic article darüber. Er verwendet C, aber es ist einfacher Code, sobald Sie die Datenstruktur verstehen. Wie er bereits erwähnt hat, ist dies die Struktur, die ispell für die Rechtschreibkorrektur verwendet.

Answer 3

Ich habe dies (eine Trie-Implementierung) in C mit 8-Bit-Zeichen getan, und einfach die Array-Version verwendet (wie von der "26 Zeichen" -Antwort angedeutet).

ABER ich vermute, dass Sie volle Unicode-Unterstützung wollen (da ein .NET Char Unicode ist, neben anderen Gründen). Vorausgesetzt, Sie müssen Unterstützung für Unicode haben, ist die Hash/Map/Dictionary-Suche wahrscheinlich die beste Wahl, da ein 64K-Entry-Array in jedem Knoten nicht wirklich gut funktioniert.

Über den einzigen Hack-up, an den ich denken könnte, ist das Speichern von ganzen Strings (Suffixe oder möglicherweise "in-fixes") auf Zweigen, die noch nicht teilen, je nachdem, wie spärlich der Baum, äh, Trie ist . Das fügt jedoch eine Menge Logik hinzu, um die Zeichenketten mit mehreren Zeichenketten zu erkennen und sie aufzuteilen, wenn ein alternativer Pfad eingeführt wird.

Was ist das Lesen vs Update-Muster?

---- Update Juli 2013 ---

Wenn .NET Strings eine Funktion wie Java haben das Bytes für einen String (wie UTF-8) zu erhalten, dann in jedem Knoten ein Array mit darzustellen Der Byte-Wert der aktuellen Position ist wahrscheinlich ein guter Weg. Sie könnten sogar die Größe der Arrays verändern, mit ersten/letzten Begrenzungsindikatoren in jedem Knoten, da VIELE Knoten sowieso nur ASCII-Kleinbuchstaben oder nur Großbuchstaben oder die Ziffern 0-9 in einigen Fällen haben.

Answer 4

Wenn Sie Bedenken hinsichtlich des Speicherplatzes haben, können Sie die Bitmap-Komprimierung für die gültigen Byte-Übergänge verwenden, wobei Sie das 26-Zeichen-Limit annehmen.

class State // could be struct or whatever 
{ 
    int valid; // can handle 32 transitions -- each bit set is valid 
    vector<State> transitions; 

    State getNextState(int ch) 
    { 
     int index; 
     int mask = (1 << (toupper(ch) - 'A')) -1; 
     int bitsToCount = valid & mask; 

     for(index = 0; bitsToCount ; bitsToCount >>= 1) 
     { 
      index += bitsToCount & 1; 
     } 
     transitions.at(index); 
    } 
}; 

es andere Möglichkeiten gibt, die Bit-Zähleinheit Here, wird der Index in den Vektor ist die Anzahl der gesetzten Bits in dem gültigen BITSET zu tun. Die andere Alternative ist das direkt indexierte Array von Zuständen;

class State 
{ 
    State transitions[ 26 ]; // use the char as the index. 

    State getNextState(int ch) 
    { 
     return transitions[ ch ]; 
    } 
}; 

Answer 5

Ich habe gefunden burst trie's sehr platzsparend sein. Ich schrieb meine eigene burst trie in Scala, die auch einige Ideen wiederverwendet, die ich in der Trie-Implementierung von GWT fand. Ich habe es in Stripes Capture the Flag-Wettbewerb für ein Problem verwendet, das aus mehreren Knoten mit einer kleinen Menge RAM bestand.