c# - example - trie c

Cómo crear un trie en c#

Question

¿Alguien sabe dónde puedo encontrar un ejemplo de cómo construir un trie en C #. Estoy tratando de tomar un diccionario / lista de palabras y crear un trie con él.

Answer 1

Acabo de crear una implementación de Trie en C #:

https://github.com/TomGullen/C-Sharp-Trie/tree/master

Código:

/*
    Copyright (c) 2016 Scirra Ltd
    www.scirra.com

    Permission is hereby granted, free of charge, to any person obtaining a copy
    of this software and associated documentation files (the "Software"), to deal
    in the Software without restriction, including without limitation the rights
    to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
    copies of the Software, and to permit persons to whom the Software is
    furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in all
    copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
    AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
    OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
    SOFTWARE.
 */
public class Trie
{
    private class Node
    {
        public bool Terminal { get; set; }
        public Dictionary<char, Node> Nodes { get; private set; }
        public Node ParentNode { get; private set; }
        public char C { get; private set; }

        /// <summary>
        /// String word represented by this node
        /// </summary>
        public string Word
        {
            get
            {
                var b = new StringBuilder();
                b.Insert(0, C.ToString(CultureInfo.InvariantCulture));
                var selectedNode = ParentNode;
                while (selectedNode != null)
                {
                    b.Insert(0, selectedNode.C.ToString(CultureInfo.InvariantCulture));
                    selectedNode = selectedNode.ParentNode;
                }
                return b.ToString();
            }
        }

        public Node(Node parent, char c)
        {
            C = c;
            ParentNode = parent;
            Terminal = false;
            Nodes = new Dictionary<char, Node>();
        }

        /// <summary>
        /// Return list of terminal nodes under this node
        /// </summary>
        public IEnumerable<Node> TerminalNodes(char? ignoreChar = null)
        {
            var r = new List<Node>();
            if (Terminal) r.Add(this);
            foreach (var node in Nodes.Values)
            {
                if (ignoreChar != null && node.C == ignoreChar) continue;
                r = r.Concat(node.TerminalNodes()).ToList();
            }
            return r;
        } 
    }

    private Node TopNode_ { get; set; }
    private Node TopNode
    {
        get
        {
            if (TopNode_ == null) TopNode_ = new Node(null, '' '');
            return TopNode_;
        }
    }
    private bool CaseSensitive { get; set; }

    /// <summary>
    /// Get list of all words in trie that start with
    /// </summary>
    public HashSet<string> GetAutocompleteSuggestions(string wordStart, int fetchMax = 10)
    {
        if(fetchMax <= 0) throw new Exception("Fetch max must be positive integer.");

        wordStart = NormaliseWord(wordStart);

        var r = new HashSet<string>();

        var selectedNode = TopNode;
        foreach (var c in wordStart)
        {
            // Nothing starting with this word
            if (!selectedNode.Nodes.ContainsKey(c)) return r;
            selectedNode = selectedNode.Nodes[c];
        }

        // Get terminal nodes for this node
        {
            var terminalNodes = selectedNode.TerminalNodes().Take(fetchMax);
            foreach (var node in terminalNodes)
            {
                r.Add(node.Word);
            }
        }

        // Go up a node if not found enough suggestions
        if (r.Count < fetchMax)
        {
            var parentNode = selectedNode.ParentNode;
            if (parentNode != null)
            {
                var remainingToFetch = fetchMax - r.Count;
                var terminalNodes = parentNode.TerminalNodes(selectedNode.C).Take(remainingToFetch);
                foreach (var node in terminalNodes)
                {
                    r.Add(node.Word);
                }
            }
        }

        return r;
    } 

    /// <summary>
    /// Initialise instance of trie with set of words
    /// </summary>
    public Trie(IEnumerable<string> words, bool caseSensitive = false)
    {
        CaseSensitive = caseSensitive;
        foreach (var word in words)
        {
            AddWord(word);
        }
    }

    /// <summary>
    /// Add a single word to the trie
    /// </summary>
    public void AddWord(string word)
    {
        word = NormaliseWord(word);
        var selectedNode = TopNode;

        for (var i = 0; i < word.Length; i++)
        {
            var c = word[i];
            if (!selectedNode.Nodes.ContainsKey(c))
            {
                selectedNode.Nodes.Add(c, new Node(selectedNode, c));
            }
            selectedNode = selectedNode.Nodes[c];
        }
        selectedNode.Terminal = true;
    }

