Spelling Correction
A corrector in fifteen lines.
Peter Norvig, who's a director of research at Google, once wrote a spelling corrector on a plane flight. It's about twenty lines long, and its idea is still wonderful. Generate every possible fix, keep the ones that are real words, then choose the most common.
- Written on a plane flight
- About twenty lines
- Generate, filter, and pick
Generate and filter
First, we count every word in our tickets. That's our dictionary. Edits makes every string that's one change away from a word. All deletions, swaps, substitutions, and additions. That's hundreds of options, nearly all of them nonsense. Correct keeps only the real words, and picks the most common. Run it. Refnd becomes refund. Deliverry becomes delivery. Parcle becomes parcel. And zzz stays as it is, since nothing's close. It's only knowledge of the vocabulary and word counts, with no neural network.
from collections import Counter
from tickets import TICKETS
words = Counter(w for text, _ in TICKETS for w in text.split())
letters = "abcdefghijklmnopqrstuvwxyz"
def edits(word):
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
gone = [a + b[1:] for a, b in splits if b]
swap = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b) > 1]
sub = [a + c + b[1:] for a, b in splits if b for c in letters]
add = [a + c + b for a, b in splits for c in letters]
return set(gone + swap + sub + add)
def correct(word):
if word in words:
return word
options = edits(word) & set(words)
return max(options, key=words.get) if options else word
for typo in ["refnd", "deliverry", "parcle", "bookk", "zzz"]:
print(typo, "->", correct(typo))refnd -> refund deliverry -> delivery parcle -> parcel bookk -> book zzz -> zzz
Also uses tickets.py
TICKETS = [
("my order arrived late and the box was crushed", "delivery"),
("the parcel never came, where is my delivery", "delivery"),
("courier left the package in the rain", "delivery"),
("tracking has not moved for a week", "delivery"),
("shipping took three weeks, far too slow", "delivery"),
("delivery driver was rude and threw the parcel", "delivery"),
("package is lost, nobody knows where it went", "delivery"),
("the courier says delivered but nothing arrived", "delivery"),
("i want my money back for this book", "refund"),
("please refund the second copy you charged me for", "refund"),
("you took payment twice, return my money", "refund"),
("how long does a refund take to reach my card", "refund"),
("cancel my order and give me a refund", "refund"),
("i returned the book but got no money back", "refund"),
("charged the wrong price, want the difference back", "refund"),
("refund has not appeared on my statement", "refund"),
("the book has missing pages in chapter four", "quality"),
("cover is torn and the spine is broken", "quality"),
("pages are printed upside down in the middle", "quality"),
("ink is smudged on every page", "quality"),
("the binding fell apart after one read", "quality"),
("this copy has a coffee stain on the cover", "quality"),
("wrong edition, and the print quality is awful", "quality"),
("several pages are stuck together badly", "quality"),
]
QUERIES = [
("where is my parcel, it has not arrived", "delivery"),
("i need my money back please", "refund"),
("the pages are torn and the cover is bent", "quality"),
("courier lost my package", "delivery"),
("refund the payment to my card", "refund"),
("print is smudged and hard to read", "quality"),
]Making it better
A real corrector does more. It uses context, because their and there are both real words, so only the sentence can tell you which is right. It knows about keyboards, so that r is a likely typo for t. It uses a far larger vocabulary. And names and product codes need protecting, or your corrector will happily break them. Large language models now handle context very well.
Summary
Generate options, filter, and pick the most common. Next, a quick way to match whole titles.
Key takeaways- Generate all one-letter edits
- Keep the real words
- Pick the most common