Auto correct algorithm

Question

I want to implement the following in C++:

1) Check whether the given word exists in a dictionary. The dictionary file is a huge file; consider 100MB or 3-4 Million words.

2) Suggest corrections for the incorrect word.

3) Autocomplete feature.

My Approach

1) I am planning to build a tree so searching will efficient.

2) I am not getting how to implement auto correction feature.

3) I can implement auto complete feature using trees

What's the best data structure and algorithm to implement all the above features?

Answer 1

I have been working on the same problem. So far the best solution I have come across is using a ternary search tree for auto completion. Ternary Search Trees are more space efficient than tries. If im unable to find the looked up string in my ternary search tree then I use an already built BK Tree for finding the closest match. BK Tree internally uses Levenshtein distance. You

Metaphones are also something you might want to explore however I havent gone into the depth of metaphones.

I have a solution in Java for BK TREE + TERNARY SEARCH TREE if you like.

Answer 2

You can do autocomplete by looking at all the strings in a given subtree. Some score to help you pick might help. This works something like if you have "te" you go down that path in the trie and the traverse the entire subtree there to get all the possible endings.

For corrections you need to implement something like http://en.wikipedia.org/wiki/Levenshtein_distance over the tree. You can use the fact that if you processed a given path in the trie, you can reuse the result for all the strings in the subtree rooted at the end of your path.