How to detect a typo in a product search and suggest possible corrections?

Question

Given a very large database of product names, how would you detect possible typos in user searches and suggest possible corrections (Kinda like the way Google presents them)?

E.g.

User enters "fork handels" and presses 'search'.

They get back

"No results. Did you mean 'fork handles'?"

Answer 1

There are several approaches for this problem:

1. Keeping a table of most popular misspellings in your database. If you need some common misspellings: here)
2. Using an algorithm based on the edit distance: In information theory and computer science, the edit distance between two strings of characters is the number of operations required to transform one of them into the other. There are several different algorithms to define or calculate this metric. Read the Wikipedia article for the Levenshtein algorithm for example.
3. If you are using Lucene for full text search, here is a nice article which shows how to implement the "Did you mean" feature.
4. If you see that feature as simple spell-correction, here are some nice, very short implementations in several languages: How to Write a Spelling Corrector