Start with a word set that answers "known or unknown" and end with a runnable checker that reads a paragraph and prints each misspelling with its line, column, and ranked "did you mean" suggestions. Every lesson is one concrete spec: edit distance, deletes/transposes/replaces/inserts, a frequency model, and a metric tree that prunes the search so you never scan the whole dictionary.
Over 40 lessons you build a working spell checker from scratch: a case-insensitive dictionary you can query and load from a word list, a tokenizer that splits text into words and remembers where each one sits, Levenshtein edit distance (plus adjacent transposition) as the measure of how far a typo is from a real word, Norvig-style candidate generation that turns a misspelling into the real words one or two edits away, a frequency model that ranks those candidates so the likeliest correction wins, and a BK-tree index whose triangle-inequality pruning finds nearby words without scanning the whole dictionary.
By the end you have a runnable tool: give it a paragraph and it flags every word not in the dictionary, reports each one by line and column, and prints ranked "did you mean" suggestions, with a personal ignore list for words you want it to accept. The capstone runs the finished checker over a real multi-line paragraph of prose and produces a full report.
This is a teaching-grade checker built around the real Norvig-plus-BK-tree design: it corrects one word at a time by edit distance and word frequency, and it is honest about what it does not do - it has no sense of context or grammar, so it cannot fix a correctly-spelled wrong word ("their" for "there"), and it works on English-like ASCII words rather than full Unicode. What you finish with is the honest core that production spell checkers extend with context models and richer language data.
Every spell checker starts with one question - is this word real? Today you build the smallest possible dictionary, one that knows no words yet, so the public surface exists from day one and every later lesson thickens it.
Create an empty dictionary whose membership check reports that any word is unknown.
A spell checker is, at heart, a thing that answers one question over and over: is this a real word? Everything else - measuring typos, suggesting fixes - hangs off that single membership test. So before any of the clever machinery matters, the shape of that surface has to exist: something you can construct and ask about a word. Today it knows nothing, so every word is unknown.
Starting from an empty dictionary that always answers false may feel trivial,
but it pins the contract the rest of the project leans on. Contains takes a word
and returns a plain yes or no. Keep it that simple - the storage, the
case-folding, the loading all arrive one lesson at a time on top of this.
// the whole checker will grow around this typetype Dictionary struct { /* word storage comes next lesson */ }func New() *Dictionary { return &Dictionary{} }// "known" vs "unknown" is the one question a spell checker answersfunc (d *Dictionary) Contains(word string) bool {return false}
A genuinely working single-word spell checker - case-insensitive dictionary, edit-distance candidate generation, frequency ranking, and a BK-tree index behind a runnable CLI that reports misspellings with line, column, and ranked suggestions - but it corrects each word in isolation, with no sense of context or grammar, and generates candidates over the ASCII letters a-z only.
The 21-line spelling corrector this project is built around - candidate generation by edits, a word-frequency model, and the candidate ladder. Read it first.
The minimum-edit-distance and spelling-correction chapters derive the exact Levenshtein DP and the noisy-channel ranking model used here, with the linguistics behind them.
The 1973 paper that introduced the BK-tree: a metric tree that uses the triangle inequality of a distance function to search by radius - the index in chapter five.
A clear, worked walkthrough of building and querying a BK-tree over a dictionary - the practical companion to the original paper.
A faster alternative index built on a precomputed deletion dictionary - the natural next structure to try after the BK-tree, and a good second-pass project.
The original definition of edit distance as insertions, deletions, and substitutions - the correctness core every candidate in this project is measured against.