    /// <summary>
    /// Normalise word for trie
    /// </summary>
    private string NormaliseWord(string word)
    {
        if (String.IsNullOrWhiteSpace(word)) word = String.Empty;
        word = word.Trim();
        if (!CaseSensitive)
        {
            word = word.Trim();
        }
        return word;
    }

    /// <summary>
    /// Does this word exist in this trie?
    /// </summary>
    public bool IsWordInTrie(string word)
    {
        word = NormaliseWord(word);
        if (String.IsNullOrWhiteSpace(word)) return false;
        var selectedNode = TopNode;
        foreach (var c in word)
        {
            if (!selectedNode.Nodes.ContainsKey(c)) return false;
            selectedNode = selectedNode.Nodes[c];
        }
        return selectedNode.Terminal;
    }
}

Ejemplo de uso:

var trie = new Trie(new String[] {"hello", "help", "he-man", "happy", "hoppy", "tom"});

var autoCompleteSuggestions = trie.GetAutocompleteSuggestions("ha");
foreach (var s in autoCompleteSuggestions)
{
    Response.Write(s + "/n");
}

Answer 2

Aquí hay un Trie y un escáner en uno (tomados de la base de código de Resin ):

using System;
using System.Collections.Generic;
using System.IO;

namespace Resin
{
    public class UseTrie
    {
        public void Main()
        {
            var words = new[]{"pre", "prefix"};
            var trie = new Trie(words);

            // Print "pre" and "prefix"
            foreach(var word in trie.GetTokens("pr"))
            {
                Console.WriteLine(word);
            }
        }
    }
    public class Trie
    {
        public char Value { get; set; }

        public bool Eow { get; set; }

        public IDictionary<char, Trie> Children { get; set; }

        public bool Root { get; set; }

        public Trie(bool isRoot)
        {
            Root = isRoot;
            Children = new Dictionary<char, Trie>();
        }

        public Trie(IList<string> words)
        {
            if (words == null) throw new ArgumentNullException("words");

            Root = true;
            Children = new Dictionary<char, Trie>();

            foreach (var word in words)
            {
                AppendToDescendants(word);
            }
        }

        public Trie(string text)
        {
            if (string.IsNullOrWhiteSpace(text))
            {
                throw new ArgumentException("text");
            }

            Value = text[0];

            Children = new Dictionary<char, Trie>();

            if (text.Length > 1)
            {
                var overflow = text.Substring(1);
                if (overflow.Length > 0)
                {
                    AppendToDescendants(overflow);
                }
            }
            else
            {
                Eow = true;
            }
        }

        public IEnumerable<string> GetTokens(string prefix)
        {
            var words = new List<string>();
            Trie child;
            if (Children.TryGetValue(prefix[0], out child))
            {
                child.Scan(prefix, prefix, ref words);
            }
            return words;
        }

        private void Scan(string originalPrefix, string prefix, ref List<string> words)
        {
            if (string.IsNullOrWhiteSpace(prefix)) throw new ArgumentException("prefix");

            if (prefix.Length == 1 && prefix[0] == Value)
            {
                // The scan has reached its destination. Find words derived from this node.
                if (Eow) words.Add(originalPrefix);
                foreach (var node in Children.Values)
                {
                    node.Scan(originalPrefix+node.Value, new string(new []{node.Value}), ref words);
                }
            }
            else if (prefix[0] == Value)
            {
                Trie child;
                if (Children.TryGetValue(prefix[1], out child))
                {
                    child.Scan(originalPrefix, prefix.Substring(1), ref words);
                }
            }
        }

        public void AppendToDescendants(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");

            Trie child;
            if (!Children.TryGetValue(text[0], out child))
            {
                child = new Trie(text);
                Children.Add(text[0], child);
            }
            else
            {
                child.Append(text);
            }
        }

        public void Append(string text)
        {
            if (string.IsNullOrWhiteSpace(text)) throw new ArgumentException("text");
            if (text[0] != Value) throw new ArgumentOutOfRangeException("text");
            if (Root) throw new InvalidOperationException("When appending from the root, use AppendToDescendants.");

            var overflow = text.Substring(1);
            if (overflow.Length > 0)
            {
                AppendToDescendants(overflow);
            }
        }
    }
}

Answer 3

Echa un vistazo a este proyecto codeplex:

