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

Question

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

Die naheliegendste Art, wie ich denke, könnte eine Trie Art zu strukturieren wäre ein Trie haben eine interne Dictionary<char, Trie> zu halten. Ich habe in der Tat eine auf diese Weise geschrieben, und es funktioniert , aber ... das scheint übertrieben. Mein Eindruck ist, dass ein Trie leicht sein sollte, und mit einem separaten Dictionary<char, Trie> für jeder Knoten scheint nicht sehr leicht für mich.

Gibt es einen geeigneten Weg, um diese Struktur zu implementieren, dass ich fehle?

---

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

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

(2) Die Trie.INodeCollection Schnittstelle gehören folgende Mitglieder an:

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 erst aufgebaut ist, ist sein _nodes Mitglied null. Der erste Aufruf von Add schafft einen SingleNode und nachfolgende Aufrufe Add geht von dort, nach den oben beschriebenen Schritten.

Ist das sinnvoll? Das fühlt sich an wie eine Verbesserung in dem Sinne, dass es etwas die „Sperrigkeit“ einen Trie reduziert (Knoten sind nicht mehr ausgewachsene Dictionary<char, Trie> Objekte, bis sie eine ausreichende Anzahl von Kindern haben). Es hat sich aber auch deutlich komplexer geworden. Ist es zu gefaltet? Habe ich einen komplizierten Weg genommen, etwas zu erreichen, das war einfach haben sollte?

Answer 1

Nun, müssen Sie jeden Knoten, etwas zu haben, die effektiv Geräte 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, benutzen Sie einfach eine char und Trie
• Für eine kleine Zahl, verwenden Sie einen List<Tuple<char, Trie>> oder eine LinkedList<Tuple<char,Trie>>
• Für eine große Zahl, verwenden Sie einen Dictionary<char, Trie>

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

Answer 2

Wenn Ihr Zeichen aus einer begrenzten Menge ist (zum Beispiel nur Groß lateinischen 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.

Answer 3

es als Wörterbuch Implementierung, in meinem Kopf, ist nicht ein Trie Umsetzung -., Die ein Wörterbuch der Wörterbücher ist die Umsetzung

Als ich realisiert habe einen Trie ich es genauso gemacht habe, wie 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 von Zeichen durch no_of_chars angegeben unterstützen und dass Sie eingegebenen Zeichen ausgeben Indizes abbilden. Z.B. wenn die Unterstützung A-Z dann würden Sie natürlich eine Karte zu 0 und Z bis 25.

Wenn Sie dann müssen hinzufügen / entfernen / Check Existenz eines Knotens Sie dann etwas tun, wie folgt aus:

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 realen Fällen Ich habe dies so optimiert gesehen, dass AddNode zum Beispiel würde eine ref TrieNode nehmen, so dass der Knoten bei Bedarf und automatisch platziert in die Children der Eltern TrieNode newed werden kann an der richtigen Stelle.

Sie können auch einen Ternary Search Baum statt als Speicher-Overhead für einen Trie verwenden kann ziemlich verrückt sein (vor allem, wenn Sie beabsichtigen, alle 32k von Unicode-Zeichen zu unterstützen!) Und die TST Leistung ist ziemlich beeindruckend (und unterstützt auch die Vorsilbe & Wildcard-Suche sowie Hamming sucht). Ebenso können TSTs nativ alle Unicode-Zeichen unterstützen, ohne eine Zuordnung zu tun hat; da sie auf einer Arbeit Größer-als / Kleiner-als / gleich Betrieb anstelle eines absoluten Indexwert.

ich den Code nahm von hier und angepasst es leicht (es war geschrieben, bevor Generika).

Ich glaube, Sie werden angenehm überrascht sein von TSTs; einmal hatte ich realisiert, die ich ganz weg von Tries gelenkt werden.

Die einzige heikle Sache ist keeeping die TST ausgeglichen; ein Problem, Sie müssen nicht mit Tries.

Answer 4

Es gibt ein paar Möglichkeiten, aber eine einfach Linkliste verwenden, ist wahrscheinlich die einfachste und leicht.

Ich würde einige Tests tun, um die Menge des untergeordneten Knoten jeden Knoten zu sehen. Wenn nicht viel (20 sagen oder weniger), sollte der Link-Liste Ansatz schneller als eine Hash-Tabelle. Sie könnten auch einen hybriden Ansatz tun, abhängig von der Menge des untergeordneten Knoten.