4
\$\begingroup\$

http://en.wikipedia.org/wiki/Trie

The basic idea is to support fast searches via prefix matching. In my implementation, I allow each node to store all of the words that match its given prefix, and then if the word length exceeds the length of the node's prefix, it passes the word into its children for further storage.

public class TrieNode
{
    private string Prefix { get; set; }
    private IList<string> Items { get; set; }
    private IDictionary<string, TrieNode> ChildNodes { get; set; }
    private IEqualityComparer<string> Comparer { get; set; }

    public TrieNode() : this(StringComparer.CurrentCulture) { }
    public TrieNode(IEqualityComparer<string> comparer) : this(comparer, string.Empty) { }

    private TrieNode(IEqualityComparer<string> comparer, string prefix)
    {
        if (prefix == null)
            throw new ArgumentNullException("Invalid prefix");

        this.Prefix = prefix;
        this.Items = new List<string>();
        this.ChildNodes = new Dictionary<string, TrieNode>(comparer);
        this.Comparer = comparer;
    }

    public void Add(string word)
    {
        if (word == null)
            throw new InvalidOperationException("Cannot add null to list");

        if (word.Length < this.Prefix.Length
            || !this.Comparer.Equals(word.Substring(0, this.Prefix.Length), this.Prefix))
        {
            throw new ArgumentException("Parameter does not match prefix.");
        } 

        this.Items.Add(word);

        if (word.Length > this.Prefix.Length)
        {
            string childKey = word.Substring(0, this.Prefix.Length + 1);
            if (!this.ChildNodes.ContainsKey(childKey))                
            {
                this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));                    
            }

            this.ChildNodes[childKey].Add(word);
        }
    }

    public void AddRange(IEnumerable<string> words)
    {
        foreach (string word in words)
            this.Add(word);
    }

    public ReadOnlyCollection<string> FindMatches(string searchPrefix)
    {
        if (searchPrefix == null)
            throw new InvalidOperationException("Cannot search on null strings");

        if (this.Comparer.Equals(searchPrefix, this.Prefix))
        {
            return new ReadOnlyCollection<string>(this.Items);
        }
        else
        {
            string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
            if (this.ChildNodes.ContainsKey(childKey))
                return this.ChildNodes[childKey].FindMatches(searchPrefix);
            else
                return new ReadOnlyCollection<string>(new string[0]); // empty list for no matches 
        }
    }
}

...

TrieNode trie = new TrieNode(StringComparer.CurrentCultureIgnoreCase);
trie.AddRange(new string[] { "Apple", "Banana", "BANANA", "Bar", "Berry", "Cherry", "Coconut", "Date" });

ReadOnlyCollection<string> matches = trie.FindMatches("BA"); // BANANA, banana, Bar

The slight concern I have is that each node contains its list of matching words, it's not an aggregation from its children. I call it slight, because it allows for easy logic when performing searches, as once a match is found, there's no need to further poll children and aggregate responses. On the other hand, I end up storing the same word in n lists, where n is the length of the word.

Edit An answer suggested returning an IEnumerable<string> to allow lazy streaming of results as well as to eliminate unnecessary copying. The tradeoff is that ordering is not preserved, and the code logic (at least, the way I tried it) is a bit less simple. But the quick changes I made to allow such a sequence are the following. First, inside the Add method, only storing matches to the specific prefix

if (this.Comparer.Equals(word, this.Prefix))
{
    // keep each match - preserves number of matches as well as differences 
    // if the comparer allows insensitive equality
    this.Items.Add(word); 
}

And then the FindMatches method

