Algorithms and Data Structures best suited for a spell checker, dictionary and a thesaurus

Question

Best way to implement a

• dictionary (is there any DS better than Trie for Dictionary)
• thesaurus (no idea, as match is made on meanings of the words, similar meanings)
• spell checker (something better than a hash map), if possible with correct spelling recommendations.

When asked in a one hour interview, are we expected to write a c/c++ code, for the algorithm?

Answer 1

I can see no better data structure than a trie for the dictionary and the thesaurus. Both can be fitted in one structure if needed with one link in the node pointing to the meaning of the word (dictionary) and one to synonyms (thesaurus). It can even offer some form of autocompletion (when there's only one link in the node).

Spelling corrector is a bit trickier - since one has to map fals input to some kind of correct input. You can take this link as a start: http://en.wikipedia.org/wiki/Spell_checker. At the end you'll find links to papers about different algorithms. According to the wikipedia article, this paper describes the most successfull algorithm: Andrew Golding and Dan Roth's "Winnow-based spelling correction algorithm"

Answer 2

See this for a 21-line Python 2.5 spelling corrector and a bit of background.