拼写纠正系列

NLP 中文拼写检测实现思路

NLP 中文拼写检测纠正算法整理

NLP 英文拼写算法,如果提升 100W 倍的性能?

NLP 中文拼写检测纠正 Paper

java 实现中英文拼写检查和错误纠正?可我只会写 CRUD 啊!

一个提升英文单词拼写检测性能 1000 倍的算法?

单词拼写纠正-03-leetcode edit-distance 72.力扣编辑距离

NLP 开源项目

nlp-hanzi-similar 汉字相似度

word-checker 拼写检测

pinyin 汉字转拼音

opencc4j 繁简体转换

sensitive-word 敏感词

目的

汉字不存在错字,但是存在别字。

查了一遍整个 github,只有一个比较靠谱的实现 correction,基于 C 语言实现。

相对成熟的产品 写作猫

核心思路

核心思路如下:

  • 使用语言模型计算句子或序列的合理性

  • bigram, trigram, 4-gram 结合,并对每个字的分数求平均以平滑每个字的得分

  • 根据Median Absolute Deviation算出outlier分数,并结合jieba分词结果确定需要修改的范围

  • 根据形近字、音近字构成的混淆集合列出候选字,并对需要修改的范围逐字改正

  • 句子中的错误会使分词结果更加细碎,结合替换字之后的分词结果确定需要改正的字

  • 探测句末语气词,如有错误直接改正

错字的场景

中文文本里说的错别字,归结为几种:

多字、漏字、字序错误、同音/音近字错误、形近字错误、语义混淆字错误。

拼写错误

步骤流程

在多种应用比如word中都有拼写检查和校正功能,具体步骤分为:

  1. 拼写错误检测

  2. 拼写错误校正:

自动校正:hte -> the

建议一个校正

建议多个校正

拼写错误类型:

Non-word Errors 非词错误:

即写了一个不是单词的词,比如graffe并不存在,应校正为giraffe

检测方法:认为任一不在字典中的词都是一个非词错误,因此字典本身越大越好

校正方法:为错误词产生一个候选,其是跟错误词相似的真词,然后选择加权编辑距离最短或者信道噪声概率最高的那个词。

Real-word Errors真词错误:

印刷错误:three->there

认知错误(同音异形字):piece -> peace; too -> two

检测方法:由于每个真词可能都是一个错误词,因此我们为每个词都产生一个候选集,包括该词本身、跟该词发音或拼写相似的词(编辑距离为1的英文单词)、同音异形词。

校正方法:按照信道噪声或者分类器选择最好的候选词。

非词错误校正

基本方法:使用The Noisy Channel Model of Spelling信道噪声模型

image

假设初始词经过一个噪声信道输出一个噪声词,即为可能的错误词,我们旨在对该噪声信道建模,从而使得在解码阶段能够根据噪声词得到一个猜测词,其跟初始词一致,即找到错误词正确的拼写。

而信道噪声我们视之为一个概率模型,如下:

输入:一个错误词x

旨在:找到一正确的词w

要求:

image

P(w)称为语言模型表示单词w为一个单词的概率,P(x w)称为信道概率(或错误概率)表示如果是w,x是w拼错的词的概率。

例子:

设:有一个错误词“acress”

1. 产生候选词:

相似拼写词

跟错误词之间小的编辑距离

采用Damerau-Levenshtein edit distance,计算的操作包括:插入、删除、置换和两个相邻字母之间的换位transposition,

以下是与“acress”编辑距离=1的列表:

image

80%错误词与正确词之间的编辑距离为1,大部分的编辑距离都小于等于2

允许插入空格或者连字符-:thisidea -> this idea; inlaw -> in-law

相似发音词

跟错误词的发音之间小的编辑距离

ps: 这里和中文一样,同音字或者形近字。

2. 选择最优候选词:套用公式

a) 计算语言模型P(w):可以采用之前说过的任一语言模型,比如unigram、bigram、trigram,大规模拼写校正也可以采用stupid backoff。

b) 计算信道概率P(x w):首先获得多个单词拼错的列表,然后计算混淆矩阵,然后按照混淆矩阵计算信道概率。

设:

image

有:

image

x和y为任一字母a-z,计数count表示后面那张情况发生的次数,其中插入和删除的情况都依赖于前一个字符,sub[x,y] 的混淆矩阵结果如下:

image

然后按照上述混淆矩阵计算信道概率:

image

c) 整体概率计算实例如下:

image

也可以选用语言模型计算整体概率,比如:使用bigram或trigram语言模型

image

3. 结果评估方法:

Wikipedia’s$list$of$common$English$misspelling

• Aspell$filtered$version$of$that$list

• Birkbeck$spelling$error$corpus

• Peter$Norvig’s$list$of$errors$(includes$Wikipedia$and$Birkbeck,$for$training$

or$tes/ng)

真词校正

25-40%的拼写错误都是真词错误。

具体步骤:

image

个人的理解就是真词的纠正是依赖上下文的。

所以根据原始句子,生成对应的可能纠正序列,计算出考虑最大的候选序列。

image

为了方便起见,我们假定每个句子中只有一个拼写错误,所以有:

image

要求从中找到一个组合序列使得序列的概率最高。

计算P(W):

方法1:语言模型,比如unigram、bigram等

方法2:信道模型:跟“一”中的方法一样,但还需要额外计算没有错误的概率P(w w),因为候选集中还包括自身词。
计算P(w w):其完全依赖于应用本身,表示一个词可能被拼错的概率,不同的应用概率不同:

image

经典系统 state of art

1. HCI issues in spelling

如果对校正结果非常自信:自动校正

一般自信:给定一个最好的校正方案

一点点自信:给定一个校正方案的列表

没有自信:给错误词做出标记,不校正

2. 经典噪声信道

实际应用中,信道概率和语言模型概率的权重并非一致,而是采用如下的计算公式:

image

然后在开发测试数据集中训练学习lambdas的值。

3. 语音错误模型

针对有相似发音的错误拼写的纠正

a) Metaphone, used in GNU aspell

将错误拼写转换为变音发音,规则如下

image

然后找到跟错误拼写的发音的编辑距离为1-2的词

打分

给结果列表打分,按照:

  1. 候选词跟错误词之间的加权编辑距离

  2. 候选词的发音与错误词发音的编辑距离

4. 信道模型的升级版

a) 允许更多的操作(Brill and Moore 200)

ent->ant

ph=>f

le->al

b) 在信道中结合发音(Toutanova and Moore 2003)

c)在计算信道概率 P(x|w) 时考虑更多的影响因素

  • The source letter

  • The target letter

  • Surrounding letters

  • The position in the word

  • Nearby keys on the keyboard

  • Homology on the keyboard

  • Pronunciations

  • Likely morpheme transformations

5. 基于分类器的真词拼写校正方法

  1. 考虑更多的特征

  2. 针对特定词对建立分类器

参考资料

nlp 公开课

斯坦福大学自然语言处理公开课课件汇总

拼写检测

stanford nlp第五课“拼写纠错(Spelling Correction)”

拼写校正

中文拼写检测

didi-拼写检测

Introduction to SIGHAN 2015 Bake-off for Chinese Spelling Check

data 下载地址