How does spell checker and spell fixer of Google (or any search engine) work?

Question

When searching for something in Google, if you misspell a word (may be by mistake or may be when you really mean this non-dictionary word), Google says: "Showing results for ..... Search instead for .......".

I am trying to figure out how this would work. This basically means being able to find the closest dictionary word to the non-dictionary word entered. How does it work? One way I can guess is : count no. of instances of each character and then scan dictionary to find a word with same no. of instances of each character (only with +-1 difference). But this will also return anagrams.

Is some kind of probabilistic model of any use here such as Markov etc. I don't understand Markov well enough to throw it around but just a very wild guess.

Any insights?

Answer 1

You're forgetting that google has a lot more information available to it then you do. They track when people type in a word, don't select a result, and then do another search shortly afterwards. They then use this information to suggest better searches for you.

See How does the Google "Did you mean?" Algorithm work? for a fuller explanation.

Note that this approach makes sense when you consider that Google aren't actually doing spell-checking. Instead, they are trying to work out what search term will give you the answer you are looking for. Obviously there is a lot of overlap between this and spell-checking, but it means they are not always trying to correct a search for, e.g., "Flickr".

Answer 2

When you search something which is related to other searches performed earlied closed to yours and got more results, google shows suggest on them. We are sure that it is not spell checking but it shows what other people queried the related keywords.