https://trienet.codeplex.com/

Es una biblioteca que contiene varias variantes diferentes de clases c # trie genéricas bien probadas, incluyendo patricia trie y trie paralelo.

• Trie - el trie simple, permite solo la búsqueda de prefijos, como .Where(s => s.StartsWith(searchString))
• SuffixTrie : también permite la búsqueda infija, como .Where(s => s.Contains(searchString))
• PatriciaTrie : comprimida, más compacta, un poco más eficiente durante la búsqueda, pero una acumulación bastante más lenta.
• SuffixPatriciaTrie : lo mismo que PatriciaTrie , que también permite la búsqueda infija.
• ParallelTrie : estructura de datos en paralelo implementada muy primitivamente que permite agregar datos y recuperar resultados de diferentes hilos simultáneamente.

Answer 4

El artículo a continuación URI tiene muy buena implementación y comparación con otra .NET Collection. También especifica el escenario en el que deberíamos usar Trie en lugar de construir .NET en colecciones como (HashSet <>, SortedList <>), etc.

https://visualstudiomagazine.com/articles/2015/10/20/text-pattern-search-trie-class-net.aspx

Answer 5

Este es mi propio código, extraído de mi respuesta a ¿Cómo encontrar una palabra de matrices de caracteres? :

public class Trie
{
  public struct Letter
  {
    public const string Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    public static implicit operator Letter(char c)
    {
      return new Letter() { Index = Chars.IndexOf(c) };
    }
    public int Index;
    public char ToChar()
    {
      return Chars[Index];
    }
    public override string ToString()
    {
      return Chars[Index].ToString();
    }
  }

  public class Node
  {
    public string Word;
    public bool IsTerminal { get { return Word != null; } }
    public Dictionary<Letter, Node> Edges = new Dictionary<Letter, Node>();
  }

  public Node Root = new Node();

  public Trie(string[] words)
  {
    for (int w = 0; w < words.Length; w++)
    {
      var word = words[w];
      var node = Root;
      for (int len = 1; len <= word.Length; len++)
      {
        var letter = word[len - 1];
        Node next;
        if (!node.Edges.TryGetValue(letter, out next))
        {
          next = new Node();
          if (len == word.Length)
          {
            next.Word = word;
          }
          node.Edges.Add(letter, next);
        }
        node = next;
      }
    }
  }

Answer 6

Resultados rápidos de google:
Tomado de: Trie Generic
Por Glenn Slayden
atribuido a Kerry D. Wong

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

public class Trie<TValue> : System.Collections.IEnumerable, IEnumerable<Trie<TValue>.TrieNodeBase>
{
    public abstract class TrieNodeBase
    {
        protected TValue m_value = default(TValue);

        public TValue Value
        {
            get { return m_value; }
            set { m_value = value; }
        }

        public bool HasValue { get { return !Object.Equals(m_value, default(TValue)); } }
        public abstract bool IsLeaf { get; }

        public abstract TrieNodeBase this[char c] { get; }

        public abstract TrieNodeBase[] Nodes { get; }

        public abstract void SetLeaf();

        public abstract int ChildCount { get; }

        public abstract bool ShouldOptimize { get; }

        public abstract KeyValuePair<Char, TrieNodeBase>[] CharNodePairs();

        public abstract TrieNodeBase AddChild(char c, ref int node_count);

        /// <summary>
        /// Includes current node value
        /// </summary>
        /// <returns></returns>
        public IEnumerable<TValue> SubsumedValues()
        {
            if (Value != null)
                yield return Value;
            if (Nodes != null)
                foreach (TrieNodeBase child in Nodes)
                    if (child != null)
                        foreach (TValue t in child.SubsumedValues())
                            yield return t;
        }

        /// <summary>
        /// Includes current node
        /// </summary>
        /// <returns></returns>
        public IEnumerable<TrieNodeBase> SubsumedNodes()
        {
            yield return this;
            if (Nodes != null)
                foreach (TrieNodeBase child in Nodes)
                    if (child != null)
                        foreach (TrieNodeBase n in child.SubsumedNodes())
                            yield return n;
        }

        /// <summary>
        /// Doesn''t include current node
        /// </summary>
        /// <returns></returns>
        public IEnumerable<TrieNodeBase> SubsumedNodesExceptThis()
        {
            if (Nodes != null)
                foreach (TrieNodeBase child in Nodes)
                    if (child != null)
                        foreach (TrieNodeBase n in child.SubsumedNodes())
                            yield return n;
        }

