Fix spelling
- Lesson 12
- 35 min
- Module 4: Understand the query
Where we are
In the last lesson, we normalised and stemmed text, so the forms of a word now match. Normalising does not help when a word is spelt wrong: “outdor” is not a form of “outdoor”. In this lesson, we fix spelling with edit distance and a dictionary built from the catalogue and the query log, and we decide when to correct and when to ask “did you mean”.
Lesson 12 of 30 · Search and Ranking: Find the Best MatchFix spelling
1. The search problem
2. Measure relevance before you change anything
3. Lexical search: the baseline to beat
4. Understand the query
5. Dense and hybrid retrieval
6. Re-rank the top results
7. The parts of search that people see
8. Run search in production
What you will be able to do
Find the product when a person types a word wrong, without breaking the queries that were right. You build the corrector from edit distance and a dictionary, measure it, and choose when to correct and when to ask.
NotebookDo this lesson in a notebook
The notebook builds a dictionary from the catalogue and the query log. It asks you to write the step that finds every string one edit away. Then it corrects the validation queries and counts how many got better and worse. Its setup cells download the practice data, so it needs no local setup. About 35 minutes.
Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.
Before you startWhat to know and to have ready
What you need to know
- Normalising and the run
bm25-norm, from Normalise text. - The synthetic query log, from Meet the catalogue and the query log.
- The kinds of query in the test set (English WANDS, French, planted misspellings), from Build a test set that represents your users.
What you need on your computer (only for the guided practice)
- The project
larkfield-searchwith this module’s files and packages, from the guided practice of Normalise text.python -m pytest -qmust say24 passed.
A shop assistant who reads a bad note
Section titled “A shop assistant who reads a bad note”A customer gives the shop assistant a note: “outdor cushon”. She does not say “we have nothing called that”. She thinks: which words that we sell look almost like these? “outdoor” is one letter away from “outdor”. “cushion” is one letter away from “cushon”. She brings outdoor cushions.
She uses two things. First, she knows the words of her shop. Second, she knows which words are close to the note. A search engine can do the same, if you give it both.
The problem: one wrong letter, no product
Section titled “The problem: one wrong letter, no product”In Larkfield’s synthetic query log, the second most common search with no result is “ligth bulb”: 139 empty pages for one swapped pair of letters. Today’s search needs every word to match, and no product contains “ligth”.
BM25 is kinder: any word may match. But the wrong word still matches nothing. For the query “outdor cushion”, BM25 with normalising finds cushions, because “cushion” matches. The word “outdor” is ignored, so the first results are “bench cushion” and “indoor chair cushion”. The person asked for outdoor cushions and gets indoor ones first.
So a misspelt word is not only a lost word. It is the most important word lost, very often: “outdor” is what makes this query different from every other cushion query.
The idea: the closest word that the shop knows
Section titled “The idea: the closest word that the shop knows”The idea has two parts, as for the shop assistant.
- A dictionary: the words that Larkfield knows, each with a count of how often it appears.
- A distance: how many small changes turn the typed word into a dictionary word.
The distance is called edit distance. One edit is one of four small changes to a word:
- delete a letter: “stoool” → “stool”
- swap two letters next to each other: “ligth” → “light”
- change a letter: “gracity” → “gravity”
- add a letter: “outdor” → “outdoor”
The edit distance between two words is the smallest number of edits that turns one into the other. “outdor” and “outdoor” are at distance 1. “filaret” and “flared” are at distance 2: delete the “i”, then change “t” into “d”. The idea is old and simple. The version with swaps is often called the Damerau-Levenshtein distance, after the two people who described it.
The corrector, step by step
Section titled “The corrector, step by step”The project’s corrector, spell.py, follows the shop assistant:
- Take a word of the query. If it is in the dictionary, it is known: keep it. Words of fewer than 4 letters and numbers are always kept.
- Otherwise, make every string one edit away from it. For “outdor”, there are 338 such strings, most of them not words.
- Keep only the strings that are in the dictionary.
- If none is left and the word has 7 letters or more, try two edits away.
- If several are left, choose the most frequent one in the dictionary.
The diagram follows two real words through these steps. The first one ends well; the second one does not.
Text description of the diagram
Two rows of boxes. Top row: “Unknown word: outdor” leads to “Every string one edit away: delete otdor, swap uotdor, change outdoo, add outdoor; 338 strings”, then to “Keep the strings in the dictionary: outdoor (11,318 times)”, then to a box with a thick border: “Correction: outdoor”. Bottom row: “Unknown word: filaret” leads to “One edit away: no dictionary word”, then to “Two edits away (7+ letters): flared 27, filament 3, floret 1, eilardt 1”, then to a box with a dashed red border: “Most frequent wins: flared. Wrong: the person meant a sofa named Filaret.”
Where the dictionary comes from
Section titled “Where the dictionary comes from”The dictionary decides what the corrector can find. Larkfield’s has 29,312 words. It counts every word in four kinds of product text: the titles, the product classes and categories, the attributes, and the machine-translated French titles. Then it adds the words of every logged search that got a click.
Why only searches with a click? A click says that the search found something that the person wanted, so its words are probably right. A search with no click may contain the same typo that you want to correct. If “ligth” got into the dictionary, the corrector would keep it.
Why not the descriptions? They are long and full of rare words. A rare word in the dictionary can capture a typo. Even so, a word seen very few times can win. The dictionary knows “toro” only twice: from the English and the French title of one faucet. That is enough for the corrector to choose it, as you see below.
Larkfield: measure the corrector
Section titled “Larkfield: measure the corrector”The run bm25-norm+spell corrects the query, then runs bm25-norm. On the test queries, NDCG@10 goes from 0.583 to 0.615 (95% interval 0.568 to 0.657). Each mean is over 241 of the 243 queries. The paired difference is +0.032 (95% interval +0.013 to +0.053): 31 queries better and 11 worse. The chart splits this difference by kind of query.
Text description of the chart
Three rows on an axis of differences, with a line at zero. Misspelt queries (40, a practice problem we made on purpose): +0.232 (95% interval +0.148 to +0.324). English WANDS queries (119): −0.008 (−0.024 to +0.006). French queries (59): −0.008 (−0.021 to 0.000).
The misspelt queries gain +0.232: from 0.416 to 0.648. That is a large and clear gain. But read it with care. Our code made these misspellings with exactly one edit each, a practice problem we made on purpose. The corrector looks for exactly that kind of error. Real typing errors are more varied: two letters wrong, a missing space, a word spelt as it sounds. So +0.232 is probably better than what you would see on real misspellings.
The real English queries do not gain. Their difference is −0.008, and the interval includes 0. To see why, count the changes. On the 364 validation and test queries, the corrector changed 88:
| Kind of query | Changed | Better | Worse | The same |
|---|---|---|---|---|
| Misspelt (planted) | 57 | 36 | 5 | 16 |
| English WANDS (real) | 17 | 3 | 7 | 7 |
| French (machine-translated) | 14 | 1 | 3 | 10 |
| All | 88 | 40 | 15 | 33 |
On the planted misspellings, the corrector is right far more often than wrong. On the real English queries, it changed 17, and made 7 worse and only 3 better. The real queries that it changes are mostly not typos. They are names that the dictionary does not know.
A wrong correction is worse than no correction
Section titled “A wrong correction is worse than no correction”Look at three real WANDS queries that the corrector made worse.
- “filaret outdoor sofa” becomes “flared outdoor sofa”. Filaret is the name of a sofa collection. Now the first result is “samuel 91 ‘’ velvet flared arm sofa”, an indoor sofa. NDCG@10 falls from 0.931 to 0.438.
- “togo chair” becomes “toro chair”. The Togo is a famous chair, but no Larkfield product text has the word. The dictionary knows “toro” twice, from one faucet’s English and French titles. Now the first result is “toro lever wall mounted bathroom faucet”. NDCG@10 falls from 1.000 to 0.641.
- “trinaic towel rod” becomes “trinsic towel rod”. Now Trinsic towel bars take three of the first four places. Nobody judged them for this query, so they count as irrelevant, and NDCG@10 falls from 0.936 to 0.398. But perhaps the person did mean Trinsic. The measure cannot tell, because these products have no judgment.
The first two show the key point. An unknown word does little harm: BM25 finds no product with it, and the other words still work. A wrong correction does real harm. It adds a word that the person never typed, and a rare word gets a high BM25 weight, as you saw in BM25. So the corrector must be more careful than “always choose the closest word”.
French queries show the same problem. The corrector’s dictionary is mostly English. “moto hors route 12v” is a French query for an off-road motorbike. It becomes “moto hors rouge 12v”, because “route” is not in the dictionary and “rouge” (red) is.
Empty pages on the log
Section titled “Empty pages on the log”The corrector has one clear success that NDCG does not show: empty pages. The chart runs each search of the synthetic log through each run and counts the searches with no result.
Text description of the chart
A column chart with five columns: today’s search 30.7%, BM25 7.8%, BM25 with fields and the code rule 6.2%, with normalising 2%, with spelling correction 0.3%.
After normalising, 2.0% of the logged searches still get nothing. With the corrector, only 0.3% do. A search with a wrong correction still shows something, often something close. An empty page shows nothing. In the course’s cost assumptions, 30% of people leave the shop after an empty page.
Correct automatically, or ask?
Section titled “Correct automatically, or ask?”Big search engines rarely just replace your words without telling you. They choose between two behaviours.
- Correct and say so. The page shows the results for the corrected query, with a line such as: “Showing results for outdoor cushion. Search instead for outdor cushion.” The person sees the change and can undo it with one click.
- Ask. The page shows the results for the typed query, with a line: “Did you mean flared outdoor sofa?” Nothing changes unless the person clicks.
Larkfield’s measurements suggest when to use each one.
- Correct and say so when the typed query finds nothing or almost nothing. There, a wrong correction costs little, and an empty page costs a lot.
- Ask when the typed query already finds good products. “filaret outdoor sofa” found outdoor sofas without help; the correction only made it worse.
- Ask when the correction is far: two edits, or a word chosen from very few dictionary counts, such as “toro” (2).
- Protect names. Add the brand and collection names of your catalogue to the dictionary, and names that people search for with success. Then “filaret” would be known and kept.
The project’s run bm25-norm+spell always corrects, without asking. That is simple to measure, and it is the version you measured above. A real search page would add the line “Showing results for…” and the rules above. Those rules need a search page. The project’s page comes in Autocomplete, and Zero results and business rules shows how the page tells the person what the search changed.
Guided practice: correct and measure
Section titled “Guided practice: correct and measure”-
In
larkfield-search, with the virtual environment active, start Python withpython, and try the corrector:>>> from larkfield_search import spell>>> spell.correct_word("outdor")('outdoor', 'corrected')>>> len(spell.edits1("outdor"))338>>> spell.dictionary()["outdoor"]11318>>> spell.correct("filaret outdoor sofa")('flared outdoor sofa', [('filaret', 'flared')])The first call builds the dictionary from the data and saves it in
outputs/. Typeexit()to leave Python. -
Search for “outdor cushion” without the corrector:
Terminal window search query "outdor cushion" --run bm25-norm -k 3bm25-norm: "outdor cushion" -> 3 results1. LK-54193 bench cushion Furniture Cushions 29.992. LK-62284 indoor chair cushion Furniture Cushions 20.993. LK-26958 deep outdoor seat cushion Furniture Cushions 64.99 -
Now with the corrector:
Terminal window search query "outdor cushion" --run bm25-norm+spell -k 3bm25-norm+spell: "outdor cushion" -> 3 results1. LK-90733 outdoor adirondack chair cushion Furniture Cushions 11.992. LK-22523 rossmere indoor/outdoor bench cushion Furniture Cushions 13.99 [out of stock]3. LK-17722 texture outdoor bench cushion Furniture Cushions 12.99This query is not in the query set, so no result is marked. You judge by eye: every result is now an outdoor cushion.
-
Measure the corrector by kind of query:
Terminal window search compare bm25-norm bm25-norm+spell --by sourcebm25-norm+spell minus bm25-norm on 241 test queries: ndcg@10 +0.032 (95% interval +0.013 to +0.053); better on 31, worse on 11, the same on 199source queries bm25-norm bm25-norm+spell difference low high worsecode 20 1.000 1.000 0.000 0.000 0.000 0planted 3 0.384 0.384 0.000 0.000 0.000 0translated 59 0.309 0.301 -0.008 -0.021 0.000 2typo 40 0.416 0.648 0.232 0.148 0.324 3wands 119 0.709 0.701 -0.008 -0.024 0.006 6 -
Look at the query that got worst on the test split:
Terminal window search query "filaret outdoor sofa" --run bm25-norm+spell -k 3bm25-norm+spell: "filaret outdoor sofa" -> 3 results (query W-090: judged results are marked)1. LK-88873 samuel 91 '' velvet flared arm sofa Sofas 80.99 [not judged]2. LK-12354 catalina outdoor sofa with cushions Patio Sofas 1047.99 [partial]3. LK-15552 griswold 92 '' flared arm sofa bed Sofas 434.99 [not judged]
In step 4, read the worse column again. The corrector made 3 misspelt queries worse, 6 real English queries and 2 French queries. Then open each of them with search query, as in step 5. A list of the worse queries is the best guide to the next rule that you write.
Your turn: does it hold on validation?
Section titled “Your turn: does it hold on validation?”Change one thing: the split. Run the same comparison on the 121 validation queries. Before you run it, predict: will the misspelt queries gain as much as on the test split?
search compare bm25-norm bm25-norm+spell --split validation --by sourceThe output, and what it shows
bm25-norm+spell minus bm25-norm on 121 validation queries: ndcg@10 +0.024 (95% interval +0.004 to +0.047); better on 9, worse on 4, the same on 108
source queries bm25-norm bm25-norm+spell difference low high worse code 10 1.000 1.000 0.000 0.000 0.000 0 planted 1 0.685 0.685 0.000 0.000 0.000 0translated 30 0.245 0.241 -0.004 -0.012 0.000 1 typo 20 0.594 0.745 0.151 0.041 0.292 2 wands 60 0.695 0.694 -0.001 -0.002 0.000 1The misspelt queries gain +0.151 here, against +0.232 on test. The direction is the same, and both intervals are above 0. But with only 20 misspelt queries, the interval is wide: +0.041 to +0.292. The real English queries again do not gain. The pattern holds; the exact size does not. This is why you quote an interval, not one number.
Common mistake
A brand that the shop does not sell
Symptom: a person types “ikea bookcase”. Larkfield does not sell IKEA products. With the corrector, the third result is a dining table:
bm25-norm+spell: "ikea bookcase" -> 3 results 1. LK-77220 capel etagere bookcase Bookcases 46.99 2. LK-40051 gladbrook entagere bookcase 65.99 3. LK-17638 ikra dining table Dining Tables 625.99This query is one we wrote to show the problem; it is not in the query set.
Cause: “ikea” is not in the dictionary, so the corrector changes it into the closest known word: “ikra”, the name of a dining table. The rare word “ikra” gets a high BM25 weight, so the table comes up.
Fix: keep a list of words that the corrector must never change: brands that people search for, including brands that you do not sell. Or ask “did you mean ikra?” instead of correcting, because “ikra” has a very small count in the dictionary.
Consequence in search work: a corrector knows only its dictionary. Every word outside it looks like a typo. Read the words that the corrector changes most often in your log, and protect the ones that are not typos.
When to use a corrector, and what it costs
Section titled “When to use a corrector, and what it costs”Use one when your log has many misspelt searches and many empty pages. Larkfield’s synthetic log has both: 6% of its searches are misspelt by design, and the corrector takes empty pages from 2.0% to 0.3%.
Be careful when your queries are full of names: brands, collections, models. A corrector built from the catalogue does not know every name that people type, and it turns unknown names into wrong words. On Larkfield’s real English queries, it made more queries worse than better.
The cost at query time is tiny. In the project’s timing of one search, spelling takes 0.01 ms (p50, one thread), against 1.15 ms for the lexical search itself. The dictionary is built once from the data, in less than 2 seconds here. The real cost is your attention: every rule of the corrector changes some queries for the worse, and you must read them.
Knowledge check
Section titled “Knowledge check”Check your understanding
Compute the edit distance between “stol” and “stool”, and between “cabiet” and “cabinet”. Name the edit each time.
Show the answer
Both are 1. “stol” → “stool”: add one “o”. “cabiet” → “cabinet”: add one “n”. The corrector finds both in its first round, because it tries every string one edit away.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
The corrector raised the misspelt test queries by +0.232 but changed the real English queries by −0.008. Give two reasons why the +0.232 may be too optimistic.
Show the answer
First, our code made each planted misspelling with exactly one edit, and the corrector looks for exactly one or two edits. Real typing errors are more varied. Second, there are only 40 misspelt test queries, so the interval is wide (+0.148 to +0.324). The real English queries show the other side: the corrector mostly changes names there, and it made 7 of the 17 changed queries worse.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Check your understanding
“filaret outdoor sofa” already finds outdoor sofas without correction. Should Larkfield's page correct it automatically or ask “did you mean”? Explain with the measurement.
Show the answer
Ask, or do nothing. The typed query already has good results (NDCG@10 0.931), and the correction to “flared” drops it to 0.438. A correction only pays when the typed query finds little. Here it adds a word that the person never typed. The best fix is to add “filaret” to the dictionary, so it is known.
Does your answer have the main points of ours?
Sign in and enroll in the course to save your answers. Every check counts toward the certificate.
Recap
- Edit distance counts the small changes (delete, swap, change, add) between two words. The corrector tries every string one edit away, keeps those in the dictionary, and takes the most frequent.
- Larkfield’s dictionary (29,312 words) comes from the product titles, classes, categories, attributes, the French titles, and the logged searches that got a click.
- On Larkfield’s test queries,
bm25-norm+spellreaches NDCG@10 0.615 (0.568 to 0.657): +0.232 on the planted misspellings, −0.008 on the real English queries. Empty pages on the synthetic log fall from 2.0% to 0.3%. - A wrong correction is worse than no correction: “filaret” → “flared” (0.931 → 0.438), “togo” → “toro”. Correct and say so when the typed query finds little; ask when it already finds good products or the correction is far.
You can now catch typing errors. But some queries are spelt right and still miss, because the person uses another word for the same thing: “couch” for “sofa”. Next, you add synonym rules, try a language model that rewrites queries, and test every rule.