基于搜索引擎日志的中文纠错方法研究

杨苏稳 张晓如

摘要：针对用户使用搜索引擎输入关键词查询信息时，由于输入法的原因或者不小心输入错误关键词等，致使搜索结果不符合用户预期的问题，提出基于搜索引擎日志的中文纠错方法。首先对用户网络日志展开研究，对数据进行预处理，将用户常见错误分为两人类：一类为拼音引起的错误，针对该类错误，参考并改进了基于拼音索引的中文模糊匹配算法进行纠错;另一类为多字、少字、异位及别字引起的错误，针对该类错误，设计了模糊匹配方法结合最小编辑距离方法进行纠错。经过实验验证，证明了该纠错方法的有效性，该方法能够一定程度上提升用户体验，满足实际工程需要。

关键词：搜索引擎日志;中文纠错;模糊匹配;最小编辑距离

DOI：10.11907/rjdk.192456 开放科学（资源服务）标识码（OSID）：

中图分类号：TP391文献标识码：A 文章编号：1672-7800（2020）006-0182-06

0 引言

随着大数据时代的到来，越来越多的数据充斥着整个互联网，如何在海量数据中找到有用信息已变得越来越迫切。搜索引擎的出现极大地方便了用户进行信息查找，然而，用户在查询输入时，由于输入法的原因或者不细心等，总会存在输入错别字、多字甚至少字的现象。因此，对查询词进行校正是提高查询效率的重要手段。为了提升用户体验，本文设计了基于搜索引擎日志的中文纠错方案。

中文文本校对相对于英文文本校对起步较晚，目前中文文本纠错主要是针对字级别和词级别的纠错，常用的有基于概率统计的方法、基于机器学习的方法、基于规则的方法和基于混合的方法。

（1）基于概率统计的方法。基于概率统计的纠错方法是利用大规模语料提取文字、词以及词性的上下文关联度、搭配等特征，然后基于此进行文本纠错。常见的概率模型有N-gram语言模型、最大熵模型等，但是统计模型存在难以获得大规模训练语料以及数据稀疏表示等问题。陈智鹏等通过建立N-gram模型得到候选集，根据TF/IDF计算权重排序获得最优解推荐给用户，实现自动纠错;马金山等提出使用N-gram模型局部查错法与依存分析全局查错法对文本进行自动校对;徐白在考虑输入词串上下文的同时，统计研究查询串特征，融合N-gram相似性、拼音相似度等因素进行排序，实现文本的自动校对功能。

（2）基于机器学习的方法。基于机器学习的方法可以理解为排除有歧义词的过程，对待校对的目标词建立混淆集，用混淆集替换相应位置上的汉字产生候选集，然后根据相关规则对候选集进行排序实现校对功能。排序规则可以为一种或多种，如利用上下文特征、统计语言模型或将几种因素相结合等。张磊等提出一种快速的中文模糊词匹配算法，实现了基于相似词集代换与语言模型评分的自动校对方法，能够检查并纠正加字、减字及字串替换等错误;张照煌提出利用混淆集替换的方法实现文本自动校对，首先根据相似字特征生成混淆集，然后利用混淆集替换对应位置上的字生成候选集，最后利用统计模型对候选集进行打分，根据评分高低对候选集进行排序。

（3）基于规则或语义学知识的方法。在研究基于规则或语义学知识进行自动校对的过程中，一般先对大规模语料文本进行观察和统计，对其字、词、词法、句法、语义和语用错误进行分析与总结，通过总结错误发生的共同规律，得到能够反映错误的一般產生式规则集。在进行文本校对时，直接运用这些产生式集进行查错判断，若出现错误，再通过相关运算得到错字词的替换集，并从替换集中选择一个概率最大的词作为修正的候选词。易蓉湘等通过对大量汉语错误文本的分析，总结出错字词规律和产生式规则，并基于这些规则实现文本查错与纠错功能。

（4）基于混合的方法。基于混合的方法，顾名思义就是综合使用上述方法。由于错误类型种类繁多，无法一一对其规律进行总结，因此仅使用一种方法很难覆盖所有错误问题。为了更好地解决该问题，一般采用混合方法，如采用规则与统计相结合的方法。刘亮亮等提出一种多特征融合的模型，然后利用规则判断中文文本中的真词错误;段建勇等提出基于统计与特征相结合的查询纠错方法，对用户输入的查询词建模，生成混淆集，再利用混淆集排序模型选出最优结果推荐给用户，达到查错、纠错的目的;Subramaniam等利用查询日志建立语言模型，并结合最小编辑距离进行纠错;王斯宇等提出基于混淆集及上下文特征的方法进行纠错。

