Learn AI Create the Future — with Pranay
Main site

Messy Real-World Text

Building a spell checker

A spell checker guesses the intended word from a misspelled one by finding the closest real word, the same way you guess a word mumbled in a noisy market.

Read these first

On this page 5
  1. Why it exists
  2. How it works
  3. Where you have already seen it
  4. Remember this
  5. What to learn next

One lesson, three depths. Pick the one that fits you today — you can switch any time.

Beginner — No maths. Plain English.

A spell checker guesses which real word you meant, by finding the closest match to what you actually typed.

Think about a noisy vegetable market. A vendor shouts a price you half hear over the crowd. You did not catch every sound with certainty. You still guess the number correctly, because only one nearby number makes sense.

Spell checking works the same way. "langauge" is not a word. "language" is one letter-swap away, and nothing else close by makes sense either. Your brain — and a spell checker — fill the gap with the nearest real match.

Why it exists

People mistype. Fingers slip, letters swap, autocomplete guesses wrong. Search boxes, chat apps and forms all receive a steady stream of near-misses instead of exact words.

A system that only accepts exact matches fails constantly against ordinary human typing. Spell checking exists to bridge that gap — accept the messy input, find the real word it was reaching for.

How it works

  typed: "wrod"
              |
              v
     compare against every word in a dictionary
              |
              v
    "word" is one edit away (swap two letters)  <-- closest match, pick this one

An edit is one small change. Delete a letter, insert one, swap two neighbours, or replace one. Counting how many edits separate two words tells you how close they are.

Where you have already seen it

  • Search engines showing "Did you mean: language" under a mistyped query.
  • Phone keyboards silently correcting "teh" to "the" as you type.
  • Word processors underlining "recieve" in red, and suggesting "receive."

Remember this

  • A spell checker finds the closest real word to a misspelled one, usually by counting small edits between them.
  • "Closest" is measured by edits — deletions, insertions, swaps, replacements — not by how the words sound.
  • The dictionary used matters as much as the algorithm — a word missing from the dictionary can never be suggested.

What to learn next

Developer — Code and libraries.

This builds a real, working spell checker from nothing but a small word list — the classic technique, reduced to its essentials.

Setup

Nothing to install. Pure Python standard library only.

A spell checker in under 30 lines

tiny_spellcheck.py
from collections import Counter

# A tiny frequency dictionary. A real one has hundreds of thousands of words.
WORDS = Counter({
    "the": 500, "quick": 20, "brown": 15, "fox": 18, "jumps": 10,
    "over": 80, "lazy": 12, "dog": 40, "model": 60, "learn": 55,
    "learns": 30, "learning": 45, "language": 50, "word": 35,
    "words": 25, "spell": 15, "spelling": 20, "correct": 22,
    "correction": 18, "python": 40,
})

def edits1(word):
    letters = "abcdefghijklmnopqrstuvwxyz"
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    deletes = [l + r[1:] for l, r in splits if r]
    transposes = [l + r[1] + r[0] + r[2:] for l, r in splits if len(r) > 1]
    replaces = [l + c + r[1:] for l, r in splits if r for c in letters]
    inserts = [l + c + r for l, r in splits for c in letters]
    return set(deletes + transposes + replaces + inserts)

def known(words):
    return {w for w in words if w in WORDS}

def correct(word):
    if word in WORDS:
        return word
    candidates = known(edits1(word)) or known(e2 for e1 in edits1(word) for e2 in edits1(e1)) or {word}
    return max(candidates, key=WORDS.get)

for typo in ["langauge", "wrod", "speling", "pythom", "corect"]:
    print(f"{typo!r:14} -> {correct(typo)!r}")
Output
'langauge'     -> 'language'
'wrod'         -> 'word'
'speling'      -> 'spelling'
'pythom'       -> 'python'
'corect'       -> 'correct'

Line by line

edits1 generates every word reachable by one edit — one deletion, one adjacent-letter swap, one substitution, or one insertion — from the typo. For a five-letter word this generates roughly 200 candidates, most of them nonsense.

known filters those candidates down to real dictionary words. Most of the 200-odd generated strings are not real words at all — known throws them away, keeping only the handful that exist in WORDS.

When one edit finds nothing, correct tries two edits — every one-edit neighbour of every one-edit neighbour. This catches typos like "speling," which needs two changes (missing the second "l," in this case really needing an insertion) to reach "spelling."

max(candidates, key=WORDS.get) picks the most frequent surviving candidate. If a typo is genuinely ambiguous between two real words, the more common one wins — a reasonable default when no other context is available.

