CN104991889A - 一种基于模糊分词的非多字词错误自动校对方法 - Google Patents

Abstract

本发明公开了一种基于模糊分词的非多字词错误自动校对方法，该方法基于正确词词典与错字词词典进行精确切分，生成词图，然后利用模糊匹配算法计算中文词串的相似度，对精确切分的散串进行模糊匹配，将模糊匹配的结果加入到词图中，形成模糊词图，最后利用结合相似度的词的二元模型来计算模糊词图的最短路径，从而实现汉语非多字词错误的自动校对。本发明提供的基于模糊分词的非多字词错误自动校对方法，系统响应快、精度符合实际应用需求，有效性和准确性高。

Description

一种基于模糊分词的非多字词错误自动校对方法

技术领域

本发明涉及人工智能计算机领域中的自然语言处理，特别涉及中文文本自动校对领域。

背景技术

随着信息处理技术和互联网的高速发展，传统的文本工作几乎全部被计算机所取代，电子书、电子报纸、电子邮件、办公文件等电子文本、博客、微博等都成为人们日常生活的一部分，然而文本中的错误也越来越多，这给校对工作带来了很大的挑战。传统的人工校对效率低、强度大、周期长显然不能满足文本校对的需求。

文本自动校对是自然语言处理的主要应用之一，也是自然语言理解的难题。随着技术的发展，英文文本自动校对取得非常好的效果，已经商业化。相比与英文，汉语文本自动校对有以下几个难题：

1)中文文本校对没有类似于英文的“非词错误”——不在字典中的词，可以通过查字典来发现错误；中文文本中的汉字都会出现在字典中。

2)中文文本校对首先要进行中文分词，如果一个词中出现错别字，在分词的时候会分成单字散串——非多字词错误，这对中文文本的查错方法带来了难度。

3)中文中出现单字散串不一定有错别字，因为中文单字成词的能力非常强；

4)除了非多字词错误以外，中文中常把一个词写错成另外一个词典中的词，这种错误称为真词错误，这也是中文文本自动校对的难点；

针对上述几个问题，本发明提出并且实现了中文非多字词错误的自动查错和自动校对方法。

发明内容

发明目的：为了克服现有技术中存在的不足，本发明提供一种基于模糊分词的非多字词错误自动校对方法。

技术方案：为解决上述技术问题，本发明提供一种基于模糊分词的非多字词错误自动校对方法，该方法通过模糊分词的方法进行自动校对，包括以下步骤：

1)利用基于正确词词典和错字词词典建立的双数组Tire树结构，采用最大匹配方法对中文句子进行精确切分，建立精确分词词图，并对基于错字词词典进行精确切分的结果进行标记，同时将所述中文句子与错字词词典匹配的错字词对应的正确词加 入到词图中；

2)采用模糊匹配方法对精确切分的分词结果中的散串进行模糊匹配，得到与散串对应的相似的词及其相似度，将得到的与散串对应的相似的词加入到精确分词词图，形成模糊分词词图；

3)基于结合相似度的词的二元模型，计算模糊分词词图的最短路径，从而得到最终的切分结果，标记切分结果中的模糊匹配节点对应的原串为发现的错误，以实现汉语非多字词错误自动校对。

优选的，所述步骤1)包括以下步骤：

步骤11)建立正确词词典的双数组Trie树结构DicTrie；

步骤12)建立错字词词典的双数组Trie树结构TypoDicTrie：(TypoWord,CorrectWord),其中TypoWord为错字词，CorrectWord为该错字词对应的正确词；

步骤13)基于正确词词典的双数组Trie树结构DicTrie，采用最大匹配方法对所述中文句子进行精确切分，将切分后的词加入到词图中建立精确分词词图；

步骤14)基于错字词词典的双数组Trie树结构TypoDicTrie，采用最大匹配方法对所述中文句子进行精确切分，并对句子进行标记：将句子中搜索出的错字词词典中的错字词TypoWord标记为错误的词，并标记出与其对应的正确词CorrectWord；同时将句子中的各错词词TypoWord对应的正确词CorrectWord加入到精确分词词图中。

优选的，所述步骤2)包括：

遍历通过步骤1)精确分词后的中文句子中的字符，对各字符采用模糊匹配方法进行模糊匹配；计算模糊匹配上的字符串和与其对应的散串的相似度；判断相似度是否不小于阈值t_w，对相似度不小于阈值的模糊匹配上的字符串作为与其对应的散串的相似的词，并将其作为模糊匹配节点加入到精确分词词图中形成模糊分词词图，直到句子中的字符被遍历完；