通过分析国内外研究现状发现，上述纠错方法还存在以下不足：①未对错误原因及类型进行详细的分类与总结;②提出的纠错方法只针对常见的大部分错误，并未综合考虑所有错误类别，无法对少数但现实存在的错误类型进行处理;③尽管有些方法融合了多种纠错方法，但没有形成完整、清晰的纠错流程。

针对上述纠错方法存在的不足，本文进行如下改进：

第一，通过对搜索引擎日志的研究，总结搜索引擎日志中的常见错误，分析导致错误的原因，并将其分为两类：①全拼音、半拼音、音相似错误、键相邻错误及方言差异导致的错误均为拼音的声母、韵母或音调部分发生错误而导致的;②多字、少字、异位及别字引起的错误。

第二，针对错别字的错误类型提出一整套纠错流程，针对不同的错误类型，采用不同纠错方法进行处理。

第三，针对上述第一类错误，本文参考曹犟等提出的基于拼音索引的中文模糊匹配算法进行纠错，但该方法仅考虑了拼音的声母或韵母及音调变化导致的错误，而忽略了键盘输入时字母相对位置导致的错误。为此，本文改进了基于拼音纠错的算法，增加了对键相邻错误的纠错。针对上述第二类错误，本文融合传统模糊匹配方法与最小编辑距离方法进行纠错。

1 相关技术介绍

发现并总结用户常见输入错误，是针对不同错误类别设计纠错方法的基础。通过对查询日志的分析，用户常见输人错误主要有全拼音错误、半拼音错误、音相似错误、键相邻错误、方言差异导致的错误，以及别字、多字、少字及字间颠倒导致的错误等。其中全拼音、半拼音、音相似错误、键相邻错误及方言差异导致的错误均为拼音的声母、韵母或音调部分发生错误而导致的，一般采用拼音纠错的方法进行纠正。曹犟等提出的基于拼音索引的纠错方法能够有效解决此类问题。别字、多字、少字及字间颠倒导致的错误则一般使用模糊匹配或最小编辑距离方法进行纠错。

1.1 基于拼音编辑距离的纠错方法

1.1.1 基于拼音编辑距离的定义

对于一个汉字的音节而言，它与另外一个音节的差异可分为3种：声母差异、韵母差异和声调差异。其音节的声母、韵母和声调取值的可能性都是有限的，可利用枚举方式定义音节从一种取值转换为另一种取值的编辑距离。所以，对于一个给定音节，很容易找到所有与其编辑距离为.的音节。例如，要找到所有与/lan2/编辑距离为1的音节，则取值只可能是：①声母改变1个距离单位，韵母和声调不变;②韵母改变1个距离单位，声母和声调不变;③声母和韵母都不变，仅声调改变1个距离单位。音节编辑距离最后均转化为排列组合问题。

1.1.2 拼音纠错示例

通过对网络日志的分析可知，拼音错误是输人中的主要错误，但在拼音错误中，还可以作细化分类。

（1）音同而误。音同而误是指拼音相同而发生的替换错误。这类错误由于拼音输入法的原因经常发生，且很难区别。

例如：现在乘汽车必需携带身份证吗？

分析：句中“必需”是“必须”的同音替换错误。

（2）音同声不同而误。即因音调不同而发生的错误。

例如：百毒的创始人是谁？

分析：句中“百毒”就是因为“/du2/”与“/du4/”拼音相同而声调不同造成的替换错误。

（3）音似而误。音似而误是指因拼音相似而造成的替换错误，通常是由于声母或韵母发生改变而造成的替换错误，也可能是因为方言差异或相邻键造成的输入错误。

例l：牛德华今年有几场演唱会？

分析：句中“牛德华”就是因为方言中不区分“L/N”而造成的错误。

例2：涅槃从生是什么意思？

分析：句中“从生”是因为“/eong2/”和“/ehong2/”音似而发生的替换错误。

根据上述总结，在拼音错误中，要么是拼音声调发生改变，要么是拼音声母或韵母发生改变，根据定义的拼音编辑距离可知，/Lin2/与/Ling2/的编辑距离为l，/Lin2/与/Lan2/的编辑距离也为1，但从发音机制上来说，前者的可能性更大，后者的可能很小。如果仅依据之前定义的拼音编辑距离进行计算，则会出现不合理现象。因此，本文参考并改进了曹犟等提出的基于拼音改良的编辑距离，对不同的拼音错误赋予不同的替换代价。

