Skip to content
Tutorials Center
My learning

Topics

Lesson 21 of 63 ยท Language Models Before Neural Nets

Spelling Correction

Build a spelling corrector from scratch: Levenshtein edit distance, candidate generation and the noisy-channel model that ranks fixes by likelihood.

Type "recieve" into a search box and it quietly shows results for "receive". Behind that small convenience is a classic NLP pipeline: decide that a word is probably wrong, generate plausible corrections, and pick the best one. None of it needs a neural network. It needs a way to measure how different two strings are, a list of real words, and the counting habits you learned in the n-gram language model lesson.

This lesson builds the three parts from scratch: the edit distance between two strings, a generator of candidate corrections, and the noisy-channel model that ranks candidates. At the end you will have a working corrector in about 40 lines of Python.

Two kinds of spelling errors

Spelling mistakes come in two flavors, and they need different tools.

  • Non-word errors produce a string that is not in the dictionary: "wether", "recieve". Detecting these is easy (look the word up), and the task is choosing the right replacement.
  • Real-word errors produce another valid word: "I want to go there house" or "a piece of cake / cack". A dictionary cannot flag these. You need context, which is where a language model comes in.

This lesson focuses on non-word errors, which is how most simple spell checkers work, and ends with how context extends the idea.

The correction pipeline

Detect Is the word missing from the vocabulary?
Generate List words a few edits away.
Rank Likely words and likely typos win.

Each step can be improved on its own.

1 / 2

Edit distance

The Levenshtein distance between two strings is the smallest number of single-character insertions, deletions and substitutions that turn one into the other. "kitten" to "sitting" takes three: change k to s, change e to i, add g.

Computing it uses dynamic programming. Fill a table d where d[i][j] is the distance between the first i characters of a and the first j characters of b. The first row and column are easy: turning an empty string into j characters needs j insertions. Every other cell takes the cheapest of three moves: delete a character (look up), insert one (look left), or substitute (look diagonally, paying 1 if the characters differ and 0 if they match).

Python Edit distance with its table

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The bottom-right cell holds the answer, 3. Each cell is the cheapest way to get there, so the table also encodes the path of edits if you trace it back. Two details stand out in the pairs. color to colour is a single insertion, as you would expect. But recieve to receive has distance 2: swapping two neighbouring letters needs a deletion plus an insertion under plain Levenshtein, yet it is the single most common kind of typo. The Damerau-Levenshtein variant counts a swap of adjacent characters as one edit, and the candidate generator below does the same.

Plain edit distance treats all edits as equal. Real spelling errors are not: people hit a neighbouring key much more often than a distant one, and some letters are confused by sound. Weighted edit distance gives each edit its own cost, learned from data.

Generating candidates

Comparing a misspelled word with every dictionary word is slow for large vocabularies. A faster approach is to generate every string within one edit of the typo and keep only those that are real words. For a word of length n over 26 letters, the number of strings at distance one is about 54n + 25: n deletions, n - 1 transpositions, 26n substitutions and 26(n + 1) insertions, minus duplicates.

Python All strings one edit away

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Most of these strings are gibberish ("aat", "bcat"). That is fine: intersecting with the vocabulary throws them away. The growth is the real lesson. Within one edit a seven-letter word has 390 neighbours; within two edits it has more than 70,000. Production spell checkers therefore search one edit first and go to two only if nothing was found, and large systems use indexing structures such as tries or symmetric-delete tables instead of generating strings.

The noisy-channel model

Several candidates may be one edit away. Which is best? The noisy-channel model imagines that the writer meant a word w, but the typing process (the noisy channel) corrupted it into what we see, x. We want the intended word with the highest probability given what we saw. By Bayes' rule this becomes:

TEXT
best word = argmax over w of  P(x | w) * P(w)
  • P(w) is the language model: how likely is this word in ordinary text? "the" beats "thy" simply because it is far more common.
  • P(x | w) is the channel (error) model: how likely is this typo if the writer meant w? One-edit mistakes are much more likely than two-edit ones.
flowchart LR
    A["Intended word w"] -->|"noisy typing<br/>P(x | w)"| B["Typed word x"]
    B --> C["Corrector tries every w<br/>and picks max P(x | w) x P(w)"]

We never observe the intended word; we score every candidate and pick the best.

A real error model is trained from logs of typos and corrections. A simple stand-in is to assume each edit costs a fixed small probability, so P(x | w) = 0.01 ^ distance. The prior P(w) comes from counting words in a corpus. The program below ties everything together: it searches distance 0, then 1, then 2, scores candidates, and prints the ranking for two examples.

Python A complete spelling corrector

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Six typos are repaired as you would hope, paper is left alone because it is already a word, and xyzzy is returned unchanged because no known word is within two edits. The two detailed rankings show the noisy channel at work. For wrte, write and wrote are both one edit away, and write wins because it appears three times in the corpus against one for wrote; the prior breaks the tie. If a rarer word were two edits away, a common word one edit away would usually beat it, because each edit multiplies the score by 0.01.

The corrector is only as good as its vocabulary and its counts. With a corpus of 97 words it knows almost nothing; a real one trains on millions of words. It also treats every word in isolation, so it cannot fix real-word errors.

Using context

The prior P(w) does not have to be a unigram count. For the typed phrase "I went to the wether today" you can instead score each candidate by how well it fits its neighbours with a bigram model: P(weather | the) * P(today | weather). That is the same noisy-channel formula with a stronger language model, and it is how real-word errors are caught: every word, even a valid one, is replaced by its neighbours in the edit-distance set, and the sentence with the highest language-model score wins.

Modern spell checkers use neural models trained on large collections of typos and corrections, but they keep the same overall shape: propose candidates, score by likelihood. The simple version you just built is also a handy fuzzy matcher for names, product search and cleaning dirty text.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the Levenshtein distance between "cat" and "cut"?

    One substitution (a becomes u) turns "cat" into "cut", so the distance is 1.
  2. 2. Why does plain Levenshtein distance score a swap of two adjacent letters ("recieve" and "receive") as 2?

    Without a transposition operation, swapping two letters needs a substitution at each position (or a deletion plus an insertion), which costs 2. Damerau-Levenshtein adds transposition as a single edit.
  3. 3. In the noisy-channel model, what does P(w) represent?

    P(w) is the language model prior, meaning how common the candidate is. P(x | w) is the error model. The product ranks candidates by how likely they are overall.
  4. 4. Why do spell checkers usually try words within one edit before two edits?

    A seven-letter word has a few hundred strings at distance 1 but tens of thousands at distance 2. Most real typos are a single edit, so checking distance 1 first is both fast and usually enough.
  5. 5. Which kind of error can a dictionary lookup alone NOT detect?

    A real-word error produces a valid word, so the dictionary accepts it. Only context, such as a language model of neighbouring words, can reveal that it does not fit.

Summary

  • Spelling correction detects a bad word, generates nearby candidates and ranks them.
  • Levenshtein distance counts insertions, deletions and substitutions and is computed with a dynamic-programming table; Damerau-Levenshtein also counts adjacent swaps.
  • Candidates come from all strings one edit away (a few hundred per word), then two edits only if needed; the results are intersected with a vocabulary.
  • The noisy-channel model picks the word that maximizes P(x | w) * P(w): an error model times a language model.
  • Real-word errors need context, so stronger language models (bigrams and beyond) improve the prior.

Next, move from fixing text to pulling facts out of it with Rule-Based Information Extraction.