        /// <summary>
        /// Note: doesn''t de-optimize optimized nodes if re-run later
        /// </summary>
        public void OptimizeChildNodes()
        {
            if (Nodes != null)
                foreach (var q in CharNodePairs())
                {
                    TrieNodeBase n_old = q.Value;
                    if (n_old.ShouldOptimize)
                    {
                        TrieNodeBase n_new = new SparseTrieNode(n_old.CharNodePairs());
                        n_new.m_value = n_old.m_value;
                        Trie<TValue>.c_sparse_nodes++;
                        ReplaceChild(q.Key, n_new);
                    }
                    n_old.OptimizeChildNodes();
                }
        }

        public abstract void ReplaceChild(Char c, TrieNodeBase n);

    };

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    ///
    /// Sparse Trie Node
    ///
    /// currently, this one''s "nodes" value is never null, because we leave leaf nodes as the non-sparse type,
    /// (with nodes==null) and they currently never get converted back. Consequently, IsLeaf should always be ''false''.
    /// However, we''re gonna do the check anyway.
    /// 
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public class SparseTrieNode : TrieNodeBase
    {
        Dictionary<Char, TrieNodeBase> d;

        public SparseTrieNode(IEnumerable<KeyValuePair<Char, TrieNodeBase>> ie)
        {
            d = new Dictionary<char, TrieNodeBase>();
            foreach (var kvp in ie)
                d.Add(kvp.Key, kvp.Value);
        }

        public override TrieNodeBase this[Char c]
        {
            get
            {
                TrieNodeBase node;
                return d.TryGetValue(c, out node) ? node : null;
            }
        }

        public override TrieNodeBase[] Nodes { get { return d.Values.ToArray(); } }

        /// <summary>
        /// do not use in current form. This means, run OptimizeSparseNodes *after* any pruning
        /// </summary>
        public override void SetLeaf() { d = null; }

        public override int ChildCount { get { return d.Count; } }

        public override KeyValuePair<Char, TrieNodeBase>[] CharNodePairs()
        {
            return d.ToArray();
        }

        public override TrieNodeBase AddChild(char c, ref int node_count)
        {
            TrieNodeBase node;
            if (!d.TryGetValue(c, out node))
            {
                node = new TrieNode();
                node_count++;
                d.Add(c, node);
            }
            return node;
        }

        public override void ReplaceChild(Char c, TrieNodeBase n)
        {
            d[c] = n;
        }

        public override bool ShouldOptimize { get { return false; } }
        public override bool IsLeaf { get { return d == null; } }

    };

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    ///
    /// Non-sparse Trie Node
    ///
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public class TrieNode : TrieNodeBase
    {
        private TrieNodeBase[] nodes = null;
        private Char m_base;

        public override int ChildCount { get { return (nodes != null) ? nodes.Count(e => e != null) : 0; } }
        public int AllocatedChildCount { get { return (nodes != null) ? nodes.Length : 0; } }

        public override TrieNodeBase[] Nodes { get { return nodes; } }

        public override void SetLeaf() { nodes = null; }

        public override KeyValuePair<Char, TrieNodeBase>[] CharNodePairs()
        {
            KeyValuePair<Char, TrieNodeBase>[] rg = new KeyValuePair<char, TrieNodeBase>[ChildCount];
            Char ch = m_base;
            int i = 0;
            foreach (TrieNodeBase child in nodes)
            {
                if (child != null)
                    rg[i++] = new KeyValuePair<char, TrieNodeBase>(ch, child);
                ch++;
            }
            return rg;
        }

        public override TrieNodeBase this[char c]
        {
            get
            {
                if (nodes != null && m_base <= c && c < m_base + nodes.Length)
                    return nodes[c - m_base];
                return null;
            }
        }

        public override TrieNodeBase AddChild(char c, ref int node_count)
        {
            if (nodes == null)
            {
                m_base = c;
                nodes = new TrieNodeBase[1];
            }
            else if (c >= m_base + nodes.Length)
            {
                Array.Resize(ref nodes, c - m_base + 1);
            }
            else if (c < m_base)
            {
                Char c_new = (Char)(m_base - c);
                TrieNodeBase[] tmp = new TrieNodeBase[nodes.Length + c_new];
                nodes.CopyTo(tmp, c_new);
                m_base = c;
                nodes = tmp;
            }

            TrieNodeBase node = nodes[c - m_base];
            if (node == null)
            {
                node = new TrieNode();
                node_count++;
                nodes[c - m_base] = node;
            }
            return node;
        }

        public override void ReplaceChild(Char c, TrieNodeBase n)
        {
            if (nodes == null || c >= m_base + nodes.Length || c < m_base)
                throw new Exception();
            nodes[c - m_base] = n;
        }

        public override bool ShouldOptimize
        {
            get
            {
                if (nodes == null)
                    return false;
                return (ChildCount * 9 < nodes.Length);     // empirically determined optimal value (space & time)
            }
        }

        public override bool IsLeaf { get { return nodes == null; } }
    };

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    /// 
    /// Trie proper begins here
    ///
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

