How Google does this?

When you type some thing wrong in Google, it asks do you mean some thing else?
How Google does this pretty good service.
.




Answer1:
I think it finds the closest string to the query string.
Here closeness to a string means number of steps required to convert from one string to another string.
It finds the string closest to the query string among the strings stored in its database and then it displays that string.

May be it also applies some optimization techniques also to search the relevant strings only.


Answer2:
It uses the Distance Edition algorithm


Answer3:
Closely matching string can be found out by the edit-distance and then It might be using a ranking schema to rank all the close matches, based on the search patterns (collected from past records).


Answer4:
When I type "einstn" it is suggesting "Einstein", but when I type "Einste" it is not showing any thing even though the string distance is two,may be they consider past data to suggest this as well as Rajat said.

Answer5:
It a spell check algorithm based on edit distance and probably phonetic soundex.

Answer6:
phonetic soundex...
I had something of that type in mind, but didn't know that this type of algorithms really exist. Good to know about it.

Answer7:
based on the edit distance
it chooses a letter according 2 qwerty keyboard i read it some where

like if someone types theu
then it will look for they becoz "y" is jus b4 "u" in qwerty keyboard and apply edit distance ...
taking the distance value according to distance of keys in keyboard and also the word in dictionary....

and also it has dictionary for most unspelled word (wrongly spelled)
eg speeled


Answer8:
google has repository of all the keywords of this universe

it has indexed more than billions of keywords by their context type

and once you start typing ,basically it keeps showing you the list of all words starting with the letter ,in order of search which have been searched often

it can be simply implemented by a trie structure or a dictionary

so google lateral search is more like searching a dictionary made of trie trees with one sub branch of nodes as a key word which are relevant to net users :)

i had created a context search engine in my 3rd year for a german company,so have knowledge about their such searching technique which were missing in google 2.5 years ago:)



Which Is Correct?