How to Create a Trie in C#

How to create a trie in c#

This is my own code, pulled from my answer to How to find a word from arrays of characters? :

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

How can I make my trie more efficient?

I could just post a solution here that gives you 40 points but i guess this wont be any fun.

• Make use of Enumerator<char> instead of any string operations
• Count while adding values
• any charachter minus 'a' makes a good arrayindex (gives you values between 0 and 25)

Looking for the suffix tree implementation in C#?

Hei, just finished implementing .NET (c#) library containing different trie implementations. Among them:

• Classical trie
• Patricia trie
• Suffix trie
• A trie using Ukkonen's algorithm

I tried to make source code easy readable. Usage is also very straight forward:

using Gma.DataStructures.StringSearch;

...

var trie = new UkkonenTrie<int>(3);
//var trie = new SuffixTrie<int>(3);

trie.Add("hello", 1);
trie.Add("world", 2);
trie.Add("hell", 3);

var result = trie.Retrieve("hel");

The library is well tested and also published as TrieNet NuGet package.

See github.com/gmamaladze/trienet

---

Related Topics