当前位置: 首页 > 搜索 > 正文

拼写纠错功能实现

1 星2 星3 星4 星5 星 (5 次投票, 评分: 5.00, 总分: 5)
Loading ... Loading ...
baidu_share
文章目录

一.拼写纠错定义

拼写纠错(Spelling Correction),又称拼写检查(Spelling Checker),往往被用于字处理软件、输入法和搜索引擎中.

拼写纠错一般可以拆分成两个子任务:

拼写错误检测Spelling Error Detection:按照错误类型不同,分为Non-word Errors和Real-word Errors。前者指那些拼写错误后的词本身就不合法,如错误的将“giraffe”写成“graffe”;后者指那些拼写错误后的词仍然是合法的情况,如将“there”错误拼写为“three”(形近),将“peace”错误拼写为“piece”(同音),将“two”错误拼写为“too”(同音)。

拼写纠错Spelling Error Correction:自动纠错,如把“hte”自动校正为“the”,或者给出一个最可能的拼写建议,甚至一个拼写建议列表。

二.Non-word拼写错误

拼写错误检测Spelling error detection:任何不被词典所包含的word均被当作拼写错误(spelling error),识别准确率依赖词典的规模和质量。

拼写纠错Spelling error correction:查找词典中与error最近似的word,常见的方法有:最短加权编辑距离(Shortest weighted edit distance)和最高噪音通道概率(Highest noisy channel probability)。

三.Real-word拼写错误

拼写错误检测Spelling error detection:每个word都作为拼写成员(spelling error candidate)。

拼写纠错Spelling error correction:从发音和拼写等角度,查找与word最近似的words集合作为拼写建议,常见的方法有最高噪音通道概率(Highest noisy channel probability)和分类(Classifier)。

四.基于噪声信道模型(Noisy Channel Model)的拼写纠错

Noisy Channel Model即噪声信道模型,或称信源信道模型,这是一个普适性的模型,被用于语音识别、拼写纠错、机器翻译、中文分词、词性标注、音字转换等众多应用领域。其形式很简单,如下图所示:
noisy
噪声信道试图通过带噪声的输出信号恢复输入信号,形式化定义为:
noisy-Formula
应用于拼写纠错任务的流程如下:
noisy-Process
noisy word(即splling error)被看作original word通过noisy channel转换得到,现在已知noisy word(用x表示)如何求得最大可能的original word(用w表示),公式如下:
noisy-bayesian
P(w)为先验概率,P(x|w)为转移概率,二者可以基于训练语料库建立语言模型和转移矩阵(又称error model,channel model)得到。

下面通过一个Non-word spelling error correction的例子加以解释:

给定拼写错误“acress”,首先通过词典匹配容易确定为“Non-word spelling error”;然后通过计算最小编辑距离获取最相似的candidate correction,需要特别说明的是,这里的最小编辑距离涉及四种操作:

1.插入一个字符(Insertion)
2.删除一个字符(Deletion)
3.替代一个字符(Substitution)
4.转义一个字符(Transposition)
edit-distance
据统计,80%的拼写错误编辑距离为1,几乎所有的拼写错误编辑距离小于等于2,基于此,可以减少大量不必要的计算。

通过计算最小编辑距离获取拼写建议候选集(candidate w),此时,我们希望选择概率最大的w作为最终的拼写建议,基于噪声信道模型思想,需要进一步计算P(w)和P(x|w)。

通过对语料库计数、平滑等处理可以很容易建立语言模型,即可得到P(w),如下表所示,计算Unigram Prior Probability(word总数:404,253,213)
edit-distance2
接下来,可以基于大量pair计算del、ins、sub和trans四种转移矩阵,然后求得转移概率P(x|w):
edit-distance3
计算P(“acress”|w)如下:
edit-distance4
计算P(w)P(“acress”|w)如下:
edit-distance5
“across”相比其他candidate可能性更大。

上面建立语言模型时采用了unigram,也可以推广到bigram,甚至更高阶,以较好的融入上下文信息。

如句子“a stellar and versatile acress whose combination of sass and glamour…”,计算bigram为:

P(actress|versatile)=.000021 P(whose|actress) = .0010

P(across|versatile) =.000021 P(whose|across) = .000006

则联合概率为:

P(“versatile actress whose”) = .000021*.0010 = 210 x10-10

P(“versatile across whose”) = .000021*.000006 = 1 x10-10

“actress”相比“across”可能性更大。

五.Real-word拼写纠错

Kukich(1992)指出有25%~40%的拼写错误都属于Real-word类型,与Non-word类型相比,纠错难度更大,因为句子中的每个word都被当作待纠错对象。通常,解决方法分两步:

1.遍历每个句子中的单词。生成单词集合。包含单词本身;所有的单字母编辑,英语单词;同音字.
2.选择最佳候选单词。包含特定任务的分类和噪声信道模型。

例如,给定句子S=w1,w2,w3,…,wn,为每个wi生成candidate set,如下:
Candidate(w1) = {w1, w’1 , w’’1 , w’’’1 ,…}
Candidate(w2) = {w2, w’2 , w’’2 , w’’’2 ,…}
… …
Candidate(wn) = {wn, w’n , w’’n , w’’’n ,…}

最后,选择概率最大的序列W为自动纠错后的句子,与中文分词、音字转换等应用相同,可以表示成词网格形式,转化为HMM的解码过程:
noisy-channel

为了简化起见,一般规定一个句子中最多有一个word存在splling error(事实上,所出现的情况也的确如此)。

六.应用

实际的拼写纠错系统一般会遵守如下HCI(Human Computer Interface)准则:
1.如果非常有信心纠正:自动纠正
2.缺乏一点信心纠正:给出最好的纠正单词。
3.缺乏信心纠正:给出一组纠正单词。
4.不能给出纠正:给出一个错误标志。

根据应用场景不同(Domain Sensitivity),需要对语言模型进行特别的处理,如:
gongshi
除了字面上的拼写错误,还有可能同音导致,所以,有些系统将“error model”转化为“Phonetic error model”解决拼写纠错问题。

另外,键盘上临近的按键更容易引入spelling error pair,据此可以对转移矩阵进行加权。
jianpan
我们还可以将拼写纠错问题转化为分类问题,通过构建训练语料库,抽取features,训练分类模型,预测新实例等一系列过程解决。

参考资料:
1.Lecture Slides: Spelling Correction
2.http://en.wikipedia.org
3.Kukich, Karen. 1992. Techniques for automatically correcting words in text. ACM Computing Surveys 24(4):377-437.

本文固定链接: http://www.chepoo.com/spelling-correction-function-realization.html | IT技术精华网

【上一篇】
【下一篇】

拼写纠错功能实现:等您坐沙发呢!

发表评论