其中所述计算模糊匹配上的字符串W₂和与其对应的散串W₁的相似度为：

其中：中文串W₁＝c₁c₂…c_n，W₂＝d₁d₂…d_m，editdis(W₁，W₂)为两个字符串的距离函数：

其中：sim(c_i,d_i)为汉字c_i与d_i的相似度：

其中：PSim(c_i,d_i)为汉字c_i和汉字d_i的拼音相似度，SSim(c_i,d_i)为汉字c_i和汉字d_i的形相似度，α和β分别表示拼音相似度和形相似度的权重，α+β＝1。

优选的，上述模糊匹配方法是通过单字替换、多字替换或缺字替换来进行的，所述单字替换为基于形相似的单字替换和/或基于音相似的单字替换。

优选的，对于用于用户输入法为拼音输入法或语音输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝1，形相似度的权重β＝0。

作为优选的，对于用于OCR识别纠错的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0，形相似度的权重β＝1。

优选的，对于用于用户输入法为拼音输入法和字形输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0.5，形相似度的权重β＝0.5。

优选的，所述步骤3)包括以下步骤：

步骤31)基于步骤1)对句子进行精确分词和步骤2)对句子进行模糊匹配后得到的模糊分词词图，得到多条路径，结合步骤2)得到的与散串对应的相似的词及其相似度，采用二元模型计算每种切分序列的概率：

其中W为词图中的某一条分词路径，W_i为路径中的第i个词，n是分词路径中词的个数；α(W_i-1,W′)表示对句子分词过程中原串为与模糊匹配节点对应的散串给予的惩罚值，当当前词是精确切分时α(W_i-1,W′)＝1，否则α(W_i-1,W′)＝sim(W_i-1,W′)，即句子中模糊匹配的原串W'与匹配上的词W_i-1的相似度，也称为模糊匹配上的字符串W_i-1和与其对应的散串W'的相似度；

步骤32)根据步骤31)得到的模糊分词词图，利用图的Dijkstra算法求解最短 路径，从而得到最终的切分结果；

步骤33)对最短路径中的模糊匹配节点，标记其对应的原串为含有错别字的词，并且模糊匹配得到的相似的词为其对应正确的词，从而实现了汉语非多字词错误自动校对。

优选的，上述阈值t_w为0.95。

有益效果：本发明提出了一种基于模糊分词的非多字词错误自动校对方法。该方法能在分词的过程中有效的对汉语文本中的“非多字词错误”进行识别和校对，并且采用的基于双数组Trie树的方法能快速的进行模糊分词。实验表明，本发明提供的模糊分词的“非多字词错误”自动校对的方法召回率达到75.9％，精度达到85％，纠正率达62％,纠错准确率达81.7％。系统响应快、精度符合实际应用需求，有效性和准确性高，具有较高的实用性。

附图说明

图1本发明提供的的模糊切分词图示例。

具体实施方式

下面结合附图和实施例对本发明作更进一步的说明。

本发明提供的一种基于模糊分词的非多字词错误自动校对方法，基于模糊分词的方法进行自动校对，包括以下步骤：

1)利用基于正确词词典和错字词词典建立的双数组Tire树结构，采用最大匹配方法对中文句子进行精确切分，建立精确分词词图，并对基于错字词词典进行精确切分的结果进行标记，同时将所述中文句子与错字词词典匹配的错字词对应的正确词加入到词图中。具体为：

首先利用正确词词典与错字词词典进行精确分词，建立精确分词词图，其中：

S：待切分的句子；Dic1:正确词词典，Dic2:错字词词典，po1:正确词典查找位置；pos2：错字词词典查找位置。

步骤11)建立正确词词典Dic1的双数组Trie树结构DicTrie；

步骤12)建立错字词词典Dic2的双数组Trie树结构TypoDicTrie：(TypoWord,CorrectWord),其中TypoWord为错字词，CorrectWord为该错字词对应的正确词；例如(无缘无古，无缘无故)；

步骤13)基于正确词词典的双数组Trie树结构DicTrie，采用最大匹配方法对所述中文句子进行精确切分，将切分后的词加入到词图中建立精确分词词图，如图1所示，本 实施例在词图中用实线框表示精确切分；

本实施例中为：利用正确词典Dic1从pos1(初始设置为0)位置前向最大搜索，假设搜索出正确词词条word1，将其加入精确分词词图，pos1更新为word1之后的位置；否则pos1指向当前位置的下一个字；重复搜索直到pos1执行到句子S的末尾；步骤14)基于错字词词典的双数组Trie树结构TypoDicTrie，采用最大匹配方法对所述中文句子进行精确切分，并对句子进行标记：将句子中搜索出的错字词词典中的错字词TypoWord标记为错误的词，并标记出与其对应的正确词CorrectWord；同时将句子中的各错词词TypoWord对应的正确词CorrectWord加入到精确分词词图中，如图1所示，本实施例在词图中用虚线框表示。

