Algorithms – Data Structure for Fast StartsWith Filtering of a Dictionary

algorithmsdata structures

I have a list of english words. I'm trying to come up with a data structure that allows me to do fast StartsWith filtering, like:

var words = dictionary.StartsWith("foo");

I was thinking of creating a data structure like this:

Data Structure

But I wanted to ask first:

a) Does the above data structure already have a name?

b) Is this the fastest way to implement what I'm looking for?

Edit: The data structure will be built at the beginning and not change. I'll only need to do the equivalent of StartsWith and Contains.

Best Answer

Check ternary search tries: http://en.wikipedia.org/wiki/Ternary_search_tree

It has very effective (probably the most effective) algorithm for word lookups including partial match.

If this is close to auto-complete implementation case then check this: http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

Related Topic