    private TrieNodeBase _root = new TrieNode();
    public int c_nodes = 0;
    public static int c_sparse_nodes = 0;

    // in combination with Add(...), enables C# 3.0 initialization syntax, even though it never seems to call it
    public System.Collections.IEnumerator GetEnumerator()
    {
        return _root.SubsumedNodes().GetEnumerator();
    }

    IEnumerator<TrieNodeBase> IEnumerable<TrieNodeBase>.GetEnumerator()
    {
        return _root.SubsumedNodes().GetEnumerator();
    }

    public IEnumerable<TValue> Values { get { return _root.SubsumedValues(); } }

    public void OptimizeSparseNodes()
    {
        if (_root.ShouldOptimize)
        {
            _root = new SparseTrieNode(_root.CharNodePairs());
            c_sparse_nodes++;
        }
        _root.OptimizeChildNodes();
    }

    public TrieNodeBase Root { get { return _root; } }

    public TrieNodeBase Add(String s, TValue v)
    {
        TrieNodeBase node = _root;
        foreach (Char c in s)
            node = node.AddChild(c,ref c_nodes);

        node.Value = v;
        return node;
    }

    public bool Contains(String s)
    {
        TrieNodeBase node = _root;
        foreach (Char c in s)
        {
            node = node[c];
            if (node == null)
                return false;
        }
        return node.HasValue;
    }

    /// <summary>
    /// Debug only; this is hideously inefficient
    /// </summary>
    public String GetKey(TrieNodeBase seek)
    {
        String sofar = String.Empty;

        GetKeyHelper fn = null;
        fn = (TrieNodeBase cur) =>
        {
            sofar += " ";   // placeholder
            foreach (var kvp in cur.CharNodePairs())
            {
                Util.SetStringChar(ref sofar, sofar.Length - 1, kvp.Key);
                if (kvp.Value == seek)
                    return true;
                if (kvp.Value.Nodes != null && fn(kvp.Value))
                    return true;
            }
            sofar = sofar.Substring(0, sofar.Length - 1);
            return false;
        };

        if (fn(_root))
            return sofar;
        return null;
    }


    /// <summary>
    /// Debug only; this is hideously inefficient
    /// </summary>
    delegate bool GetKeyHelper(TrieNodeBase cur);
    public String GetKey(TValue seek)
    {
        String sofar = String.Empty;

        GetKeyHelper fn = null;
        fn = (TrieNodeBase cur) =>
             {
                 sofar += " ";  // placeholder
                 foreach (var kvp in cur.CharNodePairs())
                 {
                     Util.SetStringChar(ref sofar, sofar.Length - 1, kvp.Key);
                     if (kvp.Value.Value != null && kvp.Value.Value.Equals(seek))
                         return true;
                     if (kvp.Value.Nodes != null && fn(kvp.Value))
                         return true;
                 }
                 sofar = sofar.Substring(0, sofar.Length - 1);
                 return false;
             };

        if (fn(_root))
            return sofar;
        return null;
    }

    public TrieNodeBase FindNode(String s_in)
    {
        TrieNodeBase node = _root;
        foreach (Char c in s_in)
            if ((node = node[c]) == null)
                return null;
        return node;
    }

