Trie Umsetzung Frage

Question

Ich bin die Implementierung eines Trie für die prädiktive Texteingabe in VB.NET - im Grunde die automatische Vervollständigung, soweit die Verwendung des Trie betroffen ist. Ich habe meine trie eine rekursive Datenstruktur auf der Grundlage der generischen Klasse Dictionary.

Es ist im Grunde:

class WordTree Inherits Dictionary(of Char, WordTree)

Jeder Buchstabe in einem Wort (alle oberen verrohrten) als Schlüssel zu einer neuen WordTrie verwendet. Ein Null-Zeichen auf einem Blatt zeigt die Beendigung eines Wortes. Um ein Wort zu finden, mit einem Präfix beginnen ich die Trie so weit wie mein Präfix gehen geht dann alle Kinder Worte sammeln.

Meine Frage ist im Grunde über die Umsetzung des Trie selbst. Ich bin mit der Wörterbuch-Hash-Funktion meines Baum verzweigen. Ich könnte eine Liste verwenden und eine lineare Suche über die Liste tun, oder etwas anderes tun. Was ist die glatte Bewegung hier? Ist das eine vernünftige Art und Weise meiner Verzweigung zu tun?

Danke.

Aktualisieren:

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 verwendet nur Großbuchstaben, so vielleicht der Array Ansatz ist die beste. Ich könnte die gleiche Datenstruktur für eine komplexere typeahead Situation in der Zukunft (mehr Zeichen) verwenden. In diesem Fall klingt es wie das Wörterbuch der richtige Ansatz ist -. Bis zu dem Punkt, wo ich brauche etwas komplexer in der Regel zu verwenden,

Answer 1

Wenn es nur die 26 Buchstaben als 26 Eintrag Array. Dann ist Lookup durch den Index. Es nutzt wahrscheinlich weniger Platz als das Wörterbuch, wenn die Eimer-Liste länger als 26.

Answer 2

Wenn Sie sich Sorgen um Platz sind, können Sie Bitmap-Komprimierung auf den gültigen Byte Übergänge verwenden, die 26char Grenze angenommen wird.

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 gibt auch andere Möglichkeiten, um die Bit-Zählen zu tun Hier , die index in den Vektor ist die Anzahl der gesetzten Bits in dem gültigen BITSET. Die andere Alternative ist das direkte indiziertes Array von Staaten;

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

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

Answer 3

Eine gute Datenstruktur, die im Raum effizient ist und möglicherweise gibt sublinear Präfix Lookups ist der ternäre Suchbaum. Peter Kankowski hat einen fantastisch Artikel darüber. Er nutzt C, aber es ist einfach Code, wenn Sie die Datenstruktur zu verstehen. Als er erwähnte, ist dies die Struktur iSpell für Rechtschreibkorrektur verwendet.

Answer 4

Ich habe diese (eine Trie-Implementierung) erfolgen in C mit 8-Bit-Zeichen, und verwenden einfach die Array-Version (wie durch die "26 Zeichen" Antwort angedeutet).

Aber ich bin zu raten, dass Sie die volle Unicode-Unterstützung möchten (da ein .NET char Unicode ist, neben anderen Gründen). Vorausgesetzt, dass Sie Unterstützung haben müssen für Unicode, die Hash / map / Wörterbuchsuche ist wahrscheinlich die beste Wahl, als ein 64K-Eintrag Array in jedem Knoten wird wirklich sehr gut nicht.

über die nur zerhacken ich denken konnte hierzu ganze Strings zu speichern (Suffixe oder möglicherweise „in-fixen“) auf Zweige, die noch nicht gespalten tun, je nachdem, wie spärlich der Baum, äh, trie ist. Das fügt eine Menge von Logik, um die Multi-char-Strings zu erkennen, aber, und sie bis zu teilen, wenn ein alternativer Pfad eingeführt wird.

Was ist die Lese vs Update-Muster?

---- Update Juli 2013 ---

Wenn .NET Strings hat eine Funktion wie Java die Bytes für eine Zeichenfolge (als UTF-8) zu erhalten, dann einen Array in jedem Knoten mit der aktuellen Position der Byte-Wert darzustellen, ist wahrscheinlich ein guter Weg zu gehen. Man könnte sogar die Arrays variabler Größe machen, mit dem ersten / letzten Grenzen Indikatoren in jedem Knoten, da viele Knoten sowieso nur Kleinbuchstaben ASCII-Buchstaben haben, oder nur Großbuchstaben oder die Ziffern 0-9 in einigen Fällen.

Answer 5

ich gefunden habe platzen rel="nofollow"> als sehr platzsparend. Ich meine eigene platzen rel="nofollow">, die auch einige Ideen wieder verwendet, die ich gefunden in GWT Trie-Implementierung. Ich benutzte es in Streifen Capture the Flag-Wettbewerb auf ein Problem, das mit einer geringen Menge an RAM mit mehreren Knoten war.