Spelling Correction

拼写错误类型

• Non-word errors: 单词不存在于字典之中，即完全写错了。例如 teh → the
• Real-word errors: 单词在字典中，但写成其他单词了，与想表达的不符。具体来说，又分为两种错误：
  • typographical errors: three → there
  • cognitive errors： too → two， your → you're

Noisy channel model for non-word spelling correction

假设 a = {a-z, A-Z, ...} 是英语所有可能构成单词的字母集合， a* 为由这个字母表所构成的任意有限长度的字符串集合。 其中所有有效的单词构成的集合D是a*的一个子集。而noise channel 是指从目的词（即字典）与实际接收到的字符串x所构成的矩阵。
对于所捕获到的，存在拼写错误的字符串x, 目标是在字典中找到一个词w，使这一情况出现的概率最大。 即：

由于用户实际想拼写的单词是不确定的，因此需要生成一个修正候选列表（candidate corrections），这个列表基于两个规则：

• shortest weighted edit distance
• highest noisy channel probability

因此， noisy channel 实际上可以理解为，用户所输入的一个错误的字符串，经过怎样的变换过程可以得到若干个正确的单词。变换的过程越多，相当于channel越长， 而找候选列表的过程也就是找channel最短的过程。

最小编辑距离

最小编辑距离（minimum edit distance）是指从一个string到另一个string所需的最小编辑步骤，包括：插入、删除、替换。而采用这三种编辑手段计算所得的距离又称为Levenshtein distance。这一距离将所有操作的cost都记为1.

但严格来说，替换这一操作等于先删除再插入。因此这一操作的cost可当成是2（更接近实际操作的cost）。 此外，对于Damerau–Levenshtein distance，这一距离还新增了transposition of two adjacent characters 这一操作。

如何计算两个单词的edit distance

1. 单词长度对齐→例如在单词头部＋#作为占位符

2. 以对齐后的单词长度n建立一个n×n的矩阵。其中(n, 0)为坐标原点，横纵坐标分别对应两个单词各个字母的位置。

3. 按照以下方法遍历矩阵n，计算edit distance

   
   computing distance
   

   举个例子，计算单词intention → execution的 edit 距离如下：

   
   example

4. 从矩阵右上角沿着对角线上数值最小的路径回退，走过的路径即为应执行的edit操作。

• 若路径上当前位置与后一步的数值相同→说明一致不需修改
• 若数值不同：
  • 如果是落在对角线上→当前位置的字符执行替换操作
  • 如果是落在对角线左侧→ 执行插入操作

  • 如果是落在对角线右侧 → 执行删除操作

    
    editing path

候选词列表的产生

• 80%的错误可以在1个edit 操作内纠正
• 几乎所有的错误都可以在2个 edit 操作内纠正
  由于这是个NP问题，计算量很大，因此只需要计算考虑edit 操作数目 为 2 的单词即可。(intention → execution需要5步操作，因此没必要考虑这种情况。)
  此外，非字母符号也应该在纠正过程中考虑在内， 例如goodmorning → good morning， inlaw → in-law。
  同时，也应该计算不同错误出现的概率问题。 例如， P(the | teh) → high， P(the | tze) → low
  而这一点的实现也是基于统计的，也即需要从样本中统计不同错误出现的概率。

channel model probability

统计概率的计算方法如下：
首先对错误统计的方式：

• 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)
  然后，基于一个很大的语料库，统计不同单词出现的概率以及用这个单词时出现不同拼写错误的概率。

其中，w是正确的单词， x 表示捕捉到的错误字符串。 w_i 是指w中的第 i 个字符。
以一个错误的输入 acress 为例， 可能的单词与其对应的概率如下：

显然，用户想输入across的概率最大，这样候选词列表就有了排序和过滤的依据（大概率的排在前面，概率过低的可以不显示）。另一方面，P(word) 也可以使用bigram，这样就与上下文取得了联系，能更好的预测用户想要输入的单词。

Noisy channel model for real-word spelling correction

有25%-40%的错误属于 real-word error
这一部分是language model与noisy channel model的结合。假设用户输入的所有单词都没有non-word error

1. 对于输入的每个单词，无论拼写是否正确，依然生成若干个候选列表
2. 当输入多个单词后， 利用LM， 例如trigram等，判断哪种组合的概率更高
3. 只考虑有一个词需要变更的情况。

举个例子，用户输入 "two of thew"：

example

仅考虑 two off thew, two of the, too of thew 的概率，取最大值。

其他可用于spelling correction 的因素

• 根据单词发音， 优先考虑同音异义词的错误情况
  例如：bigger then → bigger than， a peace of paper → a piece of paper
• 考虑不同键盘布局下最容易错误输入的字母概率。
  例如，对于 QWERT 布局的键盘，e 和 w 这两个字母输入时更容易出错 threw → three
• ...

相关资源

Peter Norvig’s list of errors
Wikipedia’s list of common misspelllings
GNU Aspell
Hunspell
How to Write a Spelling Corrector