How to Build a Simple Bayesian Spell Checker in Python (21 Lines)

Introduction

When you type a misspelled word, Google instantly suggests the correct spelling; this article shows how to implement a fully functional spell checker in just 21 lines of Python.

Code

import re, collections

def words(text): return re.findall('[a-z]+', text.lower())

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(open('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    deletes = [a + b[1:] for a, b in splits if b]
    transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b) > 1]
    replaces = [a + c + b[1:] for a, b in splits for c in alphabet if b]
    inserts = [a + c + b for a, b in splits for c in alphabet]
    return set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words):
    return set(w for w in words if w in NWORDS)

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

Principle

The algorithm is grounded in Bayes' theorem. For a misspelled word w , we select the candidate c that maximizes P(c|w) ∝ P(w|c)·P(c). P(c) is estimated from word frequencies in a large corpus (the big.txt file). P(w|c) is approximated by the edit distance between c and w , assuming that most spelling errors are within one or two edits.

Code Analysis

words() extracts lowercase alphabetic tokens from the corpus using a regular expression. train() builds a frequency dictionary ( NWORDS) where unseen words default to a count of 1, implemented with collections.defaultdict(lambda: 1). edits1() generates all strings that are one edit away from the input word by performing deletions, transpositions, replacements, and insertions. known_edits2() extends the search to strings two edits away, filtering them through the known‑word dictionary. known() returns the subset of candidate words that actually appear in the corpus. correct() combines these steps: it first checks if the word is already known, then looks at one‑edit candidates, then two‑edit candidates, and finally returns the candidate with the highest corpus frequency.