Saw an interesting posting in MSN search blog about their spelling correction system implementation into their new MSN beta search, see what have are saying,

How do you spell Levenshtein?
Doing a good job of helping Search users to
correct misspelled queries is super important for two main reasons: a) 5 billion
crawled docs and a bleeding edge ranking algorithm can’t do much if the query
isn’t spelled right and b) more than 10% of all searches are misspelled! So we
made sure our new search engine included a revamped spelling correction system
that’s much better than our old one.
To improve the speller we worked with
Silviu Cucerzan and Eric Brill from Microsoft Research’s Text Mining, Search and
Navigation Group. Silviu and Eric have developed some novel techniques for using
search query statistics and iterative transformation of query strings to improve
spell correction. Their published paper on this topic – Spelling correction as
an iterative process that exploits the collective knowledge of web users –goes
into much more detail on some of the technical thinking that inspired the
spelling correction system we built.