0

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.

1

2 Answers 2

3

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/

2
  • Upvote, with a caveat. If you're really concerned about performance (e.g. router firmware), patricia tries are friendlier to the cache. Much the same as the ternary search tree, albeit child nodes are only created at the start of unique runs (thus inherently have fewer nodes). Deference is bad for the cache, so fewer nodes are better. en.wikipedia.org/wiki/Radix_tree Mar 3, 2016 at 13:11
  • 1
    @JonathanDickinson I agree that patricia tries have less nodes but each node in PT is of variable size. While node in TT is a fixed size structure and so the whole tree can be contained in single and compact vector<tt_node>.
    – c-smile
    Mar 3, 2016 at 17:42
1

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.

1
  • 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! Feb 4, 2013 at 0:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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