Introduction

Every time you type "teh" and your phone silently fixes it to "the", a small probabilistic argument has just run in the background. The fix feels magical, but the logic behind it has a name: the noisy-channel model.

The idea comes from Claude Shannon's 1948 information theory. Imagine the word you intended to type passes through a noisy channel — your fingers — and arrives on screen as a garbled version. The corrector's job is to invert the channel: given the garbled output, find the intended word that most plausibly produced it.

Bayes' theorem turns that intuition into a formula. The best correction w^\hat{w} of a typed string tt is:

w^=arg⁡max⁡w∈vocabulary  P(w∣t)=arg⁡max⁡w  P(t∣w)⋅P(w)\hat{w} = \underset{w \in \text{vocabulary}}{\arg\max}\; P(w \mid t) = \underset{w}{\arg\max}\; P(t \mid w) \cdot P(w)

Two factors compete: P(t∣w)P(t \mid w), the error model (how likely you are to type tt when you meant ww), and P(w)P(w), the language model (how common ww is in ordinary text). The winner is whichever candidate word maximizes their product.

This solved version of autocorrect — combining an error model with a language model — was popularized in NLP by researchers at Bell Labs and IBM in the 1990s, and brought to wide attention by Peter Norvig's celebrated 2007 essay "How to Write a Spelling Corrector."

Try It

Type a word — misspelled or not — and the corrector will generate every candidate within edit distance 1 (one insertion, deletion, substitution, or transposition), score each by P(t∣w)⋅P(w)P(t \mid w) \cdot P(w), and rank them best-first.

<!-- Noisy-channel spell corrector demo -->
<p class="hint">Type a word (misspelled or not). The corrector generates all candidates at edit distance 1, scores each by <b>error model × language model</b>, and ranks them best-first. The top result (★) is the Bayes-optimal correction.</p>
<div class="input-row">
  <input id="typo" type="text" placeholder="e.g. speling" maxlength="20" autocomplete="off" spellcheck="false" />
  <button id="correct-btn" type="button">Correct</button>
</div>
<div id="results" class="results" role="region" aria-live="polite"></div>
<div class="btns-row">
  <button id="reset-btn" type="button" class="ghost">Reset</button>
</div>