1.1.3 基于拼音改良的编辑距离纠错方法

根据基于拼音改良的编辑距离纠错方法定义可知，/lan2/与/nan2/的编辑距离为1，/lan2/与/pan2/的编辑距离也为l，但是/lan2/与/nan2/的发音机制更接近。因此，基于拼音改良的编辑距离方法具体计算方式如下：

（1）替换代价小于1。音调变化导致的差异小于l。不管哪种拼音输入法，都不要求用户输入音调，且音调错误比较普遍，因此本文认为其差异小于一般的声母与韵母之间的差异。在本实验中赋予0.5的替换代价。

发音相似且特别容易发生替换错误的声母与韵母之间的差异小于l。在声母或韵母发生改变的拼音错误中，其中有4对声母与5对韵母发生错误替换的可能性远大于其它的。4对声母分别为z/zh、c/ch、s/sh、l/n，5對韵母分别为ing/in、ang/an、eng/en、un/ui、ei/ai。本实验中对这9对替换错误也赋予0.5的替换代价。

在实验最后，将所有替换代价都乘以2，以得到整数结果的编辑距离，且不影响不同串之间的相似度比较。

（2）替换代价等于l。对于除上述替换代价小于l中的4对声母、5对韵母与相邻键间发生的替换错误外的其它错误，均按照上文定义的拼音编辑距离进行计算。

（3）替换代价大于l。对于同一音节，若其声母与韵母同时发生改变，则在计算编辑距离时给予一个正的惩罚值（本文实验中取值为2）。根据该规则，对于音节串P₁=A₁A₂A₃…A_n（其中A_i，i=1，2，…，n代表一个音节），如果音节A₁的声母和韵母同时发生差异为l的错误替换，得到新的音节串P₂=A₁，A₂A₃…A_n，P₂与P₁的编辑距离则需乘以一个惩罚值2，结果为4。若音节A₂与音节A₃的声母或韵母发生差异为l的错误替换，得到新的音节串P₃=A₁A₂，A₃，…A_n，则P₃与P₁的编辑距离为2。

1.1.4 拼音串查询扩展及纠错过程

设用户输入的查询串为H=S₁S₂S₃…S_i…S_n（其中S_i，i=1，2，…，n代表一个汉字），其拼音串为P：A₁A₂A₃…A_i…A_n（其中A_i，i=1，2，…，n代表一个拼音），m为错别字音节A_j的替换音节，且m≠A。，则所有因A_i发生错误而被替换的拼音串为P=A₁A₂A₃…m…A_n（其中A_i，i=1，2，…，n代表一个拼音）。由于最终返回给用户的结果不可能为所有纠正值，只需推荐TOP-K个即可，那么替换字S_i的音节m的编辑距离也不可能取所有情况，本次实验只取距离为1的音节集合。

在检索时，首先分别检索P_j1=A₁A₂A₃…A_j-1和P_j2=A_j+1A_j+2…A_n出现的位置，然后作比较，若在某个文本中，串P_j1与串P_j2同时出现，且P_j1的位置在串P_j2位置的j+1位之前，则将该文本加入候选集中，最终根据排序模型生成排序并推荐给用户。因此，最终将基于拼音的编辑距离纠错问题转化为两个查询字串的精确匹配问题。

1.2 基于模糊匹配的纠错方法

对于形似字错误和多字、少字及异位错误，目前并没有一般性的规律可循，拼音纠错方法也无法发挥作用，因此本文采用模糊匹配方法进行纠错。

定义l形似字：已知两个汉字W₁、W₂，若W₁、W₂之间的形相似度SSim（W₁，W₂）>A，则W₁与W₂互为形相似字。

本文从相似度的角度出发，通过对大规模语料的计算，得到与错误查询词相似度最高的词作为错误查询词串的替换词集合，并推荐给用户。在用户参与确认的情况下，形成正误词对，提高纠错的准确性。另一方面，建立自适应语料库，将现有语料库中不存在的新词添加到语料中，实现语料库的不断更新，以及新词的登录与纠错。

已知S=W₁W₂…W_n为当前查询串，P=C₁C₂…C_n为待匹配串，则S与P的相似度为：

在实际应用中，主要通过设置阈值判断两个词串是否匹配，若大于设置的阈值，则查询词S与待匹配串P匹配成功，并将P推荐给用户作为纠正建议，否则匹配失败。

1.3 最小編辑距离纠错方法

