Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
4  
en.wikipedia.org/wiki/Trie –  Ismail Badawi Feb 4 '13 at 0:00
add comment

2 Answers

up vote 2 down vote accepted

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/

share|improve this answer
add comment

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.

share|improve this answer
    
I added an edit with details on how the dictionary will be used. It will be built up front and not change. Thanks for your response! –  ConditionRacer Feb 4 '13 at 0:02
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.