- 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.


Saint Olaf College

- 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.

The Noisy Channel

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)

Learn Before

Related