    /// <summary>
    /// If continuation from the terminal node is possible with a different input string, then that node is not
    /// returned as a ''last'' node for the given input. In other words, ''last'' nodes must be leaf nodes, where
    /// continuation possibility is truly unknown. The presense of a nodes array that we couldn''t match to 
    /// means the search fails; it is not the design of the ''OrLast'' feature to provide ''closest'' or ''best''
    /// matching but rather to enable truncated tails still in the context of exact prefix matching.
    /// </summary>
    public TrieNodeBase FindNodeOrLast(String s_in, out bool f_exact)
    {
        TrieNodeBase node = _root;
        foreach (Char c in s_in)
        {
            if (node.IsLeaf)
            {
                f_exact = false;
                return node;
            }
            if ((node = node[c]) == null)
            {
                f_exact = false;
                return null;
            }
        }
        f_exact = true;
        return node;
    }

    // even though I found some articles that attest that using a foreach enumerator with arrays (and Lists)
    // returns a value type, thus avoiding spurious garbage, I had already changed the code to not use enumerator.
    public unsafe TValue Find(String s_in)
    {
        TrieNodeBase node = _root;
        fixed (Char* pin_s = s_in)
        {
            Char* p = pin_s;
            Char* p_end = p + s_in.Length;
            while (p < p_end)
            {
                if ((node = node[*p]) == null)
                    return default(TValue);
                p++;
            }
            return node.Value;
        }
    }

    public unsafe TValue Find(Char* p_tag, int cb_ctag)
    {
        TrieNodeBase node = _root;
        Char* p_end = p_tag + cb_ctag;
        while (p_tag < p_end)
        {
            if ((node = node[*p_tag]) == null)
                return default(TValue);
            p_tag++;
        }
        return node.Value;
    }

    public IEnumerable<TValue> FindAll(String s_in)
    {
        TrieNodeBase node = _root;
        foreach (Char c in s_in)
        {
            if ((node = node[c]) == null)
                break;
            if (node.Value != null)
                yield return node.Value;
        }
    }

    public IEnumerable<TValue> SubsumedValues(String s)
    {
        TrieNodeBase node = FindNode(s);
        if (node == null)
            return Enumerable.Empty<TValue>();
        return node.SubsumedValues();
    }

    public IEnumerable<TrieNodeBase> SubsumedNodes(String s)
    {
        TrieNodeBase node = FindNode(s);
        if (node == null)
            return Enumerable.Empty<TrieNodeBase>();
        return node.SubsumedNodes();
    }

    public IEnumerable<TValue> AllSubstringValues(String s)
    {
        int i_cur = 0;
        while (i_cur < s.Length)
        {
            TrieNodeBase node = _root;
            int i = i_cur;
            while (i < s.Length)
            {
                node = node[s[i]];
                if (node == null)
                    break;
                if (node.Value != null)
                    yield return node.Value;
                i++;
            }
            i_cur++;
        }
    }

    /// <summary>
    /// note: only returns nodes with non-null values
    /// </summary>
    public void DepthFirstTraverse(Action<String,TrieNodeBase> callback)
    {
        Char[] rgch = new Char[100];
        int depth = 0;

        Action<TrieNodeBase> fn = null;
        fn = (TrieNodeBase cur) =>
        {
            if (depth >= rgch.Length)
            {
                Char[] tmp = new Char[rgch.Length * 2];
                Buffer.BlockCopy(rgch, 0, tmp, 0, rgch.Length * sizeof(Char));
                rgch = tmp;
            }
            foreach (var kvp in cur.CharNodePairs())
            {
                rgch[depth] = kvp.Key;
                TrieNodeBase n = kvp.Value;
                if (n.Nodes != null)
                {
                    depth++;
                    fn(n);
                    depth--;
                }
                else if (n.Value == null)       // leaf nodes should always have a value
                    throw new Exception();

                if (n.Value != null)
                    callback(new String(rgch, 0, depth+1), n);
            }
        };

        fn(_root);
    }


