How does a search engine fix your typos and guess what you mean?
Two friends told a computer scientist they were amazed at how well Google could spell, so he wrote a toy version of it on a plane.
▶ Start the storyA search engine fixes your typos by comparing what you typed with words it knows, picking the likely candidates that are only a letter or two away, and choosing the one that people write most often. Then it tries to work out what you meant, not just what you typed. This step is called understanding: inferring the intent behind your keywords, and it generally happens before the engine retrieves and ranks any results.
In 2007, two friends told the computer scientist Peter Norvig that they were amazed at Google's spelling correction. Type in speling and Google instantly shows results for spelling. He figured that during a transcontinental plane ride he could write a toy spelling corrector that gets 80 or 90 percent right in about half a page of code, and he did start writing it on a plane.
The trick is to count edits. An edit is the insertion, deletion or substitution of one letter, and many tools also count swapping two neighbouring letters. Dictionary words one edit away from what you typed are highly likely to be what you meant; two edits away is less likely. If several words qualify, the one that appears most often in a big collection of text wins. For "thew", Norvig weighs two candidates: "thaw" changes just one letter, but "the" is a very common word, and perhaps the typist's finger simply slipped.
Step 1: You type
For example, "speling"
Step 2: Try one edit
Insert, delete, replace or swap a letter
Step 3: Keep real words
Only candidates found in the dictionary
Step 4: Pick the common one
The most frequent word wins
Step 5: Show results for it
"Showing results for: spelling"
Spelling is only one part. Engines also treat a phrase such as "New York" as one thing, not two words, and they can add or drop words to find more pages. Typos are common because people often search for things they don't know how to spell yet.
Quiz me
0/3
Recap
A spelling corrector looks at words a letter or two away from yours and picks the likeliest, weighing how common the word is against how likely the slip is.
💡 A trick to remember it · Count the slips, then pick the popular: close in letters, common in text.
Surprising fact · Typing speling returns results for spelling, a trick a computer scientist rebuilt in toy form on a plane ride.
Sources (4)
No source, no claim. Every fact in this lesson (18 claims) cites at least one of these.