How search measures how similar two words are
Levenshtein distance is the minimum number of character insertions, deletions and substitutions that turns one string into another. It was introduced by the Soviet mathematician Vladimir Levenshtein in a 1965 paper for the journal of the USSR Academy of Sciences. A year earlier Fred Damerau published a paper in Communications of the ACM on automatic spelling correction: in his sample, about 80% of misspellings contained exactly one error — an extra, missing or wrong letter, or two adjacent letters swapped. Hence the Damerau–Levenshtein variant, in which a swap counts as one edit. These metrics underpin fuzzy matching in site search.
| Query | Product | Levenshtein | Damerau–Levenshtein |
|---|---|---|---|
| “sneekers” | “sneakers” | 1 | 1 |
| “smatrphone” | “smartphone” | 2 | 1 |
| “headphnes” | “headphones” | 1 | 1 |
| “iPhone 14” | “iPhone 15” | 1 | 1 — a false match |
Thresholds by word length
The shorter the word, the riskier fuzzy matching becomes, so search engines set the allowance by length:
| Word length | Elasticsearch, AUTO | Algolia, default |
|---|---|---|
| 1–2 characters | exact match | exact match |
| 3 characters | 1 edit | exact match |
| 4–5 characters | 1 edit | 1 typo |
| 6–7 characters | 2 edits | 1 typo |
| 8 or more | 2 edits | 2 typos |
Keyboard layouts, spelling variants and sound-alikes
- Wrong keyboard layout. On German QWERTZ, Y and Z swap, so “yoga mat” arrives as “zoga mat” — one edit, usually recoverable. A layout in another script is a different story: with a Greek layout active, “samsung” becomes “σαμσθνγ”, and only a key-mapping table between layouts helps.
- Spelling variants. “colour” and “color”, “grey” and “gray”, “jewellery” and “jewelry”: a dictionary of US/UK variants is more reliable than hoping the edit-distance threshold lets them through.
- Sound-alike errors. “nite” for “night”, “foto” for “photo”. Phonetic algorithms of the Soundex and Metaphone family handle these for English — one of the classic tasks of NLP.
Where fuzzy matching hurts
On SKUs, model numbers and figures, a single edit changes the product: “RTX 4060” and “RTX 4070”, size 42 and 43. What to do:
- rank exact matches above fuzzy ones;
- switch fuzzy matching off for SKU, model and numeric fields;
- do not correct a query that already has exact results;
- say “Showing results for …” and let the shopper return to the original query.
Semantics as a complement, and a checklist
Vector semantic search is partly resilient to typos: models split words into subword tokens and recognise a word with a small error, especially in a long query. On short queries and SKUs, edit distance is more reliable.
- Pull 50 real misspelled queries from the log and check the results for each.
- Test your top 10 brands with typos, spelling variants and the wrong keyboard layout.
- Check for false matches on model numbers and SKUs.
- Watch the zero-results rate: typos are one of its common causes.