本实施例中为：利用错误词典Dic2从pos2(初始设置为0)位置前向最大搜索，若搜索出错字词TypoWord，将其对应的正确词条CorrectWord加入精确分词词图，并对句子中的错字词及其对应的正确词进行标记，pos2更新为TypoWord之后的位置；否则pos2指向当前位置的下一个字；重复搜索直到pos1执行到句子S的末尾。

举例，句子S＝"你们为什么经常无原无故扣取我的活费"。

经过上述步骤13)精确分词后，结果如图1所示，“你们”、“为什么”、“经常”、“无”、“原”、“无故”、“扣”、“取”、“我”、“的”、“活”、“费”为精确切分的结果，在词图中用实线框表示；

经过上述步骤14)精确分词后，结果如图1所示，其中因为(无原无故，无缘无故)是错字词词典中的词，利用其进行分词后、“无”、“原”、“无故”替换后为“无缘无故”，在词图中用虚线框表示。

2)采用模糊匹配方法对精确切分的分词结果中的散串进行模糊匹配，得到与散串对应的相似的词及其相似度，将得到的与散串对应的相似的词加入到精确分词词图，形成模糊分词词图。具体包括：

遍历通过步骤1)精确分词后的中文句子中的字符，对各字符采用模糊匹配方法进行模糊匹配，所述模糊匹配方法是通过单字替换、多字替换或缺字替换来进行的，所述单字替换为基于形相似的单字替换和/或基于音相似的单字替换；通过中文串相似度公式计算模糊匹配上的字符串和与其对应的散串的相似度；判断相似度是否不小于阈值t_w，对相似度不小于阈值的模糊匹配上的字符串作为与其对应的散串的相似的词，并将其作为模糊匹配节点加入到精确分词词图中形成模糊分词词图，直到句子中的字符被遍历完； 上述通过中文串相似度公式计算模糊匹配上的字符串W₂和与其对应的散串W₂的相似度为：

其中：中文串W₁＝c₁c₂…c_n，W₂＝d₁d₂…d_m，editdis(W₁，W₂)为两个字符串的距离函数：

其中：sim(c_i,d_i)为汉字c_i与d_i的相似度：

其中：PSim(c_i,d_i)为汉字c_i和汉字d_i的拼音相似度，SSim(c_i,d_i)为汉字c_i和汉字d_i的形相似度，α和β分别表示拼音相似度和形相似度的权重，α+β＝1。

对于用于用户输入法为拼音输入法或语音输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝1，形相似度的权重β＝0。

对于用于OCR识别纠错的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0，形相似度的权重β＝1。

对于用于用户输入法为拼音输入法和字形输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0.5，形相似度的权重β＝0.5。

具体在本实施例中，通过以下步骤来实现的：

步骤20)给定中文句子的起始匹配的位置nCurr＝0；

步骤21)从中文句子的当前位置nCurr，读入当前字符，对当前字符进行模糊匹配；

在模糊的过程中，当前位置的字可以是单字替换(通过字的形相似或音相似替换)、也可以是多字或缺字来计算相似度；

步骤22)利用中文串相似度公式计算两个字符串的相似度，即句子中模糊匹配的原串与匹配上的词的相似度，也可称为模糊匹配上的字符串和与其对应的散串的相似度，例如附图1中：

“无原”通过对“原”的拼音相似度和形相似度计算得到相似汉字“缘”等，利用中文 串相似度计算公式(1)，计算中文串“无原”与汉语词典中的词“无缘”的相似度。

本实施例中用户输入法为拼音输入法和字形输入法，因此设定α＝β＝0.5；

步骤23)如果相似度小于阈值t_w，则nCurr＝nCurr+1，进入步骤21)，否则进入步骤24)；因为汉字的混淆度是非常高的，本实施例中，所述阈值t_w为0.95，当然也可以根据实际应用进行调整，如0.90、0.92、0.98等；

步骤24)则相似度不小于阈值t_w，得到一组相似的词和相似度(sFuzzyWord,next,sim)，sFuzzyWord为匹配上的词，next为下一个要读入去进行模糊匹配的节点位置(next＝nCur+1)，sim是相似度，为从起始位置nCurr开始到匹配终止的位置的原串与sFuzzyWord进行计算相似度计算得到；如果next位置为句子的长度，则结束，否则更新nCurr为下一个要读入的位置next，跳回步骤21)；