public IEnumerable<string> FindMatches(string searchPrefix)
{
    if (searchPrefix == null)
        throw new InvalidOperationException("Cannot search on null strings");

    if (this.Comparer.Equals(searchPrefix, this.Prefix))
    {
        return this.Items.Concat(this.ChildNodes.SelectMany(n => n.Value.FindMatches(n.Key)));
    }
    else
    {
        string childKey = searchPrefix.Substring(0, this.Prefix.Length + 1);
        if (this.ChildNodes.ContainsKey(childKey))
        {
            return this.ChildNodes[childKey].FindMatches(searchPrefix);
        }
        else
        {
            return Enumerable.Repeat(string.Empty, 0);
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

Instead of returning a collection, why not return an IEnumerable? Then you would perform no list copying, and it would be low cost to return an Enumerable that actually recurses through all the children lists.

\$\endgroup\$
  • \$\begingroup\$ If you have a coding suggestion for the IEnumerable<string> approach, I would welcome it. I wrote such an implementation, found it a bit more messy in terms of code and logic, but I recognize the tradeoff. For example, in my approach, order is preserved, logic is relatively simple, but there is more memory utilized and results cannot be lazily streamed. +1, though. \$\endgroup\$ – Anthony Pegram May 2 '11 at 23:28
  • \$\begingroup\$ If the order you want to preserve is sort order, then as long as you traverse the childNodes in sort order, and maintain the child lists in sort order, you should get the results in sort order. ab[cde] all come before ac[abf]. \$\endgroup\$ – Phil H May 3 '11 at 13:22
  • \$\begingroup\$ @Phil, I was thinking more of preserving a non-sorted original order, such that if the original input was "million", "millimeter", "milan", then a search for "mil" would return the results in the same order. I have an idea for how to still arrive at that result even with an IEnumerable approach and without excessive copies, which is basically to keep a single copy of the original list as an ordering mechanism for the otherwise decentralized output. \$\endgroup\$ – Anthony Pegram May 3 '11 at 17:19
  • \$\begingroup\$ @Anthony, consider keeping the position of each occurrence as a list of integers at each node. Then do an insertion sort into a new list as you pick up new items. \$\endgroup\$ – Phil H May 7 '11 at 17:52
5
\$\begingroup\$

Consider just storing a single character at each node. Currently, you are storing this:

given abc, abdfa, abdfb, bcd, efg

a : abc, abdfa, abdfb
. ab : abc, abdfa, abdfb
.. abc : abc
.. abd : abdfa, abdfb
b : bcd
. bc : bcd
.. bcd : bcd
e : efg
. ef : efg
.. efg : efg

However, just storing the character and a boolean for whether the cumulative prefix has been found:

a : F
. b : F
.. c : T
.. d : F
... f : F
.... a : T
.... d : T
b : F
. c : F
.. d : T
e : F
. f : F
.. g : T

Thus your add code would be:

public void Add(string wordExcess)
{
    /* validation etc here */

    if (wordExcess == "")
        this.Seen = true;
    else
    {
        // child key is just a char
        string childKey = wordExcess[0];
        if (!this.ChildNodes.ContainsKey(childKey))                
            this.ChildNodes.Add(childKey, new TrieNode(this.Comparer, childKey));                    

        string childExcess = wordExcess.Substring(1,wordExcess.Length-1);
        this.ChildNodes[childKey].Add(childExcess);
    }
}

Then iterating to find matches:

public IEnumerator FindMatches(string searchExcess)
{
    /** validation etc here **/

    if (searchExcess == "" && this.Seen)
        yield return this.Prefix;

    if (searchExcess.Length > 0)
    {
        string childKey = searchExcess[0];
        if (this.ChildNodes.ContainsKey(childKey))
        {
            string childExcess = searchExcess.Substring(1,childExcess.Length-1);
            foreach(string match in this.ChildNodes[childKey].FindMatches(searchExcess)
                yield return this.Prefix+match;
        }
    }
    else
    {
        foreach(KeyValuePair <string,TrieNode> pair in this.ChildNodes)
            foreach(string match in pair.Value.FindMatches(""))
                yield return this.Prefix+match;
    }
}

Here we are appending the current prefix to the matches as you return them, and a parent call will do the same. So the a.b.c.d node matches "" and returns "d" to the c.match, which returns "c"+"d" to the b.match which returns "b"+"cd" etc.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestion, I will attempt to perform a similar modification when I get a chance this evening. \$\endgroup\$ – Anthony Pegram May 3 '11 at 17:20
  • \$\begingroup\$ +1 Is there any reason why storing a character is better than a word (at each node)? \$\endgroup\$ – Legend Sep 11 '14 at 20:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.