/* Demo layout and result table styles */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; padding: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .8rem; line-height: 1.5; }
.input-row { display: flex; gap: .5rem; flex-wrap: wrap; margin-bottom: .7rem; }
input { flex: 1 1 160px; font: 1rem system-ui, sans-serif; padding: .42rem .7rem;
        border: 1px solid #adb1b8; border-radius: 8px; outline: none; }
input:focus { border-color: #1d3557; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem;
         border: 1px solid #1d3557; background: #1d3557; color: #fff;
         border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { min-height: 2rem; margin-bottom: .5rem; }
.results table { width: 100%; border-collapse: collapse; font-size: .88rem; }
.results th { text-align: left; padding: .3rem .5rem; color: #555; font-weight: 600;
              border-bottom: 2px solid #cdd9e3; }
.results td { padding: .28rem .5rem; border-bottom: 1px solid #e8eef3; }
.results tr.top-row td { font-weight: 700; color: #0a7d33; }
.results tr.exact-row td { font-weight: 700; color: #1d3557; }
.results .bar-cell { min-width: 80px; }
.bar-bg { background: #e8eef3; border-radius: 4px; height: 10px; }
.bar-fill { background: #1d3557; border-radius: 4px; height: 10px; }
.msg { font-size: .95rem; font-weight: 600; padding: .4rem 0; }
.msg.ok { color: #0a7d33; }
.msg.bad { color: #c92f3c; }
.btns-row { display: flex; gap: .5rem; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Noisy-channel model: best correction = argmax_w P(t|w) * P(w)
// P(t|w) = error model (how likely to type t when meaning w); P(w) = language model (word frequency)

// Simplified unigram language model: word -> relative frequency
// Higher frequency = more common word; 0 = not in vocabulary
const FREQ = {
  the:2000,be:900,to:800,of:750,and:720,a:700,in:680,that:620,have:580,
  it:560,for:520,not:500,on:480,with:460,he:440,as:420,you:400,do:380,
  at:360,this:340,but:320,his:310,by:300,from:290,they:280,we:270,
  say:260,her:250,she:240,or:230,an:220,will:210,my:200,one:190,all:185,
  would:180,there:175,their:170,what:165,so:160,up:155,out:150,if:145,
  about:140,who:135,get:130,which:125,go:120,me:118,when:115,make:112,
  can:110,like:108,time:105,no:103,just:100,him:98,know:96,take:94,
  people:92,into:90,year:88,your:86,good:84,some:82,could:80,them:78,
  see:76,other:74,than:72,then:70,now:68,look:66,come:64,its:62,over:60,
  think:58,also:56,back:54,after:52,use:50,two:48,how:46,our:44,work:42,
  first:40,well:38,way:36,even:34,new:32,want:30,because:28,any:26,
  these:24,give:22,day:20,most:18,us:17,great:16,between:15,need:14,
  large:13,often:12,hand:11,high:10,place:9,hold:8,world:7,spell:6,
  correct:5,letter:4,word:3,edit:2,model:1,type:2,typo:1,error:1,
  their:170,there:170,they:280,than:72,then:70,
  the:2000,teh:0,hte:0,eth:0,
  hear:15,here:60,hare:8,bare:7,care:10,dare:5,fare:4,rare:6,
  from:290,form:25,farm:8,firm:10,fore:4,fork:5,fort:6,ford:4,
  have:580,gave:30,cave:10,save:25,wave:12,nave:2,rave:5,
  love:40,live:45,line:35,lime:6,like:108,life:38,lift:10,
  make:112,lake:18,cake:15,bake:12,fake:10,rake:6,sake:8,take:94,wake:9,
  come:64,came:22,same:28,game:20,name:30,fame:7,lame:5,tame:4,
  write:22,quite:8,white:18,while:24,whole:12
};

const ALPHA = 'abcdefghijklmnopqrstuvwxyz';

// Generate all strings at edit distance 1 from the typed word
function edits1(word) {
  const res = new Set();
  const w = word.toLowerCase();
  const n = w.length;
  // deletions: remove one character
  for (let i = 0; i < n; i++) res.add(w.slice(0,i) + w.slice(i+1));
  // transpositions: swap two adjacent characters
  for (let i = 0; i < n-1; i++) res.add(w.slice(0,i)+w[i+1]+w[i]+w.slice(i+2));
  // substitutions: replace one character with another
  for (let i = 0; i < n; i++) for (const c of ALPHA) res.add(w.slice(0,i)+c+w.slice(i+1));
  // insertions: add one character at any position
  for (let i = 0; i <= n; i++) for (const c of ALPHA) res.add(w.slice(0,i)+c+w.slice(i));
  return res;
}

// Score a candidate: combine error model and language model
// Returns 0 if candidate is not in vocabulary
function score(typed, candidate) {
  const t = typed.toLowerCase();
  const c = candidate.toLowerCase();
  const freq = FREQ[c] || 0;
  if (freq === 0) return 0;
  const lm = freq;  // language model: raw frequency as proxy for P(w)
  // error model: uniform channel — exact match gets highest weight, any 1-edit gets base weight
  let err;
  if (t === c) {
    err = 1000;  // exact match: the typed word is already known — penalize nothing
  } else {
    err = 100;   // one edit away — uniform channel assumes all edits equally likely
  }
  return err * lm;
}

function correct() {
  const raw = document.getElementById('typo').value.trim();
  if (!raw) { showMsg('Please type a word first.', 'bad'); return; }
  const typed = raw.toLowerCase();
  const candidates = edits1(typed);
  candidates.add(typed); // also score the typed word itself (it may be a valid word)

  // keep only candidates in vocabulary; rank by score descending
  const scored = [];
  for (const c of candidates) {
    const s = score(typed, c);
    if (s > 0) scored.push({ word: c, s });
  }

  if (scored.length === 0) { showMsg(i18nFmt('No known corrections found for "%w%".', { w: raw }), 'bad'); return; }

  scored.sort((a, b) => b.s - a.s);
  const top = scored.slice(0, 8);
  const maxS = top[0].s;

  let html = '<table><thead><tr><th>Rank</th><th>Word</th><th>Score</th><th class="bar-cell">Fit</th></tr></thead><tbody>';
  top.forEach(({ word, s }, i) => {
    const isExact = word === typed;
    const isTop = i === 0;
    const cls = isTop ? 'top-row' : (isExact ? 'exact-row' : '');
    const pct = Math.round((s / maxS) * 100);
    const display = isTop ? '&#9733; ' + word : word;
    html += `<tr class="${cls}"><td>${i+1}</td><td>${display}</td><td>${s.toLocaleString()}</td><td class="bar-cell"><div class="bar-bg"><div class="bar-fill" style="width:${pct}%"></div></div></td></tr>`;
  });
  html += '</tbody></table>';
  document.getElementById('results').innerHTML = html;
}

function showMsg(text, cls) {
  document.getElementById('results').innerHTML = `<div class="msg ${cls}">${text}</div>`;
}

document.getElementById('correct-btn').addEventListener('click', correct);
document.getElementById('typo').addEventListener('keydown', e => { if (e.key === 'Enter') correct(); });
document.getElementById('reset-btn').addEventListener('click', () => {
  document.getElementById('typo').value = '';
  document.getElementById('results').innerHTML = '';
});
Result
Console

Notice how the top candidate is almost always what you intended. The error model penalizes candidates that require an unlikely substitution; the language model boosts common words. A rare but correctly spelled word can still lose to a very common near-neighbor — that is the tension at the heart of autocorrect.

The Real Complexity

The formula w^=arg⁡max⁡wP(t∣w)⋅P(w)\hat{w} = \arg\max_w P(t \mid w) \cdot P(w) looks clean, but estimating both factors well is where the work lives.

Generating candidates. For a word of length nn over an alphabet of size σ\sigma, edit-distance-1 gives O(n⋅σ)O(n \cdot \sigma) candidates — a few thousand for English. Distance 2 squares that; real systems prune aggressively.

The error model P(t∣w)P(t \mid w). The simplest version treats all single-character errors as equally likely — the "uniform channel." Better systems use a confusion matrix trained on observed typos: the probability that someone types "ie" when they meant "ei" differs from the probability of a random substitution. Keyboard-distance models go further, weighting nearby keys higher.

The language model P(w)P(w). A unigram model counts how often each word appears in a large corpus — the approach in the interactive demo above. Real systems use n-gram models (conditioning on the surrounding words) or neural language models that represent meaning as vectors. Context changes everything: "their" vs "there" vs "they're" are all common words, and only the sentence decides which is right.

Why it connects to information theory. Shannon's channel capacity theorem tells us there exist codes that can recover the original message with arbitrarily low error — but spelling correction cannot use those codes, because the "channel" (human fingers) is fixed and noisy in its own idiosyncratic way. What Bayes gives us is the optimal decision rule given the channel we have.

Modern neural spell checkers (integrated into large language models) subsume the noisy-channel decomposition into a single end-to-end model, but the Bayesian intuition remains the clearest lens for understanding why any correction is preferred over another.

Where It Matters

The noisy-channel view of text is one of the most productive framings in all of NLP:

  • Keyboard autocorrect: every smartphone keyboard runs a variant of this model, typically augmented with a neural language model trained on billions of keystrokes.
  • Search query correction: when Google suggests "did you mean …?", it is scoring candidate queries by their edit distance to what you typed, weighted by query frequency — the same formula.
  • OCR post-processing: characters scanned from images arrive with substitution errors that have their own confusion matrix (e.g., "0" vs "O", "l" vs "1"). A channel model cleans the output.
  • Speech recognition: the acoustic model plays the role of P(t∣w)P(t \mid w) and the language model plays P(w)P(w); decoding is exactly the noisy-channel arg-max.
  • Machine translation: the original IBM models (Brown et al., 1993) framed translation as a noisy channel from target language to source language, then inverted it with Bayes — the founding insight of statistical MT.

Understand the noisy-channel model and you hold the conceptual key to a wide swath of language technology. It also connects naturally to Bayesian inference, where the same prior-times-likelihood structure appears across all of statistics.

Conclusion

Spelling correction looks like a simple string-matching task, but underneath it is Bayesian inference applied to a communication channel. The word you intended is the hidden signal; your keystrokes are the noisy output; and Bayes' theorem is the optimal decoder.

The formula w^=arg⁡max⁡wP(t∣w)⋅P(w)\hat{w} = \arg\max_w P(t \mid w) \cdot P(w) packages two kinds of knowledge — how fingers err and how language flows — into a single ranking. Get both factors right and you get autocorrect that feels like mind-reading. Get them wrong and you get the notorious autocorrect fails that flood the internet.

The same math that fixes "teh" → "the" also decodes speech, cleans up OCR, and originally powered machine translation. Bayes was doing NLP long before the term existed.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/spell-correction-noisy-channel/Content licensed under CC BY-NC 4.0.