Was wäre ein sinnvoller Weg, ein Trie in .NET zu implementieren?

Question

Ich bekomme das Konzept hinter einem trie. Aber ich bin ein wenig verwirrt, wenn es um die Umsetzung geht.

Der offensichtlichste Weg, den ich denken könnte, um eine Trie Art zu strukturieren, wäre eine Trie pflegen eine interne Dictionary<char, Trie> zu haben. Ich habe tatsächlich eine auf diese Weise geschrieben, und es funktioniert, aber ... das scheint wie Overkill. Mein Eindruck ist, dass ein Trie leicht sein sollte, und eine separate Dictionary<char, Trie> für jeden Knoten scheint mir nicht sehr leicht.

Gibt es eine geeignetere Methode, um diese Struktur zu implementieren, die ich vermisse?

---

UPDATE: OK! Basierend auf die sehr hilfreich Eingabe von Jon und leppie, ist das, was ich mit so weit habe kommen:

(1) Ich habe den Trie Typen, der Trie.INodeCollection ein eigenes _nodes Mitglied des Typs hat.

(2) Die Trie.INodeCollection Schnittstelle hat die folgenden Mitglieder:

interface INodeCollection 
{ 
    bool TryGetNode(char key, out Trie node); 
    INodeCollection Add(char key, Trie node); 
    IEnumerable<Trie> GetNodes(); 
} 

(3) Es gibt drei Implementierungen dieser Schnittstelle:

class SingleNode : INodeCollection 
{ 
    internal readonly char _key; 
    internal readonly Trie _trie; 

    public SingleNode(char key, Trie trie) 
    { /*...*/ } 

    // Add returns a SmallNodeCollection. 
} 

class SmallNodeCollection : INodeCollection 
{ 
    const int MaximumSize = 8; // ? 

    internal readonly List<KeyValuePair<char, Trie>> _nodes; 

    public SmallNodeCollection(SingleNode node, char key, Trie trie) 
    { /*...*/ } 

    // Add adds to the list and returns the current instance until MaximumSize, 
    // after which point it returns a LargeNodeCollection. 
} 

class LargeNodeCollection : INodeCollection 
{ 
    private readonly Dictionary<char, Trie> _nodes; 

    public LargeNodeCollection(SmallNodeCollection nodes, char key, Trie trie) 
    { /*...*/ } 

    // Add adds to the dictionary and returns the current instance. 
} 

(4) Wenn ein Trie zuerst aufgebaut wird, sein _nodes Mitglied ist null. Der erste Aufruf an Add erstellt eine SingleNode, und nachfolgende Aufrufe an Add gehen von dort, entsprechend den oben beschriebenen Schritten.

Macht das Sinn? Dies fühlt sich an wie eine Verbesserung in dem Sinne, dass es etwas reduziert die "Sperrigkeit" von Trie (Knoten sind nicht mehr voll 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?

Answer 1

Nun, Sie brauchen jeden Knoten, um etwas zu haben, effektiv implementiert IDictionary<char, Trie>.Sie könnten Ihre eigene benutzerdefinierte Implementierung schreiben, die seine innere Struktur variiert je nachdem, wie viele untergeordnete Knoten hat:

• Für einen untergeordneten Knoten, verwenden Sie nur ein char und ein Trie
• Für eine kleine Zahl, verwenden Sie ein List<Tuple<char, Trie>> oder ein LinkedList<Tuple<char,Trie>>
• Für eine große Zahl, verwenden Sie einen Dictionary<char, Trie>

(Da ich gerade leppie Antwort gesehen, das ist die Art von Hybrid-Ansatz spricht er über, glaube ich.)

Answer 2

Es gibt ein paar 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.

Answer 3

Implementieren Sie es als ein Wörterbuch, in meinen Gedanken, implementiert keine Trie - das ist ein Dictionary of Dictionaries implementieren.

Als ich realisiert habe einen Trie ich getan habe es auf die gleiche Weise wie durch Damien_The_Unbeliever vorgeschlagen (+1 dort):

public class TrieNode 
{ 
    TrieNode[] Children = new TrieNode[no_of_chars]; 
} 

Dies erfordert idealerweise dann, dass Ihre Trie wird nur eine begrenzte Teilmenge Unterstützung von Zeichen, die durch no_of_chars angezeigt werden und dass Sie Eingabezeichen zu Ausgabe-Indizes zuordnen können. Z.B. wenn die Unterstützung AZ dann würden Sie natürlich A auf 0 und Z bis 25. Karte

Wenn Sie dann hinzufügen müssen/entfernen/Check Existenz eines Knotens Sie dann so etwas tun:

public TrieNode GetNode(char c) 
{ 
    //mapping function - could be a lookup table, or simple arithmetic 
    int index = GetIndex(c); 
    //TODO: deal with the situation where 'c' is not supported by the map 
    return Children[index]; 
} 

In Echt Fälle, die ich gesehen habe dies optimiert, so dass AddNode, zum Beispiel, würde eine ref TrieNode nehmen, so dass der Knoten auf Anforderung neu und automatisch in die Children des Elternteils TrieNode an der richtigen Stelle platziert werden kann.

Sie könnten auch eine Ternary Search Tree verwenden, da der Speicheraufwand für einen Trie ziemlich verrückt sein kann (besonders wenn Sie alle 32k Unicode-Zeichen unterstützen wollen!) Und die TST-Leistung ist ziemlich beeindruckend (und unterstützt auch Präfix) & 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 from here und angepasst es leicht (es wurde vor Generika geschrieben).

Ich denke, Sie werden von TSTs angenehm überrascht sein; Sobald ich eine implementiert hatte, steuerte ich komplett von Tries ab.

Die einzige knifflige Sache ist, die TST ausgeglichen zu halten; Ein Problem, das Sie bei Tries nicht haben.

Answer 4

Wenn Ihr Zeichen aus einer begrenzten Menge ist (zum Beispiel nur Groß lateinisches Alphabet), dann können Sie eine 26-Element-Array speichern und jede Lookup ist nur

Trie next = store[c-'A'] 

wobei c das aktuelle Lookup-Zeichen ist.