Trie in C# - Example of prefix string search and substring search to implement auto-completion/Intelli-sense like features

George Mamaladze - .NET Data Structures for Prefix String Search and Substring (Infix) Search to Implement Auto-completion and Intelli-sense

Background

Typing a complete word in a search box is out. So if you are implementing a modern user friendly peace of software you will very probably need something like this:

I have seen many questions about an efficient way of implementing a (prefix or infix) search over a key value pairs where keys are strings (for instance see: http://stackoverflow.com/questions/10472881/search-liststring-for-string-startswith).

So it depends:

* If your data source is a SQL or some other indexed database holding your data it makes sense to utilize it’s search capabilities and issue a query to find matching records.

* If you have a small amount of data, a linear scan will be probably the most efficient.

* If you are searching in a large set of key value records you may need a special data structure to perform your search efficiently efficiently.

Trie

There is a family of data structures referred as Trie. In this post I want to focus on a c# implementations and usage of Trie data structures. If you want to find out more about the theory behind the data structure itself Google will be probably your best friend. In fact most of popular books on data structures and algorithms describe tries (see.: Advanced Data Structures by Peter Brass)

...

I came across this via George's CodePlex project today, https://trienet.codeplex.com, and thought it pretty darn interesting and cool. Now to see how I can use this in my code. I've cobbled together some much simpler and lamer, so I'd love to see if this will let me provide something much more polished.