How a search finds the right page despite a typo
Keyword search needs every word spelled exactly right. People mistype, and names can be spelled several ways. Fuzzy search measures how close two words are instead of asking whether they are identical. You will try four ways to measure closeness: counting letter changes, sharing pieces of letters, comparing how words sound, and finishing a half-typed word. Every number is shown, so you can check each one by hand.
Try this first
- Open “Read the 10 documents” below. They describe a made-up island, Fernport. Each document’s title counts as part of its text.
- In Typos and edit distance, look at the table for “okafur” and “okafor”. Find the bottom-right cell: that is the distance.
- Change one word in the table and predict the new distance before you read it.
- In Character pieces, compare “harbor” and “harbour”: which pieces do they share?
- In Sounds alike, see that “okafur” and “okafor” get the same code.
- In Autocomplete, press “lig”, then type one more letter.
- In Compare, press “okafur” to see what exact search misses.
Read the 10 documents
Fernport is a made-up island. A document’s title counts as part of its text when the vocabulary is built.
- Fernport Bakery
- Fernport Bakery stands on Harbour Street. It is run by Mira Okafor. Mira is famous for her dark rye bread, baked only on Tuesdays. She learned to bake from Tomas Reyes when she was sixteen. The shop opens at 7 in the morning and closes when the bread is gone.
- Fernport Lighthouse
- The Fernport Lighthouse was built in 1891 on the north cliff. Its lamp can be seen 30 kilometres out at sea. Guided tours run on Saturdays and Sundays at 10:00 and 14:00. The guide is Tomas Reyes, who has climbed the lighthouse’s 120 stairs every week for 20 years. The lighthouse is closed in January for repairs.
- Ferry timetable
- The ferry crosses from Millbay on the mainland to Fernport in 40 minutes. A ferry fare costs 6 coins, and children ride free. Bikes travel for 1 coin more. December to February is the quiet season. Then there is only one crossing a day, at 10:00 from Millbay. The rest of the year, the ferry leaves Millbay at 8:00, 12:00 and 17:00.
- Lantern Festival
- The Lantern Festival lights up Fernport every October. People hang paper lanterns along Harbour Street for a week. On the last night of the festival, everyone walks to the north cliff to watch the lighthouse lamp switch on.
- Visitor rules
- Visitors may camp only at the campsite behind the school. Fires are allowed on the beach, but never in the woods. Dogs must stay on a lead near the harbour.
- Harbour guide
- The Fernport harbour is the busiest place in town. The harbour has a long stone wall, and the harbour wall keeps the water calm inside. Fishers bring their catch to the harbour at dawn, and the harbour market sells it fresh by seven. Every morning the harbour fills with gulls, nets and carts. The ferry from the mainland ties up at the harbour, at the far end of the east pier. A small harbour office hands out maps and answers questions. The harbour café serves hot soup to anyone who is cold. Walk along the harbour edge at sunset to see the water turn orange. At night the harbour is lit by a row of yellow lamps, and the harbour is quiet. The harbour crane lifts crates of apples, wool and salt from the quay onto carts. Young children feed the gulls near the harbour steps, while old fishers mend their nets and trade stories about the weather. Two painted sheds beside the harbour store ropes, buoys and lamps. A harbour bell rings at noon, and again when the tide turns. Anyone who loves the sea should spend a slow afternoon at the harbour.
- Fernport School
- Fernport School teaches about forty children, from age five to twelve. Classes start at 9 in the morning and end at 3. Every child learns to swim in the sea pool, and older children learn to sail. The school library is open to the whole town on Wednesdays. The school choir sings at the end of every term.
- Saturday market
- The Saturday market fills the square beside the town hall. Farmers sell apples, honey and goat cheese. Weavers sell wool scarves and hats. A woman named Ida Lund sells smoked fish from a blue stall. The market opens at 8 in the morning and packs up at noon.
- Weather and seasons
- Fernport is mild and damp. Summer days reach about 22 degrees, and the sea is warm enough to swim in July and August. Autumn brings strong winds from the west. Fog often covers the cliffs in the early morning. It snows only once or twice a year, and the snow melts by noon.
- History of Fernport
- Fernport began as a fishing village about 400 years ago. The first stone houses were built in 1650, from rock taken from the cliffs. A great storm in 1702 washed away the old pier, and the town built a new one. In 1950 a bridge was planned, but the islanders voted against it. Today about 900 people live in Fernport.
Chapter 1: Typos and edit distance: count the fixes
Exact search fails the moment you mistype a word. Edit distance counts the smallest number of single-letter changes that turn one word into another. A change is an insertion (add a letter), a deletion (remove one) or a substitution (swap one for another), and each costs 1. The table below does the counting for you: each cell is the distance between the first few letters of the top word and the first few letters of the side word, and the bottom-right cell is the answer. Each cell is the smallest of three things: the cell above plus 1 (a deletion), the cell to the left plus 1 (an insertion), or the cell diagonally above-left plus 0 if the two letters match or plus 1 if not (a substitution). Below the table, the search lists every word in the documents within 2 changes of your word, closest first.
The table starts with “okafur” and “okafor”: one letter differs, so the distance is 1. Change the words and check the bottom-right cell by hand. Then press “ligthouse” in the search.
Try two words
Edit distance between okafur and okafor is 1.
Scroll sideways to see every column.
| Letters of okafur down, letters of okafor across | (none) | o | k | a | f | o | r |
|---|---|---|---|---|---|---|---|
| (none) | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
| o | 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| k | 2 | 1 | 0 | 1 | 2 | 3 | 4 |
| a | 3 | 2 | 1 | 0 | 1 | 2 | 3 |
| f | 4 | 3 | 2 | 1 | 0 | 1 | 2 |
| u | 5 | 4 | 3 | 2 | 1 | 1 | 2 |
| r | 6 | 5 | 4 | 3 | 2 | 2 | 1 |
Distance: 1. Read the bottom-right cell.
Search the documents
1 word in 1 document found.
Words found
- okafor distance 1
Documents that use these words
- Fernport Bakery
Chapter 2: Character pieces: match by shared trigrams
Another way to forgive a typo is to cut each word into overlapping pieces of 3 letters (trigrams) and see how many pieces two words share. Each word gets a $ added at both ends first (padding), so the first and last letters make their own pieces. The score is the Jaccard score: pieces both words have, divided by all different pieces in either word. 1 means identical, 0 means nothing in common. This search keeps words that score 0.3 or more.
Try “harbor” against “harbour” in the table: they share most pieces, so the score is high. Then press “ferri” and see “ferry” appear even though one letter changed.
Try two words
harbor and harbour share 4 pieces of 9. Score 0.444.
- Pieces of harbor (padded as $harbor$)
- $ha arb bor har or$ rbo
- Pieces of harbour (padded as $harbour$)
- $ha arb bou har our rbo ur$
- Shared pieces: 4
- $ha arb har rbo
Jaccard score = 4 shared ÷ 9 different pieces in all = 0.444
Search the documents
1 word in 2 documents found.
Words found
- ferry score 0.429, shares $fe err fer
Documents that use these words
- Ferry timetable
- Harbour guide
Chapter 3: Sounds alike: Soundex codes
Sometimes a name is spelled differently but sounds the same. Soundex turns a word into a code: its first letter, then 3 digits. Letters that sound alike share a digit (b, f, p, v are 1; c, g, j, k, q, s, x, z are 2; d, t are 3; l is 4; m, n are 5; r is 6). Vowels, h, w and y get no digit. A digit is skipped when the letter before it has the same digit. h and w do not break a run, but a vowel does. The code is cut or filled with 0 to be exactly 4 characters. Two words with the same code “sound alike”. This is the American Soundex rule set.
“Okafur” and “Okafor” get the same code, so Soundex finds the bakery’s owner even with the wrong vowel. Soundex is rough, though: it keeps the first letter, so a mistake there is not forgiven.
Try two words
okafur has code O216 and okafor has code O216. They sound alike.
- okafur: code O216
- O: first letter, kept as it isK: digit 2, addedA: no digit for this letter, skippedF: digit 1, addedU: no digit for this letter, skippedR: digit 6, addedThen the code is cut or filled with 0 to be 4 characters.
- okafor: code O216
- O: first letter, kept as it isK: digit 2, addedA: no digit for this letter, skippedF: digit 1, addedO: no digit for this letter, skippedR: digit 6, addedThen the code is cut or filled with 0 to be 4 characters.
Same code, so they sound alike.
Search the documents
1 word in 1 document found.
Words found
- okafor code O216
Documents that use these words
- Fernport Bakery
Chapter 4: Autocomplete: finish the word as you type
Autocomplete lists the words that start with what you have typed so far (the prefix). The list comes from the vocabulary: every different search word in the documents. The words are ordered by how many documents use them, most first, then alphabetically. It needs at least 2 letters, because one letter matches far too many words.
Press “lig”: “lighthouse” comes first because more documents use it than any other word starting with “lig”. Now add a letter at a time and watch the list shrink.
Search the documents
2 words in 2 documents found.
Words found
- lighthouse in 5 documents
- light in 1 document
Documents that use these words
- Fernport Lighthouse
- Lantern Festival
Chapter 5: Compare: what exact search misses
Here one question goes through the four fuzzy methods and, at the end, through plain keyword search (an exact match: the word must be spelled exactly the same). When the question has a typo, exact matching finds nothing, while the fuzzy methods still reach the right documents. Edit distance uses at most 2 changes.
Try “okafur”: keyword search finds no document, but edit distance, trigrams and Soundex all find the bakery. Autocomplete finds nothing for it, because no word starts with “okafur”.
Search the documents
Edit distance: 1 word in 1 document. Trigrams: 1 word in 1 document. Sound: 1 word in 1 document. Autocomplete: 0 words in 0 documents. Exact keyword search: 0 documents.
Edit distance
- okafor distance 1
- Fernport Bakery
Trigrams
- okafor score 0.333, shares $ok kaf oka
- Fernport Bakery
Sound (Soundex)
- okafor code O216
- Fernport Bakery
Autocomplete
No word found.
No document matches.
Exact keyword search
The word must be spelled exactly the same.
No document matches.
Word list
- Fuzzy search
- Search that still finds the right thing when your words are not exactly right: a typo, a different spelling, or only the start of a word.
- Exact match
- A match only when the word is spelled exactly the same. “okafur” does not exactly match “okafor”.
- Typo
- A small spelling mistake, like “ligthouse” for “lighthouse”.
- Edit distance
- The smallest number of single-letter changes (insertions, deletions and substitutions) that turn one word into another. Also called Levenshtein distance.
- Insertion
- Adding one letter. “fery” to “ferry” is one insertion.
- Deletion
- Removing one letter. “ferry” to “fery” is one deletion.
- Substitution
- Swapping one letter for another. “okafur” to “okafor” is one substitution.
- Table cell
- One box of the table. Here each cell holds the edit distance between the first few letters of the two words.
- Vocabulary
- The list of every different search word in the documents. Fuzzy search compares your word with each word in it.
- Character n-gram
- A piece of a word that is n letters long. Cut “harbour” into overlapping pieces of 3 letters and you have its trigrams.
- Piece
- One trigram: 3 letters of a word in a row. “harbour” padded as $harbour$ has pieces such as $ha, har and arb.
- Trigram
- A character n-gram where n is 3: a piece of 3 letters.
- Padding
- Adding a $ at the start and end of a word before cutting it into trigrams, so its first and last letters make their own pieces.
- Jaccard score
- Pieces both words share, divided by all different pieces in either word. 1 means the same pieces, 0 means none in common.
- Soundex
- A way to turn a word into a 4-character code so words that sound alike get the same code.
- Sound code
- The Soundex result for a word: its first letter and 3 digits, like O216.
- Prefix
- The first letters of a word. “lig” is a prefix of “lighthouse”.
- Autocomplete
- Suggesting words that start with what you have typed so far.
- Search words
- The words of your question that are kept for searching. Very common words (filler words like “the”) are dropped, and a plural “s” is cut.
- Documents
- The pages of text being searched. A word “matches” a document when the document uses it.