- 签证留学 |
- 笔译 |
- 口译
- 求职 |
- 日/韩语 |
- 德语
拼写更正有很多算法,我们将重点研究贝叶斯算法,因为这种算法具有普遍性,本文只重点讨论非词拼写错误。
Kernighan et al.(1990)首先提出把噪声信道方法应用于拼写更正,所用的correct程序把UNIX spell 程序拒绝的单词生成潜在地可能正确的单词表,并按式1排序,从中挑选出序号最高的单词作为真正正确的单词。
式1
让我们以Kernighan et al. (1990) 的错拼单词acress为例,将其使用的算法走一遍。这个算法分为两步:第一步是提出候选更正表(proposing candidate correction),第二步是对候选进行打分(scoring the candidate )。
为了提出候选更正表,Kernighan等简单地假设:正确单词与错拼单词的差别只表现为插入、脱落、替代和换位这四种方式中的一种。Damerau(1964)的结果说明,尽管这个假设可能漏掉某些更正,但它可以对付在人的打字文本中的大多数拼写错误。这个候选单词表可以从错拼单词生成,而把在单词中引起的任何一个单独的转换方式应用于一个大型的联机词典就可以得到错拼单词(typo)。把所有的转换方式应用于acress,就可以得到图2中的候选单词表。
式2
算法的第二步是使用式2来给候选更正打分。令t表示错拼单词(typo),c表示候选更正集合C上的元素c。这样,最佳的更正为式3
式3
图2
错拼词acress的候选更正表以及产生错误的转换方式(Kernighan et al.,1990),“-”表示零字母正如在式1中一样,我们在式2中省略了分母,因为错拼词为t,所以对于所有的c,t的概率P(t)是一个常数。每个更正的先验概率P(c),可以根据单词c在某个语料库中出现的频繁程度次数来计算。然后,用所有单词的总出现次数来归一化(normalizing)这个频繁程度次数。所以,一个更正单词c的概率就等于c的出现次数除以语料库中的词数N。零次数可能会引起问题,所以我们给所有出现次数都加0.5。这种做法称为“平滑”(smoothing)。注意,在式4中不能只用单词总数N来除,因为我们对每个更正单词的出现次数都加了0.5,所以也要给词汇中的单词V加0.5。