- The first stage of the algorithm proposes candidate corrections by finding words that have a similar spelling to the input word. Analysis of spelling error data has shown that the majority of spelling errors consist of a single-letter change and so we often make the simplifying assumption that these candidates have an edit distance of 1 from the error word. To find this list of candidates we’ll use the minimum edit distance algorithm introduced in Chapter 2, but extended so that in addition to insertions, deletions, and substitutions, we’ll add a fourth type of edit, transpositions, in which two letters are swapped. The version of edit distance with transposition is called Damerau-Levenshtein edit distance.


The noisy channel algorithm

- We use a confusion matrix that contains counts of errors
- A confusion matrix lists the number of times one thing was confused with another.
- we’ll use four confusion matrices.
  + del[x, y]: count(xy typed as x)
  + ins[x, y]: count(x typed as xy)
  + sub[x, y]: count(x typed as y)
  + trans[x, y]: count(xy typed as yx)

Likelihood of channel/error model

- Is used for treating the misspelled word as if a correctly spelled word had been “distorted” by being passed through a noisy communication channel.
- Is a kind of Bayesian inference.

Saint Olaf College

Spelling correction is often considered from two perspectives, non-word spelling correction and real word spelling correction.

Spelling correction and the noisy channel

Detecting and correcting spelling errors even if they accidentally result in an actual
real word. 

This can happen from typographical errors (insertion, deletion, transposition) that accidentally produce a real word, or cognitive errors where the writer substituted the wrong spelling of a homophone or near-homophone. It is a much more difficult task than non-word errors correction since any word in the input text could be an error.

Learn Before

Related

Learn After