Autocomplete functionality using prefix trees

Update: all the source code for this article can be accessed from here

This is a follow up to my previous post on implementing a prefix tree in C#.

This expands on that idea and uses the data structure to generate a list of autocomplete matches for a given input character sequence.

These are the modifications I brought to the code:

	private List<string> subsequentStrings;
	/// <summary>
	/// Create a prefix tree - the root node should always store ' '
	/// Initializae the list that will store the strings
	/// found during the autocomplete process
	/// </summary>
	public Tree()
	{
	_root = new Node(' ');
	subsequentStrings = new List<string>();
	}

view raw Prefix tree autocomplete functionality part 1 hosted with ❤ by GitHub

	/// <summary>
	/// get the autocomplete matches given the input
	/// </summary>
	/// <param name="query">the input</param>
	/// <returns>the list of autocomplete matches</returns>
	public List<string> GetMatches(string query)
	{
	StringBuilder sbPrevious = new StringBuilder();
	char[] chars = query.ToCharArray();
	Node currentNode = _root;
	Node child = null;
	for (int counter = 0; counter < chars.Length; counter++)
	{
	//form the sequence before the current char
	if(counter < chars.Length - 1)
	sbPrevious.Append(chars[counter]);
	child = currentNode.GetChild(chars[counter]);
	if (child == null)
	break;
	currentNode = child;
	}
	//clear the subsequent string storage
	subsequentStrings.Clear();
	GenerateSubsequentStrings(currentNode, sbPrevious.ToString());
	return subsequentStrings;
	}
	/// <summary>
	/// given a node and the current string generate the autocomplete matches recursively
	/// </summary>
	/// <param name="node">the current node</param>
	/// <param name="subsequentString">the current sequence</param>
	private void GenerateSubsequentStrings( Node node,
	string subsequentString)
	{
	//if there are no more nodes stop the recursion
	if(node == null)
	return;
	//add the current char to the current sequence
	subsequentString = subsequentString + node.Char;
	//if a word ends here add the current sequence to the autocomplete list
	if(node.AWordEndsHere)
	subsequentStrings.Add(subsequentString);
	//foreach child call the method recursively
	foreach (var subnode in node.Subtree)
	GenerateSubsequentStrings(subnode, subsequentString);
	}

view raw autocomplete prefix trees gist 2 hosted with ❤ by GitHub

This is the main program:

	Tree prefixTree = new Tree();
	prefixTree.AddWord("abc");
	prefixTree.AddWord("abcd");
	prefixTree.AddWord("abcde");
	prefixTree.AddWord("abcdef");
	prefixTree.AddWord("ab123cd");
	prefixTree.AddWord("abc123d");
	prefixTree.AddWord("abc132d");
	string word = "abc";
	if (prefixTree.Find(word))
	{
	var matches = prefixTree.GetMatches("abc");
	Console.WriteLine("gasit");
	Console.WriteLine("Autocomplete:");
	if (matches.Count > 0)
	foreach (var m in matches)
	Console.WriteLine(m);

view raw Prefix Tree Autocomplete Gist 3 hosted with ❤ by GitHub