¿Cuál sería una forma sensata de implementar un Trie en .NET?

Question

obtengo el concepto detrás de trie. Pero me confundo un poco cuando se trata de implementación.

La forma más obvia que podría pensar para estructurar un tipo Trie sería tener un Trie mantener un Dictionary<char, Trie> interno. De hecho, he escrito uno de esta manera, y funciona, pero ... esto parece exagerado. Mi impresión es que un trie debería ser liviano, y tener un Dictionary<char, Trie> por separado para cada nodo no me parece muy liviano.

¿Existe alguna forma más adecuada de implementar esta estructura que me falta?

---

ACTUALIZACIÓN: OK! Basándose en la información muy útil de Jon y leppie, esto es lo que he encontrado hasta el momento:

(1) que tienen el tipo Trie, que tiene una _nodes miembro privado de tipo Trie.INodeCollection.

(2) La interfaz Trie.INodeCollection tiene los siguientes miembros:

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

(3) Hay tres implementaciones de esta interfaz:

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) Cuando un Trie se construye primero, su miembro _nodes es null. La primera llamada al Add crea un SingleNode, y las llamadas posteriores al Add van desde allí, de acuerdo con los pasos descritos anteriormente.

¿Tiene esto sentido? Esto se siente como una mejora en el sentido de que algo reduce el "volumen" de un Trie (los nodos ya no son objetos completos Dictionary<char, Trie> hasta que tengan un número suficiente de hijos). Sin embargo, también se ha vuelto significativamente más complejo. ¿Es muy complicado? ¿He tomado una ruta complicada para lograr algo que debería haber sido sencillo?

Answer 1

Bueno, necesita que cada nodo tenga algo que efectivamente implemente IDictionary<char, Trie>.Usted puede escribir su propia implementación personalizada que varía su estructura interna basada en el número de subnodos que tiene:

• Para un solo nodo secundario, utilice sólo un char y una Trie
• Para un número pequeño, use un List<Tuple<char, Trie>> o un LinkedList<Tuple<char,Trie>>
• Para un gran número, utilice un Dictionary<char, Trie>

(Habiendo visto la respuesta de leppie, este es el tipo de enfoque híbrido habla, creo.)

Answer 2

Hay algunas maneras, pero el uso de una lista de enlaces individuales es probablemente la más simple y ligera.

Haría algunas pruebas para ver la cantidad de nodos secundarios que tiene cada nodo. Si no es mucho (digamos 20 o menos), el enfoque de la lista de enlaces debería ser más rápido que una tabla hash. También podría hacer un enfoque híbrido dependiendo de la cantidad de nodos secundarios.

Answer 3

Implementándolo como un diccionario, en mi opinión, no está implementando un Trie, eso es implementar un diccionario de diccionarios.

Cuando he implementado un trie lo he hecho de la misma manera como lo sugiere Damien_The_Unbeliever (1 allí):

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

Esto requiere idealmente luego de que su trie sólo apoyará un subconjunto limitado de caracteres indicados por no_of_chars y que puede asignar caracteres de entrada a los índices de salida. P.ej. si el apoyo AZ continuación, que, naturalmente, el mapa de A a Z a 0 y 25.

Cuando este caso es necesario añadir/eliminar/comprobar la existencia de un nodo, a continuación, hacer algo como esto:

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]; 
} 

En bienes casos que he visto esto optimizado para que AddNode, por ejemplo, tome un ref TrieNode para que el nodo se pueda actualizar a demanda y se coloque automáticamente en el Children de TrieNode padre en el lugar correcto.

También podría usar un árbol de búsqueda Ternary ya que la sobrecarga de memoria para un trie puede ser bastante loca (¡especialmente si intenta soportar los 32k de caracteres Unicode!) Y el rendimiento de TST es bastante impresionante (y también admite el prefijo & búsqueda de comodines, así como las búsquedas hamming). Del mismo modo, TST puede admitir de forma nativa todos los caracteres Unicode sin tener que hacer ningún mapeo; ya que trabajan en una operación mayor que/menor que/igual en lugar de un valor de índice absoluto.

Tomé el código from here y lo adapté ligeramente (fue escrito antes de los genéricos).

Creo que quedarás gratamente sorprendido con TST; una vez que tuve uno implementado me alejé de Tries por completo.

Lo único delicado es mantener equilibrado el TST; un problema que no tienes con Tries.

Answer 4

Si sus personajes son de un conjunto limitado (por ejemplo, solamente el alfabeto latino en mayúsculas), entonces usted puede almacenar una matriz de 26 elementos, y cada búsqueda es sólo

Trie next = store[c-'A'] 

donde c es el carácter de búsqueda actual.