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