Common mistakes

Using a dictionary too small for real text. This toy dictionary has twenty words. A real spell checker needs hundreds of thousands, or it will "correct" real unfamiliar words — technical terms, names — into something wrong, only because the right word was never in the dictionary.

Ignoring word frequency entirely. Without WORDS.get weighting the choice, a rare candidate could beat a far more likely one. Frequency is a cheap, effective tiebreaker.

Assuming two edits catches everything. A badly mangled typo — three or more edits away from the intended word — will not be found by this method at all, and correct silently returns the original typo unchanged.

Try it yourself

Add a typo that needs three edits to fix, and watch correct fail — it returns the typo unchanged, since the search only goes two edits deep. Extend the e2 loop to a third level and see the runtime cost: each additional edit level multiplies the candidate count by roughly the same factor again.

What to learn next

Researcher — Mathematics and papers.

Formalising edit distance

The Levenshtein distance between strings s and t is the minimum number of single-character insertions, deletions and substitutions needed to transform s into t:

text
lev(i, j) = min(
    lev(i-1, j)   + 1,                          -- deletion
    lev(i, j-1)   + 1,                          -- insertion
    lev(i-1, j-1) + cost(s_i, t_j)              -- substitution (cost 0 if s_i == t_j)
)
  • i, j index into s and t; lev(0, j) = j and lev(i, 0) = i as base cases.
  • cost(s_i, t_j) is 0 if the characters match, 1 otherwise.

This is computed by dynamic programming in O(|s| * |t|) time and space, filling an (|s|+1) x (|t|+1) table bottom-up. The developer demo above uses a different, historically earlier formulation — Damerau-Levenshtein distance restricted to distance 1 or 2 — which additionally treats adjacent transposition as a single edit, matching a common real typing error (swapped keystrokes) that plain Levenshtein charges two edits for.

Noisy channel framing

Norvig's formulation (2007), implemented directly in the developer demo above, treats spelling correction as Bayesian inference:

text
correct(w) = argmax over c in candidates of  P(c) * P(w | c)
  • P(c) is the prior probability of the intended word c, estimated from word frequency in a large corpus.
  • P(w | c) is the error-model likelihood: how probable is it that someone typing c would produce the observed typo w.
  • argmax selects the candidate maximising this product.

The demo above approximates P(w | c) crudely, treating every edit-distance-1 candidate as equally likely and using frequency alone to break ties — real systems learn P(w | c) from actual observed typo data, since some substitutions (adjacent keys on a QWERTY layout) are far more likely than others.

Beyond edit distance

Phonetic algorithms — Soundex (Russell, early 1900s), Metaphone (Philips, 1990), Double Metaphone (Philips, 2000) — match words by approximate pronunciation rather than spelling distance, catching errors like "fisiks" for "physics" that are phonetically close but several edits apart under Levenshtein distance.

Context-sensitive correction. "Their" and "there" are each other's most common typo, at edit distance 2, yet the correct choice depends entirely on surrounding grammar, not on either word's dictionary frequency. Modern spell checkers increasingly use a language model to score candidates in context, rather than scoring each misspelled word in isolation.

Neural spelling correction. Character-level sequence-to-sequence models, trained on large corpora of real (typo, correction) pairs, learn the error model directly from data rather than hand-coding edit operations, and handle multi-error typos that classical edit-distance search misses entirely.

Key references

  • Levenshtein, V. (1966). Binary Codes Capable of Correcting Deletions, Insertions, and Reversals. Soviet Physics Doklady 10(8).
  • Damerau, F. (1964). A Technique for Computer Detection and Correction of Spelling Errors. Communications of the ACM.
  • Norvig, P. (2007). How to Write a Spelling Corrector. norvig.com/spell-correct.html — the direct basis for the developer demo above.
  • Kernighan, M., Church, K. & Gale, W. (1990). A Spelling Correction Program Based on a Noisy Channel Model. COLING. — the original statistical noisy-channel formulation.

Current state and open problems

Edit-distance and noisy-channel methods remain fast, transparent and effective for single-word, single-error typos, and are still widely deployed for exactly that case, since they need no training data beyond a word-frequency list.

Context-dependent errors — real-word errors like "their" for "there," where the typo is itself a valid dictionary word — are structurally invisible to any method that scores words in isolation, since correct(word) never even triggers when the word already exists in the dictionary. This class of error requires a language model over surrounding context, moving the problem from lexical distance into the same territory as grammar and meaning.

What to learn next