Data structure for fast StartsWith filtering of a dictionary

Question

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:

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.

Answer 1

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/

Answer 2

This isn't identical to, but very similar to a B-tree. It's a generalization on a binary search tree. A binary search tree stores one value at each node, and has two children, with the left subtree guaranteed less than that node, and the right subtree guaranteed greater. With a B-tree, you store k values in sorted order at each node, and allow k+1 children based on in between which two children it lies. This is basically the same thing, except that you have equality instead of inequality (since there are only 26 possible choices at each step). Also, note how in your case you aren't actually storing data at each node, each node just uses the same letters a-z to determine which child to follow down. So you'd likely store children at the leaves. I'm not sure exactly how balance would work out; you'd need to create new nodes whenever you inserted a word that shared the same prefix as another words in terms of nodes you already had.

In your case, you need to give more details so we can answer b). If your list of words is fixed and doesn't change, your best bet might actually be just a simple array. Just sort it once. Then to find all words starting with "foo", you simply do binary search to find "foo" and "fop", or the close possible matches (rounded in the appropriate directions). You then return all the words between them. This will give you logN + numResults in time complexity. It's also likely to have very good constants as you don't have to follow a lot of pointers around. Also has virtually zero space overhead. Obviously, if you are adding words to your dictionary on a regular basis this is not a good solution as adding a word costs O(N), whereas tree solutions will probably cost O(logN) to add a word.