Ich bekomme das Konzept hinter trie . Aber ich bin ein wenig verwirrt, wenn es um die Umsetzung geht.
Der offensichtlichste Weg, um einen Trie -Typ zu strukturieren, wäre, wenn ein Trie einen internen Dictionary<char, Trie> behalten würde. Ich habe tatsächlich einen auf diese Weise geschrieben, und es funktioniert , aber ... das scheint übertrieben zu sein. Mein Eindruck ist, dass ein Trie leichtgewichtig sein sollte, und ein separates Dictionary<char, Trie> für jeden Knoten scheint mir nicht sehr leicht zu sein.
Gibt es eine geeignetere Methode, um diese Struktur zu implementieren, die ich vermisse?
UPDATE : OK! Basierend auf den sehr hilfreichen Beiträgen von Jon und leppie ist das, was ich bisher herausgefunden habe:
(1) Ich habe den Trie -Typ, der ein privates _nodes -Member vom Typ Trie.INodeCollection hat.
(2) Die Schnittstelle Trie.INodeCollection hat folgende Mitglieder:
(3) Es gibt drei Implementierungen dieser Schnittstelle:
%Vor% (4) Wenn ein Trie zuerst erstellt wird, ist sein _nodes -Member null . Der erste Aufruf von Add erzeugt eine SingleNode , und nachfolgende Aufrufe von Add gehen von dort aus, entsprechend den oben beschriebenen Schritten.
Macht das Sinn? Das fühlt sich an wie eine Verbesserung in dem Sinne, dass es etwas die "Sperrigkeit" eines Trie reduziert (Knoten sind nicht länger vollwertige Dictionary<char, Trie> -Objekte, bis sie eine ausreichende Anzahl von Kindern haben). Es ist jedoch auch wesentlich komplexer geworden. Ist es zu kompliziert? Habe ich einen komplizierten Weg eingeschlagen, um etwas zu erreichen, das einfach hätte sein sollen?
Nun, Sie brauchen für jeden Knoten etwas, das effektiv implementiert IDictionary<char, Trie> . Sie könnten Ihre eigene benutzerdefinierte Implementierung schreiben, die ihre interne Struktur basierend auf der Anzahl der Unterknoten variiert:
char und ein Trie
List<Tuple<char, Trie>> oder LinkedList<Tuple<char,Trie>>
Dictionary<char, Trie>
(Nachdem ich gerade die Antwort von leppie gesehen habe, glaube ich, das ist die hybride Herangehensweise, von der er spricht, glaube ich.)
Wenn Ihre Zeichen aus einem begrenzten Satz sind (z. B. nur lateinisches Alphabet in Großbuchstaben), können Sie ein Array mit 26 Elementen speichern, und jede Suche ist nur
%Vor%wobei c das aktuelle Suchzeichen ist.
Wenn ich es als ein Wörterbuch implementiere, implementiere ich kein Trie - das ein Dictionary of Dictionaries implementiert.
Wenn ich einen Trie implementiert habe, habe ich es genauso gemacht wie von Damien_The_Unbeliever (+1 da) vorgeschlagen:
%Vor% Dies erfordert idealerweise, dass Ihr Trie nur eine begrenzte Teilmenge von Zeichen unterstützt, die durch no_of_chars angezeigt wird, und dass Sie Eingabezeichen den Ausgabe-Indizes zuordnen können. Z.B. Wenn Sie A-Z unterstützen, würden Sie natürlich A auf 0 und Z auf 25 abbilden.
Wenn Sie dann die Existenz eines Knotens hinzufügen / entfernen / prüfen müssen, dann tun Sie etwas wie folgt:
%Vor% In realen Fällen habe ich gesehen, dass dies optimiert ist, so dass beispielsweise AddNode ein ref TrieNode benötigt, so dass der Knoten bei Bedarf neu eingeordnet und automatisch an der richtigen Stelle in die Children des übergeordneten TrieNodes platziert werden kann / p>
Sie können stattdessen auch eine Ternary Search Tree verwenden, da der Speicheraufwand für einen Trie ziemlich wahnsinnig sein kann (besonders wenn Sie alle 32k Unicode-Zeichen unterstützen wollen!) und die TST-Performance ist ziemlich beeindruckend (und unterstützt auch Präfix und Amp ; Wildcard-Suche sowie Hamming-Suchen). Ebenso können TSTs alle Unicode-Zeichen nativ unterstützen, ohne eine Zuordnung vornehmen zu müssen. da sie an einer Größer / Kleiner-als-Gleich-Operation statt an einem absoluten Indexwert arbeiten.
Ich nahm den Code von hier und passte ihn leicht an (er wurde vor Generika geschrieben).
Ich denke, Sie werden von TSTs angenehm überrascht sein; Sobald ich einen implementiert hatte, habe ich mich komplett von Tries entfernt.
Das einzige Knifflige ist, den TST im Gleichgewicht zu halten; ein Problem, das Sie nicht mit Tries haben.
Es gibt einige Möglichkeiten, aber die Verwendung einer einzelnen Linkliste ist wahrscheinlich die einfachste und leichteste.
Ich würde einige Tests durchführen, um die Anzahl der Kindknoten zu sehen, die jeder Knoten hat. Wenn nicht viel (etwa 20 oder weniger), sollte der Link-Listen-Ansatz schneller sein als eine Hashtabelle. Je nach Anzahl der untergeordneten Knoten können Sie auch einen hybriden Ansatz verwenden.
Tags und Links .net data-structures trie dictionary implementation