步骤25)将模糊匹配的相似度不小于阈值t_w的相似的词，作为模糊匹配节点加入到精确分词词图，形成模糊分词词图；如图1所示，本实施例在词图中用虚线框表示。

在本实施例图1给出的示例中，散串“无”、“原”通过音相似模糊匹配找到词典中的词“无缘”，散串“活”、“费”通过形相似和缺字模糊匹配找到词典中的“话费”、“生活费”，将这些模糊匹配的节点加入到词图中，在词图中用虚线框表示。

3)基于结合相似度的词的二元模型，计算模糊分词词图的最短路径，从而得到最终的切分结果，标记切分结果中的模糊匹配节点对应的原串为发现的错误，以实现汉语非多字词错误自动校对。具体包括：

步骤31)基于步骤1)对句子进行精确分词和步骤2)对句子进行模糊匹配后得到的模糊分词词图，得到多条路径，结合步骤2)得到的与散串对应的相似的词及其相似度，采用二元模型计算每种切分序列的概率：

本发明采用结合相似度的词的二元模型来计算切分后的概率，对模糊切分的结果，加上一定的惩罚：其中W为词图中的某一条分词路径，W_i为路径中的第i个词，n是分词路径中词的个数；α(W_i-1,W′)表示对句子分词过程中原串为与模糊匹配节点对应的散串给予的惩罚值，如果当前词是精确切分，α(W_i-1,W′)＝1，否则α(W_i-1,W′)＝sim(W_i-1,W′)，即句子中模糊匹配的原串W'与匹配上的词W_i-1的相似度，也可称为模 糊匹配上的字符串W_i-1和与其对应的散串W'的相似度；

步骤32)根据步骤31)得到的模糊分词词图，利用图的Dijkstra算法求解最短路径，从而得到最终的切分结果；

步骤33)对最短路径中的模糊匹配节点，标记其对应的原串为含有错别字的词，并且模糊匹配得到的相似的词为其对应正确的词，从而实现了汉语非多字词错误自动校对。

如图1给出的本实施例的示例中，经过精确分词与模糊分词生成的词图，采用结合相似度的二元模型对该图进行最短路径求解，得到路径：Path＝{“S”、“你们”、“经常”、“为什么”、“无缘无故”、“扣”、“取”、“我”、“的”、“话费”}概率最大，即是图的最短路径，其中路径中虚线框节点“无缘无故”、“话费”为模糊匹配的节点，则原句子中的原串“无原无故”、“活费”中包含错别字，与模糊匹配正确的词“无缘无故”、“话费”比较，“原”、“活”为句子中的错别字，“无原无故”、“活费”即为非多字词错误。

四、实验

经历过多次开放的测试，实验采用2万行句子的测试语料，其中包含664处非多字词错误，其中非多字词错误包括别字替换型非多字词错误、字插入型非多字词错误以及字删除型非多字词错误。实验结果表明，本发明提供的非多字词错误识别召回率达到75.9％，精度为85％，纠正率达到62％，纠错准确率为81.7％，这一精度超过了现有技术，达到了实际应用的需求，具有较高的有效性和准确性。

以上实施列仅是本发明的较佳实施例，对本发明不构成限定，相关工作人员在不偏离本发明技术思想的范围内，所进行的任何修改、等同替换、改进等，均落在本发明的保护范围内。

Claims (9)

1.一种基于模糊分词的非多字词错误自动校对方法，其特征在于通过模糊分词的方法进行自动校对，包括以下步骤：

1)利用基于正确词词典和错字词词典建立的双数组Tire树结构，采用最大匹配方法对中文句子进行精确切分，建立精确分词词图，并对基于错字词词典进行精确切分的结果进行标记，同时将所述中文句子与错字词词典匹配的错字词对应的正确词加入到词图中；

2)采用模糊匹配方法对精确切分的分词结果中的散串进行模糊匹配，得到与散串对应的相似的词及其相似度，将得到的与散串对应的相似的词加入到精确分词词图，形成模糊分词词图；

3)基于结合相似度的词的二元模型，计算模糊分词词图的最短路径，从而得到最终的切分结果，标记切分结果中的模糊匹配节点对应的原串为发现的错误，以实现汉语非多字词错误自动校对。

2.根据权利要求1所述的基于模糊分词的非多字词错误自动校对方法，其特征在于所述步骤1)包括以下步骤：

步骤11)建立正确词词典的双数组Trie树结构DicTrie；

步骤12)建立错字词词典的双数组Trie树结构TypoDicTrie：(TypoWord,CorrectWord),其中TypoWord为错字词，CorrectWord为该错字词对应的正确词；

