--- title: "A Spelling Correction Program Based on a Noisy Channel Model" description: "The authors present correct , a post-processor for words flagged by the Unix spell program. 6 references, cited by 66 papers here." authors: ["Mark D. Kernighan", "Kenneth W. Church", "William A. Gale"] year: 1990 venue: "COLING 1990 Volume 2: Papers presented to the 13th International Conference on Computational Linguistics" source: "https://aclanthology.org/C90-2036/" licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/" summary_licence: "Elamur Cosmic License" canonical: "https://research.elamur.ai/free/en/papers/kernighan-1990-spelling-correction-program-based-noisy/" --- [Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/kernighan-1990-spelling-correction-program-based-noisy/) [home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [1990](https://md.research.elamur.ai/free/en/papers/1990/) / A Spelling Correction Program Based on a Noisy Channel Model # A Spelling Correction Program Based on a Noisy Channel Model **Authors:** Mark D. Kernighan, [Kenneth W. Church](https://md.research.elamur.ai/free/en/authors/kenneth-w-church/) and [William A. Gale](https://md.research.elamur.ai/free/en/authors/william-a-gale/) · **Year:** 1990 · **Venue:** [COLING 1990 Volume 2: Papers presented to the 13th International Conference on Computational Linguistics](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 1990](https://md.research.elamur.ai/free/en/venues/coling/1990/)) · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/) **Links:** [Publisher's page](https://aclanthology.org/C90-2036/) · [PDF](https://aclanthology.org/C90-2036.pdf) · [OpenAlex](https://openalex.org/W1972099155) **Citations:** 262 citations (OpenAlex, 2026-10-14) · [66](https://md.research.elamur.ai/free/en/papers/kernighan-1990-spelling-correction-program-based-noisy/cited-by/) in our library, of the 141,840 papers whose bibliographies we read ## Summary The paper addresses how to rank possible fixes for misspelled words, rather than simply listing them. The authors present *correct*, a post-processor for words flagged by the Unix spell program. For each rejected string it first gathers dictionary words that are one edit away: an insertion, deletion, substitution, or reversal of adjacent letters. It then ranks these candidates with a noisy channel model borrowed from speech recognition. A candidate c is scored by the product of its prior word probability Pr(c) and the probability Pr(t|c) that typing c would produce the observed typo t. Scores are normalized across candidates. Both components were trained on the Associated Press (AP) newswire, which contains plenty of real typing errors. The channel model uses per-character confusion counts, which are learned iteratively starting from a uniform guess. In a judged evaluation of typos with two candidates, the top choice matched the majority of three human judges in 87% of cases. Removing either model component made results clearly worse. The work matters because it showed early on that simple probabilistic modeling produces useful and well-calibrated spelling suggestions. ## Key points - Candidates are restricted to dictionary words within a single insertion, deletion, substitution, or adjacent-letter reversal of the typo. The word list was compiled from spell, the AP newswire, and machine-readable dictionaries. - The prior is estimated as (freq(c) + 0.5)/N, where counts are taken from AP newswire text for 1988, totaling N = 44 million words. The authors call this an expected likelihood estimate. - The channel probabilities come from four confusion matrices (del, add, sub, rev), each normalized by character or character-pair counts. The matrices are built by bootstrapping from a uniform start and smoothed with Good-Turing. - The system was trained on AP wire from 2/88 to 2/89 and tested on 3/89 to 9/89. The test data showed roughly 2,000 typos per month, and most had only a few candidates. - Three judges labeled 564 two-candidate triples, and 329 cases with clear agreement were kept. Results were: - **correct:** 87% (286/329) - **no-prior:** 80% - **no-channel:** 75% - **neither (first candidate):** 52% - **judges against each other:** 96–99% ## Interesting ideas - **Bootstrapping the error model from unlabeled data:** the model starts with uniform confusion probabilities, corrects a raw corpus, recounts the errors, and repeats. This avoids hand-labeling typo/correction pairs and could transfer to OCR noise or to languages with little annotated data, such as Ukrainian. - **Ablation against weak baselines:** the full model is compared with versions that drop the prior, drop the channel, or drop both. This cheaply shows how much each component contributes and is a good template for evaluating any combined scoring function. - **Checking calibration, not just accuracy:** predictions are grouped by score (20 typos per group), and the average score is compared with the actual hit rate, with sampling-error bands. This reveals whether the probabilities can be trusted, for example when deciding whether to auto-correct a word or only suggest a fix. - **Filtering the evaluation set:** only items where two judges agreed on one of the two candidates are kept. This isolates the ranking component from upstream problems, such as spell flagging valid words, which accounted for about 20% of judge responses. - **Context as the next step:** the judges struggled without surrounding text, which suggests adding context to the prior, for example with trigram language models. Isolated-word correctors in any language would likely gain from the same change. *Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.* ## Institutions - [AT&T](https://md.research.elamur.ai/free/en/companies/at-t/) — Company, Bedminster, United States · 29 works · 15,393 citations 📚 Shelves (4): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works 🧭 Topics (1): [🖍️ Grammatical error correction & learner language](https://md.research.elamur.ai/free/en/topics/grammatical-error-correction/) · 80 works ## Cite Cite as: Mark D. Kernighan, Kenneth W. Church and William A. Gale. 1990. A Spelling Correction Program Based on a Noisy Channel Model. COLING 1990 Volume 2: Papers presented to the 13th International Conference on Computational Linguistics. The paper itself, not this page. BibTeX from the library's record of the work. ```bibtex @inproceedings{kernighan1990spelling, title = {{A Spelling Correction Program Based on a Noisy Channel Model}}, author = {Mark D. Kernighan, Kenneth W. Church and William A. Gale}, booktitle = {COLING 1990 Volume 2: Papers presented to the 13th International Conference on Computational Linguistics}, year = {1990}, doi = {10.3115/997939.997975}, url = {https://doi.org/10.3115/997939.997975} } ``` - [← previous Synchronous Tree-Adjoining Grammars](https://md.research.elamur.ai/free/en/papers/shieber-1990-synchronous-tree-adjoining-grammars/) - [next → Constraint Grammar as a Framework for Parsing Running Text](https://md.research.elamur.ai/free/en/papers/karlsson-1990-constraint-grammar-as-framework-parsing/) - [↑ back to papers of 1990](https://md.research.elamur.ai/free/en/papers/1990/) ## References 6 references, 0 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet. 1. Box, G. E. P., and G. C. Tiao, 1973 Bayesian Inference in Statistical Analysis, Addison-Wesley, Reading, Massachusetts. [find](https://scholar.google.com/scholar?q=Box%2C+G%2E+E%2E+P%2E%2C+and+G%2E+C%2E+Tiao%2C+1973+Bayesian+Inference+in+Statistical+Analysis%2C+Addison%2DWesley%2C+Reading%2C+Massachusetts%2E) 2. Gale, W., Church, K., (1990, submitted), "What's Wrong with Adding One?" Good, I.J., (1953), "The population frequencies of species and the estimation of population parameters," Biometrika, v. 40, pp. 237-264. [find](https://scholar.google.com/scholar?q=Gale%2C+W%2E%2C+Church%2C+K%2E%2C+%281990%2C+submitted%29%2C+%22What%27s+Wrong+with+Adding+One%3F%22+Good%2C+I%2EJ%2E%2C+%281953%29%2C+%22The+population+frequencies+of+species+and+the+estimation+of+population+parameters%2C%22+Biometrika%2C+v%2E+40%2C+pp%2E) 3. Jelinek, F. (1985) "Self-organized Language Modeling for Speech Recognition," IBM Report. [find](https://scholar.google.com/scholar?q=Jelinek%2C+F%2E+%281985%29+%22Self%2Dorganized+Language+Modeling+for+Speech+Recognition%2C%22+IBM+Report%2E) 4. Kucera, H., (1988), "Automated Word Substitution Using Numerical Rankings of Structural Disparity Between Misspelled Words & Candidate Substitution Words," Patent Number: 4,783,758. [find](https://scholar.google.com/scholar?q=Kucera%2C+H%2E%2C+%281988%29%2C+%22Automated+Word+Substitution+Using+Numerical+Rankings+of+Structural+Disparity+Between+Misspelled+Words+%26+Candidate+Substitution+Words%2C%22+Patent+Number%3A+4%2C783%2C758%2E) 5. Mcllroy, M., (1982), "Development of a Spelling List," IEEE Transactions on Communications, Vol. COM-30, No. 1. [find](https://scholar.google.com/scholar?q=Mcllroy%2C+M%2E%2C+%281982%29%2C+%22Development+of+a+Spelling+List%2C%22+IEEE+Transactions+on+Communications%2C+Vol%2E+COM%2D30%2C+No%2E+1%2E) 6. Accuracy of Probabilities o o d ,/' [find](https://scholar.google.com/scholar?q=Accuracy+of+Probabilities+o+o+d+%2C%2F%27) *Updated 24 October 2026*