How to Implement a dictionary in C/C++ with autoCorrect, auto-complete, spellcheck

Question

I have to write a C/C++ Code for a dictionary implementation with the following features:

There are basically definitions (1 or more) for words.

1) Insertion

2) Searching (As fast as possible)

3) Auto Complete

4) Auto Correct

5) Spell Check

So I need to know HOW TO DO SO?

Which data structures should be the most efficient? Trie or hast table or something else

Which searching technique to use...?

How to implement auto-complete and spell Checking effectively..?

Answer 1

Certainly you need a database with a list of words, then you need to split your text up into words and see if they exist in the database.

For Autocomplete you can just check that the text entered so far matches words in the dictionary (with a LIKE txt+'%' clause), implemented with an AJAX call.

Answer 2

You would typically use a tree of words, arranged according to edit distance from one another, such as a BK tree.

IIRC, the idea is to have a balanced tree with each word linked through edges numbered according to edit distance. If you want to find the nearest match for a word, you compute it's edit distance to the root word, then follow the root word's link of the same number, and repeat the process until you reach a leaf node which is either the same word, or the closest match.

EDIT: in hindsight, that article I linked does a much better job of explaining it than I did. I'd just recommend reading through it for a good explanation of the approach.