步骤13)基于正确词词典的双数组Trie树结构DicTrie，采用最大匹配方法对所述中文句子进行精确切分，将切分后的词加入到词图中建立精确分词词图；

步骤14)基于错字词词典的双数组Trie树结构TypoDicTrie，采用最大匹配方法对所述中文句子进行精确切分，并对句子进行标记：将句子中搜索出的错字词词典中的错字词TypoWord标记为错误的词，并标记出与其对应的正确词CorrectWord；同时将句子中的各错词词TypoWord对应的正确词CorrectWord加入到精确分词词图中。

3.根据权利要求1所述的基于模糊分词的非多字词错误自动校对方法，其特征在于所述步骤2)包括：

遍历通过步骤1)精确分词后的中文句子中的字符，对各字符采用模糊匹配方法进行模糊匹配；计算模糊匹配上的字符串和与其对应的散串的相似度；判断相似度是否不小于阈值t_w，对相似度不小于阈值的模糊匹配上的字符串作为与其对应的散串的相似的词，并将其作为模糊匹配节点加入到精确分词词图中形成模糊分词词图，直到句子中的字符被遍历完；

其中所述计算模糊匹配上的字符串W₂和与其对应的散串W₁的相似度为：

$Sim(W_1,W_2)=1-\frac{editdis\left(W_1{W}_2\right)}{max(m,n)}---\left(1\right);$

其中：中文串W₁＝c₁c₂...c_n，W₂＝d₁d₂...d_m，editdis(W₁，W₂)为两个字符串的距离函数：

$editdis(W_1,W_2)=\max \{\begin{array}{c}editdis(c_2\mathrm{...}{c}_n,d_1\mathrm{...}{d}_m)+1\\ editdis(c_1\mathrm{...}{c}_n,d_2\mathrm{...}{d}_m)+1\\ editdis(c_2\mathrm{...}{c}_n,d_1\mathrm{...}{d}_m)+1(1-sim(c_1,d_1))\end{array}---\left(2\right);$

其中：sim(c_i，d_i)为汉字c_i与d_i的相似度：

其中：PSim(c_i，d_i)为汉字c_i和汉字d_i的拼音相似度，SSim(c_i，d_i)为汉字c_i和汉字d_i的形相似度，α和β分别表示拼音相似度和形相似度的权重，α+β＝1。

4.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于：所述模糊匹配方法是通过单字替换、多字替换或缺字替换来进行的，所述单字替换为基于形相似的单字替换和/或基于音相似的单字替换。

5.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于：对于用于用户输入法为拼音输入法或语音输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝1，形相似度的权重β＝0。

6.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于：对于用于OCR识别纠错的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0，形相似度的权重β＝1。

7.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于：对于用于用户输入法为拼音输入法和字形输入法的汉语非多字词错误自动校对方法，所述拼音相似度的权重α＝0.5，形相似度的权重β＝0.5。

8.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于所述步骤3)包括以下步骤：

步骤31)基于步骤1)对句子进行精确分词和步骤2)对句子进行模糊匹配后得到的模糊分词词图，得到多条路径，结合步骤2)得到的与散串对应的相似的词及其相似度，采用二元模型计算每种切分序列的概率：

$\begin{array}{c}{W}^{*}=\arg \underset{W}{\max }P\left(W\right)\\ =\arg \underset{W}{\max }p\left(W_1\right)\underset{i=2}{\overset{n}{\Π}}p\left(W_i\right|W_{i-1})*\mathrm{\α}(W_{i-1},W^{\′})\end{array}---\left(4\right);$

其中W为词图中的某一条分词路径，W_i为路径中的第i个词，n是分词路径中词的个数；α(W_i-1，W′)表示对句子分词过程中原串为与模糊匹配节点对应的散串给予的惩罚值，当当前词是精确切分时α(W_i-1，W′)＝1，否则α(W_i-1，W′)＝sim(W_i-1，W′)，即句子中模糊匹配的原串W′与匹配上的词W_i-1的相似度，也称为模糊匹配上的字符串W_i-1和与其对应的散串W′的相似度；

步骤32)根据步骤31)得到的模糊分词词图，利用图的Dijkstra算法求解最短路径，从而得到最终的切分结果；

步骤33)对最短路径中的模糊匹配节点，标记其对应的原串为含有错别字的词，并且模糊匹配得到的相似的词为其对应正确的词，从而实现了汉语非多字词错误自动校对。

9.根据权利要求3所述的基于模糊分词的非多字词错误自动校对方法，其特征在于，所述阈值t_w为0.95。