式4

现在，我们使用Kernighan et al. (1990）的语料库来进行计算，这是AP新闻语料库（1988），规模为4400万词。所以，N为4400万。在这个语料库中，单词actress出现了1343次，单词acres出现了2879次，等等。我们计算得到如下的先验概率：

式5

其中，c表示候选更正单词，freq(c)表示c的出现次数（频度），p(c)表示c的概率。

似然度（p（t l c））的精确计算至今还是一个没有解决的（或不可解决的）研究题目；一个单词被错误拼写的精确概率与打字者是谁、打字者是否熟悉他所用的键盘、打字者的一只手是否比另一只手更疲倦等因素都有关系。幸运的是，尽管我们不能精确地计算p(t | c)，但是可以相当好地来估算它，因为预示插入、脱落、换位等错拼的大多数重要因素都是一些局部性的因素，诸如正确字母本身是否等同，字母如何被错拼以及错拼时周围的上下文等。例如，字母m和n经常彼此替代而发生错拼，其部分原因是由于这两个字母的等同性（这两个字母发音相近，在键盘的位置彼此相邻），部分原因是由于上下文（这两个字母不仅发音相近，而且它们往往出现在相似的上下文中）。

Kerninghan et al. (1990) 使用了一种估算这种概率的简单方法，不考虑大多数可能因素对错误概率的影响，而只是进行估算。例如，考虑在某个有错误的大语料库中e替代o的次数来估算p (acress l across)。这可以用含混矩阵（confusion matrix）来表示，含混矩阵是26x26的方框表，表示一个字母被另一个字母错误替代的次数。例如，在替代含混矩阵中，标记为[o, e]的单元将给出e替代o的次数；在插入含混矩阵中，标记为[t, s]的单元将给出t插入到s后面的次数。计算含混矩阵时，需要手工收集拼写错误及其相应的正确拼写，然后计算不同错误发生的次数，Grudin

(1983) 就是这样做的。Kernighan et al. (1990）使用了四个含混矩阵，每个含混矩阵代表一类单独错误。

del [x, y] 训练集中的字符xy在正确单词中应打字为x的次数。

ins [x，y] 训练集中的字符x在正确单词中应打字为xy的次数。

sub [x, y] x被打字为y的次数。

trans [x, y] xy被打字为yx的次数。

注意，在这里选择插入和脱落的条件是前面一个字符，也可以选择后面一个字符为条件。使用这些含混矩阵，估算p（t l c）如下（其中，Cp，表示单词c中的第p个字符）：

式6

图6 给出了每个潜在可能的更正的最后概率；根据式4 计算先验概率，使用式6和含混矩阵计算似然度，并把先验概率与似然度相乘。最后一栏给出了“归一化后的百分比”。

图6 

图6 每个候选更正等级的计算。注意，等级最高的单词不是actress而是acres（在表中最底部的两行），因为acres可以通过两个途径生成。在Kerninghan et al.(1990)中给出了del[ ]，ins[ ], sub[ ]和trans[ ]的全部含混矩阵

我们使用贝叶斯算法预见到acres是正确单词（这个单词的归一化百分比共计为45%），而actress 则是第二位的最可能的正确单词。遗憾的是，这个算法在这里算错了。文章作者的意图可以从如下的上下文中看得很清楚….was called a“stellar and versatile acress whose combination of sass and glamour has defined her .….”。从acress周围的词来看，它的正确单词显然应该是actress（女演员）而不是acres（英亩）。

我们所描述的算法要求手工标注数据来训练含混矩阵。Kernighan(1990）等的另一种不同方法是迭代地使用错拼更正算法本身来计算含混矩阵。选代算法首先用相等的值启动一个矩阵，这时任何字符都是相等的，无论它是脱落还是被另一个字符替代等。然后，在一个拼写错误词的集合上运行错拼更正算法。给出拼写错误类型及其相对应的更正，这时再计算含混矩阵，再运行拼写算法，这样地不断进行，便可以循序渐进地得到越来越好的含混矩阵。这个聪明的方法是重要的EM算法的一个实例 (Dempster et al.,1977)。Kernighan et al.（1990）的算法的评测是取一些具有两种潜在更正的拼写错误，请三个评判人从中挑一个最好的更正来投票。程序与大多数评判人的投票是一致的，占了87%。

责任编辑：admin