怎样写一个拼写检查器六

取自 自然语言处理百科

2. P(w|c) 是误差模型. 到目前为止, 我们都是用的一个很简陋的模型: 距离越短, 概率越大. 这个也造成了一些问题, 比如下面的例子中, correct 函数返回了编辑距离为 1 的词作为答案, 而正确答案恰恰编辑距离是 2:

correct('reciet') => 'recite' (5); expected 'receipt' (14)
correct('adres') => 'acres' (37); expected 'address' (77)
correct('rember') => 'member' (51); expected 'remember' (162)
correct('juse') => 'just' (768); expected 'juice' (6)
correct('accesing') => 'acceding' (2); expected 'assessing' (1)

举个例子, 程序认为在 'adres' 中把 'd' 变成 'c' 从而得到 'acres' 的优先级比把 d 写成 dd 以及 s 写成 ss 的优先级高, 从而作出了错误的判断. 还有些时候程序在两个编辑距离一样的候选词中选择了错误的一个, 比如:

correct('thay') => 'that' (12513); expected 'they' (4939)
correct('cleark') => 'clear' (234); expected 'clerk' (26)
correct('wer') => 'her' (5285); expected 'were' (4290)
correct('bonas') => 'bones' (263); expected 'bonus' (3)
correct('plesent') => 'present' (330); expected 'pleasant' (97)

这个例子给我们一个同样的教训: 在 'thay' 中, 把 'a' 变成 'e' 的概率比把 'y' 拼成 't' 大. 为了正确的选择 'they', 我们至少要在先验概率上乘以 2.5, 才能使得最后 they 的几率超过 that, 从而选择 they.

显然, 我们可以用一个更好的模型来衡量拼错单词的概率. 比如说, 把一个字母顺手打成两个, 或者把一个元音打成另一个的情况都应该比其他打字错误更加容易发生. 当然, 更好的办法还是从数据入手: 比如说, 找一个拼写错误语料, 然后统计插入; 删除; 交换和变换在给定周围字母情况下的概率. 为了采集到这些概率, 可能我们需要非常大的数据集. 比如说, 如果我们带着观察左右两个字母作为上下文, 看看一个字母替换成另一个的概率, 就一共有 266 种情况, 也就是大约超过 3 亿个情况. 然后每种情况需要平均几个证据作为支撑, 因此我们知道10亿个字母的训练集. 如果为了保证更好的质量, 可能至少100亿个才差不多.

需要注意的是, 语言模型和误差模型之间是有联系的. 我们的程序中假设了编辑距离为 1 的优先于编辑距离为 2 的. 这种误差模型或多或少也使得语言模型的优点难以发挥. 我们之所以没有往语言模型中加入很多不常用的单词, 是因为我们担心添加这些单词后, 他们恰好和我们要更正的词编辑距离是1, 从而那些出现频率更高但是编辑距离为 2 的单词就不可能被选中了. 如果有一个更加好的误差模型, 或许我们就能够放心大胆的添加更多的不常用单词了. 下面就是一个因为添加不常用单词影响结果的例子:

   correct('wonted') => 'wonted' (2); expected 'wanted' (214)
   correct('planed') => 'planed' (2); expected 'planned' (16)
   correct('forth') => 'forth' (83); expected 'fourth' (79)
   correct('et') => 'et' (20); expected 'set' (325)

3.枚举所有可能的概率并且选择最大的: argmaxc. 我们的程序枚举了直到编辑距离为2的所有单词. 在测试集合中, 270个单词中, 只有3个编辑距离大于2, 但是在测试集合中, 400个中却有23个. 他们是:

   purple perpul
   curtains courtens
   minutes muinets
   successful sucssuful
   hierarchy heiarky
   profession preffeson
   weighted wagted
   inefficient ineffiect
   availability avaiblity
   thermawear thermawhere
   nature natior
   dissension desention
   unnecessarily unessasarily
   disappointing dissapoiting
   acquaintances aquantences
   thoughts thorts
   criticism citisum
   immediately imidatly
   necessary necasery
   necessary nessasary
   necessary nessisary
   unnecessary unessessay
   night nite
   minutes muiuets
   assessing accesing
   necessitates nessisitates

我们可以考虑有限的允许一些编辑距离为3的情况. 比如说, 我们可以只允许在元音旁边插入一个元音, 或者把元音替换, 或者把 c 写成 s 等等. 这些基本上就覆盖了上面所有的情况了.

转自Eric You XU翻译：http://blog.youxu.info/spell-correct.html

原文作者Peter Norvig，原始链接：http://norvig.com/spell-correct.html