    /// <summary>
    /// note: only returns nodes with non-null values
    /// </summary>
    public void EnumerateLeafPaths(Action<String,IEnumerable<TrieNodeBase>> callback)
    {
        Stack<TrieNodeBase> stk = new Stack<TrieNodeBase>();
        Char[] rgch = new Char[100];

        Action<TrieNodeBase> fn = null;
        fn = (TrieNodeBase cur) =>
        {
            if (stk.Count >= rgch.Length)
            {
                Char[] tmp = new Char[rgch.Length * 2];
                Buffer.BlockCopy(rgch, 0, tmp, 0, rgch.Length * sizeof(Char));
                rgch = tmp;
            }
            foreach (var kvp in cur.CharNodePairs())
            {
                rgch[stk.Count] = kvp.Key;
                TrieNodeBase n = kvp.Value;
                stk.Push(n);
                if (n.Nodes != null)
                    fn(n);
                else
                {
                    if (n.Value == null)        // leaf nodes should always have a value
                        throw new Exception();
                    callback(new String(rgch, 0, stk.Count), stk);
                }
                stk.Pop();
            }
        };

        fn(_root);
    }

    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    ///
    /// Convert a trie with one value type to another
    ///
    ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
    public Trie<TNew> ToTrie<TNew>(Func<TValue, TNew> value_converter)
    {
        Trie<TNew> t = new Trie<TNew>();
        DepthFirstTraverse((s,n)=>{
            t.Add(s,value_converter(n.Value));
        });
        return t;
    }
};

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
///
///
///
///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
public static class TrieExtension
{
    public static Trie<TValue> ToTrie<TValue>(this IEnumerable<String> src, Func<String, int, TValue> selector)
    {
        Trie<TValue> t = new Trie<TValue>();
        int idx = 0;
        foreach (String s in src)
            t.Add(s,selector(s,idx++));
        return t;
    }

    public static Trie<TValue> ToTrie<TValue>(this Dictionary<String, TValue> src)
    {
        Trie<TValue> t = new Trie<TValue>();
        foreach (var kvp in src)
            t.Add(kvp.Key, kvp.Value);
        return t;
    }

    public static IEnumerable<TValue> AllSubstringValues<TValue>(this String s, Trie<TValue> trie)
    {
        return trie.AllSubstringValues(s);
    }

    public static void AddToValueHashset<TKey, TValue>(this Dictionary<TKey, HashSet<TValue>> d, TKey k, TValue v)
    {
        HashSet<TValue> hs;
        if (d.TryGetValue(k, out hs))
            hs.Add(v);
        else
            d.Add(k, new HashSet<TValue> { v });
    }
};

Answer 7

Una simple implementación de Trie.

http://github.com/bharathkumarms/AlgorithmsMadeEasy/blob/master/AlgorithmsMadeEasy/Tries.cs

using System;
using System.Collections.Generic;
using System.Linq;

namespace AlgorithmsMadeEasy
{
    class Tries
    {
        TrieNode root;

        public void CreateRoot()
        {
            root = new TrieNode();
        }

        public void Add(char[] chars)
        {
            TrieNode tempRoot = root;
            int total = chars.Count() - 1;
            for (int i = 0; i < chars.Count(); i++)
            {
                TrieNode newTrie;
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];
                }
                else
                {
                    newTrie = new TrieNode();

                    if (total == i)
                    {
                        newTrie.endOfWord = true;
                    }

                    tempRoot.children.Add(chars[i], newTrie);
                    tempRoot = newTrie;
                }
            }
        }

        public bool FindPrefix(char[] chars)
        {
            TrieNode tempRoot = root;
            for (int i = 0; i < chars.Count(); i++)
            {
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];
                }
                else
                {
                    return false;
                }
            }
            return true;
        }

        public bool FindWord(char[] chars)
        {
            TrieNode tempRoot = root;
            int total = chars.Count() - 1;
            for (int i = 0; i < chars.Count(); i++)
            {
                if (tempRoot.children.Keys.Contains(chars[i]))
                {
                    tempRoot = tempRoot.children[chars[i]];

                    if (total == i)
                    {
                        if (tempRoot.endOfWord == true)
                        {
                            return true;
                        }
                    }
                }
                else
                {
                    return false;
                }
            }
            return false;
        }
    }

    public class TrieNode
    {
        public Dictionary<char, TrieNode> children = new Dictionary<char, TrieNode>();
        public bool endOfWord;
    }
}

/*
Calling Code:
    Tries t = new Tries();
    t.CreateRoot();
    t.Add("abc".ToCharArray());
    t.Add("abgl".ToCharArray());
    t.Add("cdf".ToCharArray());
    t.Add("abcd".ToCharArray());
    t.Add("lmn".ToCharArray());

    bool findPrefix1 = t.FindPrefix("ab".ToCharArray());
    bool findPrefix2 = t.FindPrefix("lo".ToCharArray());

    bool findWord1 = t.FindWord("lmn".ToCharArray());
    bool findWord2 = t.FindWord("ab".ToCharArray());
    bool findWord3 = t.FindWord("cdf".ToCharArray());
    bool findWord4 = t.FindWord("ghi".ToCharArray());
*/