Skip to content
Français

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”.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

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 notebookColab · Kaggle · GitHub

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 readyAbout 35 minutes

What you need to know

What you need on your computer (only for the guided practice)

  • The project larkfield-search with this module’s files and packages, from the guided practice of Normalise text. python -m pytest -q must say 24 passed.

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.

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.

  1. A dictionary: the words that Larkfield knows, each with a count of how often it appears.
  2. 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 project’s corrector, spell.py, follows the shop assistant:

  1. 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.
  2. Otherwise, make every string one edit away from it. For “outdor”, there are 338 such strings, most of them not words.
  3. Keep only the strings that are in the dictionary.
  4. If none is left and the word has 7 letters or more, try two edits away.
  5. 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.

Two words through the corrector. outdor: every string one edit away (delete otdor, swap uotdor, change outdoo, add outdoor), 338 strings; only outdoor is in the dictionary, 11,318 times; the correction is outdoor. filaret: no dictionary word one edit away; two edits away there are flared 27 times, filament 3, floret 1, eilardt 1; the most frequent wins: flared, which is wrong, because the person meant a sofa named Filaret.
The corrector on two real words. The rule “most frequent wins” is right for “outdor” and wrong for “filaret”.
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.”

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.

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.

What the corrector changes on Larkfield's test queries, by kind of query, with the paired 95% interval. It helps the misspellings that we planted, and it slightly hurts the real English queries and the French queries.
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.

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.

The share of the 20,000 searches of Larkfield's synthetic log that get no result, per run: today's search, BM25, BM25 with fields and the code rule (Codes), with normalising (Norm) and with spelling correction (Spell). Spelling correction takes it from 2.0% to 0.3%.
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.

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.

  1. 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.
  2. Ask when the typed query already finds good products. “filaret outdoor sofa” found outdoor sofas without help; the correction only made it worse.
  3. Ask when the correction is far: two edits, or a word chosen from very few dictionary counts, such as “toro” (2).
  4. 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.

  1. In larkfield-search, with the virtual environment active, start Python with python, 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/. Type exit() to leave Python.

  2. Search for “outdor cushion” without the corrector:

    Terminal window
    search query "outdor cushion" --run bm25-norm -k 3
    bm25-norm: "outdor cushion" -> 3 results
    1. LK-54193 bench cushion Furniture Cushions 29.99
    2. LK-62284 indoor chair cushion Furniture Cushions 20.99
    3. LK-26958 deep outdoor seat cushion Furniture Cushions 64.99
  3. Now with the corrector:

    Terminal window
    search query "outdor cushion" --run bm25-norm+spell -k 3
    bm25-norm+spell: "outdor cushion" -> 3 results
    1. LK-90733 outdoor adirondack chair cushion Furniture Cushions 11.99
    2. LK-22523 rossmere indoor/outdoor bench cushion Furniture Cushions 13.99 [out of stock]
    3. LK-17722 texture outdoor bench cushion Furniture Cushions 12.99

    This query is not in the query set, so no result is marked. You judge by eye: every result is now an outdoor cushion.

  4. Measure the corrector by kind of query:

    Terminal window
    search compare bm25-norm bm25-norm+spell --by source
    bm25-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 199
    source queries bm25-norm bm25-norm+spell difference low high worse
    code 20 1.000 1.000 0.000 0.000 0.000 0
    planted 3 0.384 0.384 0.000 0.000 0.000 0
    translated 59 0.309 0.301 -0.008 -0.021 0.000 2
    typo 40 0.416 0.648 0.232 0.148 0.324 3
    wands 119 0.709 0.701 -0.008 -0.024 0.006 6
  5. Look at the query that got worst on the test split:

    Terminal window
    search query "filaret outdoor sofa" --run bm25-norm+spell -k 3
    bm25-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.

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?

Terminal window
search compare bm25-norm bm25-norm+spell --split validation --by source
The 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 0
translated 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 1

The 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.99

This 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.

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.

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.

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.

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+spell reaches 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.

Next: Synonyms and query rewriting