编辑距离又称为Leveinshtein距离，是由俄罗斯科学家Levenshtein在1965年提出的。以字符串为例，查询字符串a与匹配字符串b的编辑距离是将a转换成b的最小操作次数，这里的操作包括3种：①插人一个字符;②删除一个字符;③替换一个字符。

例如：计算忠心耿和忠心耿耿的编辑距离，操作如下：忠心耿->忠心耿耿，添加字符耿，需要做1次操作，编辑距离为l。

1.3.1 算法基本原理及步骤

s[1…n]和t[1…m]分别代表查询串与待匹配串，求串s[1…n]转换到串t[1…m]所需执行的最小操作次数，一般用动态规划方法求得。其算法一般基本步骤为：

（1）构造行数为m+l、列数为n+1的矩阵，用来保存完成某个转换需要执行的操作次数，matrix[n][m]的值即为将串S[1…n]转换到串t[1…m]需要执行的操作次数。

（2）初始化matrix第一行为0到n，第一列为0到m。Matrix[0][j]表示第l行第j-1列的值，该值表示将串s[1…0]转换为t[1…j）所需执行的操作次数，很显然将一个空串转换为一个长度为j的串，只需执行j次的增加操作即可，所以matrix[0][j]）的值应该是j，其它值依此类推。

（3）扫描每个从1到n的s[i]字符。

（4）扫描每个从1到m的s[j]字符。

（5）将串s与串t的每一个字符进行两两比较，如果相等，则定义cost为0，如果不相等，则定义cost为l。

（6）定义d[I，j]=min（d[i-1，j）+1，d[i，j-1]+1，d[i-1，j-1]+cost），其中d[i-1，j）+1表示增加操作，d[i，j-1]+1表示删除操作，d[i-1，j-1]+cost表示替换操作。

（7）扫描完成后，d[n，m]的值即为串s[1…n]转换到串t[1…m]所需执行的最小操作次数。

由上述得到动态规划公式为：

2 改进的纠错策略

2.1 纠错流程设计

通过对用户查询日志的分析总结，用户常见输入错误主要有全拼音错误、半拼音错误、音相似错误、键相邻错误、方言差异导致的错误，以及别字、多字、少字及字间颠倒导致的错误等，单一纠错方法无法对其一一进行纠正。为此，本文提出一套完整的纠错流程，首先将上述错误类型分为两大类，然后针对不同类别设计不同的纠错方法。其中全拼音、半拼音、音相似错误、键相邻错误及方言差异导致的错误均为拼音的声母、韵母或音调部分发生错误而导致的，针对该类错误，本文参考并改进了曹犟等提出的基于拼音索引的中文模糊匹配算法进行纠错;另一类为多字、少字、异位及别字引起的错误，针对该类错误，本文设计了融合模糊匹配方法与最小编辑距离的方法进行纠错。查询词串纠错流程如图l所示。

查错与纠错是文本校对中密不可分的两部分，具体步骤如下：①获取用户查询串并进行分词;②利用N-gram模型判断分词后的散串是否合理;③若为合理的串，转入步骤⑧输出查询结果，否则转入步骤④;④判断查询串是否为拼音错误，若是，转入步骤⑤，否则转入步骤⑦;⑤将错误的散串按照汉字拼音表转化为拼音串，对于多音字则需按照多音字表转化为相应的拼音串;⑥根据定义的基于拼音的编辑距离计算方式对错误的查询串按照编辑距离进行扩展，得到错误查询串的混淆集，然后对所有扩展的查询串进行精确匹配，得到查询结果后，首先作去重处理，然后按照编辑距离大小进行排序，形成候选集后，转人步骤⑧;⑦采用模糊匹配与最小编辑距离方法对别字进行纠正，并将结果放人候选集中;⑧根据排序模型对候选集进行排序，并显示给用户。

2.2 改进的拼音纠错策略

曹犟等提出的拼音纠错方法仅考虑了拼音的声母、韵母及音调变化导致的错误，而忽略了键盘输入时字母相对位置导致的错误。通过对用户网络日志错字词的研究发现，约7%的错误是由于键盘相邻键敲击错误导致的，如“考虑”与“老虑”。因此，本文在曹犟等提出的拼音纠错方法基础上进行改进，具体改进方法如下：相邻键发生替换错误的差异小于1。除上述9种易发生声母及韵母错误替换的情况外，在利用键盘输人时，由于键盘按键距离较近，很容易发生相邻键输入错误。如声母“k”与“l”相邻，因此容易输入错误，但是“k”与“p”距离较远，发生错误的概率远小于被误输为“l”的概率。因此，本文对相邻键间的差异赋予0.5的替换代价。

2.3 改进的拼音纠错步骤

对于系统判定为拼音错的查询词，先检查拼音错误，利用定义的拼音编辑距离方法进行纠错并给出纠错建议。具体步骤如下：①执行分词操作，将用户输入的查询词串切割成查询段;②将仅出现中文错误的查询段按照汉字拼音表注音成带声调的拼音串;③对于查询段中既出现单字又出现拼音串的情况，保留拼音串位置，将单字转化成拼音，并与其组合成完整的拼音串;④根据拼音编辑距离的具体方法及规则求出编辑距离最近的拼音集合;⑤根据拼音串的查询扩展方法求出步骤④中拼音集合的候选集;⑥将得到的拼音候选集进行音字转换，形成汉字候选集;⑦根据相关排序模型对候选集进行打分，根据分数高低将纠错建议返回给用户。

3 实验结果与分析

3.1数据集选取

实验数据来源于搜狗实验室提供的日志文件，其格式包括时间、用户ID、查询词、返回结果排名、用户点击序号、页面URL等。具体格式如表1所示。

由表1可知，网络日志中包含较多信息，由于本文实验只涉及到其中的查询词部分，因此首先挑选出连续3天的查詢日志数据，使用MapReduce脚本提取其中的查询词串，然后对提取的查询词串进行去噪、去重、去敏感词等处理后，形成共约260万条有效的查询数据。

本文从260万条有效查询数据中随机抽取40万条连续记录，对其进行编号并根据拼音表注音形成查询文件记录。查询文件结构如表2所示。

本文使用的词典共收录词组约9万条，每个词语都有相应的拼音注音，且3字以上的词语标注拼音缩写。词典结构如表3所示。

在词典中新增两列信息，分别为查询词频与日志中出现次数，形成语料库文件，本次实验共形成语料90753条。语料库结构如表4所示。

3.2 实验过程及结果分析

测试集由搜狗实验室提供用户日志中的查询词串及人工添加数据组成。首先从查询日志中选取常用且出现在语料库中的查询词作为测试集的一部分;其次，由于查询中某些错误类型数量非常少，本文通过人工添加的方式加以补充;最后利用选取的测试数据根据上述纠错流程进行实验，获得错误查询串的纠正串，如图2所示。

在不同规模的测试集下，准确率和召回率也不同，本文共选取6组不同规模的测试集，大小分别为10K、30K、50K、70K、90K、110K，纠错结果如图3所示。

从图3可以看出，本文提出的搜索引擎中文纠错方法的准确率和召回率都较高，因此该方法可以有效纠正用户在进行搜索引擎查询时不小心输入错误查询词的问题，并根据用户搜索意图返回正确的搜索结果。

将本文改进的方法与仅使用拼音编辑距离纠错及模糊匹配的方法进行比较，实验结果如图4所示。

之后将本文改进的方法与仅使用单一统计方法进行比较。如陈智鹏等提出的完全通过分析上下文统计信息的方法，根据中文语言特点，在对大规模中文语料库建立N-gram模型的基础上，通过计算TF/DF权重的方式获得最优纠错结果，实现对搜索引擎中关键词的自动查错与纠错。实验结果如图5所示。

从实验结果可以得到以下结论：

（1）测试集大小直接影响实验的准确率和召回率，本文提出的纠错方法在测试集为110K时，准确率和召回率均达到最高。

（2）通过图4实验可知，本文针对第二类错误使用模糊匹配结合最小编辑距离的方法，能够弥补单独使用模糊匹配方法无法解决字间颠倒问题的缺陷，能更有效地纠正由于多字、少字、异位及别字引起的错误。

（3）通过图3与图5对比可知，本文提出的纠错方法相比基于N-gram模型的纠错方法，在测试集达到110K时准确率提高了4.8%。

4 结语

本文提出基于搜索引擎日志的纠错方法，该方法首先对日志进行分析与分类，总结出不同错误类型，并基于此提出纠错方案。针对因输入法导致的拼音错误，本文参考并改进曹犟等提出的基于拼音改良的编辑方法进行纠错;针对多字、少字、异位及别字引起的错误，本文使用模糊匹配结合最小编辑距离方法进行纠错。通过实验，本文方法在实际中具有一定可行性，一定程度上提升了用户满意度。但该方法还存在一定不足，例如对新的网络流行语会出现误判等。后期将会考虑实时更新常见的流行语等，以进一步提升纠错方法的准确性。