Auto correction , auto complete features

Question

Hii ,

We see suggestions when we type a word in Ms-word , google etc... How do they do that ?

I would like to know how the techniqueslike auto correct , auto complete , spell checking etc.. are performed . HOw are the words actually stored... what algorithms are followed ... ???

Any links that suggest a possible way are welcome,

Answer 1

Here are some data structures that are especially useful for working with (and finding) strings.

• Tries
• Suffix trees
• Directed acyclic word graphs
• Suffix array
• Patricia trie

These can be especially useful for auto-completion.

Here's a simple spell checker written in Python with a bit of digression on how it works.

In order to build a dictionary, you could "parse" e.g. wikipedia to collect known words.