大观数据搜索引擎自动纠错技术及架构

1 背景

如今，搜索引擎是人们获取信息的重要途径之一。在搜索页面小小的输入框里，你只需要输入几个关键词，就能找到关于你感兴趣的问题的相关网页。搜索巨头甚至把这个造词做成了动词，你有什么问题，直接点击就可以了。在中国，百度也成了动词。除了一般的搜索需求，很多垂直细分领域也有很强的搜索需求，比如电商网站的商品搜索、文学网站的小说搜索等。针对这些需求，大观数据（）作为国内提供中文云搜索服务的高科技公司，为合作伙伴提供优质的搜索技术服务，并对搜索服务进行统计分析等功能。（大观数据联合创始人 高翔）

搜索引擎系统最基本、最核心的功能是信息检索，找到包含关键词的网页或文档，然后按照一定的顺序给出结果。在此基础上，搜索引擎可以提供更复杂的功能来增强用户体验。对于成熟的搜索引擎系统来说，用户看似简单的搜索过程需要经过系统中的多个环节，多个模块共同协作才能提供令人满意的搜索结果。其中，拼写纠正（简称 EC）是用户很容易感知的功能。例如，百度的纠错功能如下图所示：

图1：百度纠错功能示例

EC其实是（以下简称QR）模块中的一个功能，QR模块包含了拼写纠正、同义词改写、联想等功能，QR模块对于提升用户体验有很大的帮助，可以对搜索质量差的词进行改写后返回更好的搜索结果。QR模块的内容比较多，下面重点讲解EC功能。

在搜索引擎中，我们将用户输入的关键字查询称为“搜索结果”。用户希望得到与其输入相关的高质量网页或文档。衡量“好”的定义有很多种，最简单的标准就是对用户最有帮助、最有吸引力的结果能够排在最前面。搜索工程师也在努力通过改进各种算法来实现这一目标。然而，由于种种原因，用户输入的质量往往较低或有误。如果搜索引擎不纠正这种错误，就会导致召回错误的结果，或者结果数量很少甚至没有结果。

当用户看到搜索结果差、少的时候，如果能意识到自己的错误，改正过来重新搜索，或许就能找到想要的结果。但有时用户也不知道自己错在哪儿，这时候就会很焦虑。我以前从事搜索相关工作的时候，搜索系统一开始是不支持纠错功能的，结果就收到了很多用户的投诉和抱怨，表示没有纠错功能的搜索系统会大大降低用户体验。不仅如此，这些错误的搜索还浪费了很多流量。在开发完成，并在搜索系统中使用EC模块之后，成功纠错的流量占到了总流量的2%，不仅提升了用户体验，还挽回了流量流失，增加了用户粘性。

2 个常见的电子商务错误

EC该怎么办？首先我们来看看常见的错误。

对于英语来说，最基本的语义元素就是单词，因此拼写错误主要有两种类型。一种是 Non-word，即单词本身拼写错误，例如“”被拼写成“”，“”本身不是一个单词。另一种是 Real-word，即单词拼写正确，但在上下文中是错误的，例如“two eyes”被写成“too eyes”，“too”在这里是一个明显的拼写错误。

对于中文来说，最小的语义单位是字，错别字经常不会发生，因为现在几乎每个汉字都是通过输入法输入的，不像手写的汉字，可能会错。汉字虽然可以组成词，但是由两个或多个汉字组成的词是更常见的语义元素。这种组合带来了类似英文的非词。例如“洗衣机”写成“洗一只鸡”，虽然每个字都是正确的，但整体不是一个词，这就是所谓的错字。中文字符也存在类似现实单词的问题。例如“加薪圣旨”，“加薪”和“圣旨”都是正确的单词，但是当两者连接在一起时就会出现问题。因此，很多时候中文纠错其实是短语纠错问题。除了纯汉字，现在还有中英文混合拼写错误、汉语拼音混合拼写错误等错误。以下图片是笔者在搜索日志中发现的一些常见错误：

图 2：搜索错误日志

从上图可以看出，中文搜索常见的错误主要有拼写错误、纯拼音、发音歧义、拼音与汉字混合、拼音与其他符号混合等等问题。

3.错误原因分析

目前，输入中文最常见的方式是拼音输入法。用户输入拼音，输入法给出候选词。然而，当用户误选或不需要候选词时，可能会出现错误。虽然现在的智能输入法比以前足够强大，但仍然有一些新产品、小说、影视作品是输入法可能无法覆盖的。例如，随着一些新颖的网络词汇的出现，传统词典已经无法收录这些词。还有一些相对陌生的词，比如《芈月传》，很多人听朋友说很好看，但到搜索引擎上搜索相关信息时，很多人只知道第一个字读作“芈”，却不确定到底是哪个字。

此外，用户在搜索时可能会从网页或其他文档中复制粘贴文本，导致搜索不完整或包含其他字符，甚至打字速度过快也会导致输入错误。

4 纠错解决方案

英语拼写纠错历史悠久，关于英语纠错的研究也很多。英语纠错是中文纠错的重要基础，很多算法思想也适用于中文。因此我们先来介绍一下英语纠错​​问题。在介绍具体的纠错方案之前，我们先介绍两个重要的概念：编辑距离和n-gram模型。

4.1 基本概念

4.1.1 编辑距离

编辑距离是将一个字符串转换为另一个字符串所需的最少操作次数，允许的操作包括字符替换、添加字符、删除字符和反转字符。例如 和 的编辑距离为 1， 和 的编辑距离为 2， 和 的编辑距离为 3。编辑距离的计算过程如下图所示：

图3：编辑距离计算过程

4.1.2 n-gram模型

语言模型广泛应用于语音识别、机器翻译、中文自动分词、基于统计模型的句法分析等，目前主要使用的模型是n-gram模型。

语言模型构建了字符串的概率分布p(W)，设p(W)为某个字符串是句子的概率，该概率计算公式如下：

公式 1：语言模型

其中 w1 代表第一个单词，w2 代表第二个单词，依此类推。p(w4|) 表示当前三个单词是 w4 时，第四个单词是 w4 的概率。

w1w2...wi-1 称为历史。假设 w 一共有 5000 个不同的词，那么当 i=3 时，就有 1250 亿种组合。但是训练数据或者已有的语料数据不可能有这么多的组合，而且大多数组合都不会出现。因此，w1w2...wi-1 可以按照规则映射到等价类中。最简单的做法就是取 wi 之前的 n-1 个历史。根据马尔可夫假设，一个词只和它之前的 n-1 个词有最高的相关性。这就是 n-gram 语法模型。

公式2：n-gram模型

常用的n-gram模型有，，，其中这个词和前一个词无关，相互独立，计算公式如下：

公式3：语法模型

表示一个词只和它前面的词相关，计算公式如下：

公式4：语法模型

4.2 英文错误修正

4.2.1 非词语错误纠正

纠错首先要发现错误，发现错误的方法有很多种，对于非单词错误，可以使用语料库词典，如果输入的单词不在词典中，则可以判定为错误单词。

纠错的过程就是找出一些和错误词最相似的候选词，然后选取正确的词进行纠正。利用上面介绍的编辑距离，可以从语料库中找到候选词。统计显示，80% 的错误词的编辑距离为 1，几乎所有的错误编辑距离都在 2 以内。

在候选词中寻找最终的校正词，一种比较简单的方法是将候选词按照权重进行排序，将权重最高的词作为校正词。这个权重可以是人工标注的结果，也可以是语料统计的词频或其他方法。相对复杂的候选词选取方法可以使用统计模型来计算，例如噪声通道模型。

噪声信道模型（ ）最早由香农基于信息熵的概念提出，用于对信道的通信问题进行建模。其目标是优化噪声信道中信号传输的吞吐量和准确率。对于自然语言处理，信道噪声模型如下图所示，其中 I 表示输入，O 表示经过噪声信道后的输出，I' 表示解码后最可能的输入。

图4：通道噪声模型框图

在自然语言处理中，许多问题可以归结为在给定输出 O（可能包含错误消息）的所有可能输入 I 中找到最可能的输入 I'。

通道噪声模型可以用于解决自然语言处理中的很多问题，比如机器翻译、词性标注、语音识别等，通道噪声模型也可以用于解决纠错问题，其对应的解可以用公式表示：

公式5：噪声信道模型误差修正公式

其中，p(x|w)为正确词被编辑成错误词x的转移概率，包括删除()、添加()、替换()、反转()四个转移矩阵。这个转移矩阵的概率可以通过统计大量的正确词和错误词对来得到。转移矩阵的计算公式如下：

公式6：传递矩阵公式计算

将转移矩阵计算公式代入公式5的噪声信道模型公式，根据不同候选词与纠错词之间的变换关系选择转移矩阵类型，即可得到概率最大的候选词。

4.2.2 实词纠错：

有研究报告指出，40%~45%的错误属于Real-word问题。在Real-word问题中百度搜索自动出来的词条怎么删除，每个单词都是正确的，但是组合成短语或句子时意思就是错误的。因此纠错策略与Non-word有些不同。首先是候选词集的生成。对于句子或短语中的每个单词，都会生成一个候选集。这个集合包括：1.单词本身；2.与这个单词编辑距离为1的所有单词；3.同音词。在集合选定之后，可以用来选取最佳候选或组合的方法包括噪声通道模型和特殊的分类器。

噪声通道模型与无词纠错类似，只是计算目标由某个候选词的概率最大值变为了由不同位置的候选词组合而成的句子概率最大值p(s)，这个问题可以用HMM（隐马尔可夫模型）来解决。

图 5：噪声信道模型中纠错的实际问题

上图中，每一个序列都是这个位置上的单词的候选词集合，其中，每个单词的状态转移概率可以通过对语料库中的语言模型进行统计得到。

基于分类方法纠错，分类器会根据多个特征，训练出一对Real-之间的迁移模型。常见的分类器有SVM（支持向量机）或者基于规则的分类器。特征可以为每个词选取，概率等。

4.3 中文纠错

中文纠错以英文纠错为基础但又有所不同。中文中错字和正确字的长度一般相同，但在指定位置的某个字符有错误，因此状态转移矩阵只有一次替换。其次，中文词语往往较短，即使编辑距离只有1，也会有大量的候选词，逃逸风险较大。中文以拼音作为文字的读音，每个词都有固定的读音（多音字除外），而拼音输入法在中文输入法中占有主导地位，导致出现字音同音但字形不正确的错误。因此中文纠错以拼音为主，辅以编辑距离等其他方法。

4.3.1 获取候选词集

对于错别字候选词集，可以通过数据自动挖掘的方式生成。英文候选词集一般通过编辑距离得到，中文候选词集则由与错别字拼音相同的单词组成。例如错别字“大易”的拼音为“dayi”，可以由预先挖掘出的拼音为“dayi”的单词组成候选集。

4.3.2 候选词的选择

纠错候选词的选取就是对候选词进行排序，按照一定的排序规则返回排序最高的候选词作为最佳纠错结果。排序规则可以使用词频等多种特征，按照这些特征规则对候选词进行排序，返回权重较高的词。

在没有上下文的情况下对单词进行纠错时，候选词的选取比较困难。例如上面的错别字“妲衣”就有很多候选词，无论用哪种方法进行排序，都存在严重的逃逸风险。此时可以采用编辑距离等其他方法来辅助选取。

相比单个单词，多个单词组成的纠错相对准确率更高，每个单词都有上下文约束，整体意图更明确，通过分词找到每个单词的候选词集，然后进行纠错，类似英文实词纠错。

除了对搜索日志和语料进行统计挖掘之外，搜索系统中的分析和点击模型提供的数据还可以起到纠错服务的作用。搜索是指用户在一定时间段内的搜索行为。如果将搜索日志按照时间排序，对于某个用户的搜索日志，可以看到用户的搜索行为是分段的，而各个分段之间往往存在比较明显的间隔，我们称每个分段为一次搜索。一般来说，用户在一段时间内的搜索行为都是为了解决某个问题，因此用户在这段时间内的输入往往是相关的。

点击模型中的一些统计数据可以决定搜索的质量。高质量的结果往往能给出更好的结果，用户点击的可能性也更大。例如，在“”（正确）和“”（错误）之间，如果用户输入了较多错误的“”，系统就会给出较差的结果。在下面的例子中，“”的所有搜索结果都没有命中标题，而标题往往是用户最关注的信息。如果标题不包含搜索关键词，用户点击的可能性就会更小。

图 6：错误“休假”的结果很少，质量较差

图 7：有很多正确的“度假”结果，质量很好

这种情况下，“”虽然搜索量较大，但是点击模型给出的评分会比较低，而候选词“”的评分会比较高，可以辅助其他纠错方法完成纠错。

4.4 问题

搜索系统很多功能的召回率和准确率是矛盾的，但在纠错问题上，往往要求准确率更高。拼音到汉字的纠错往往有较大的逃逸风险。不同类型的拼音转换方式（全拼、模糊全拼、简化拼音、混合拼音）都有不同程度的逃逸风险。召回率越大，准确率越低，所以使用全拼更安全。（大观数据联合创始人 高翔）

5. 大观数据搜索系统纠错技术介绍

大观数据在搜索引擎等大数据技术方面有着深厚的经验，搜索引擎提供了多种功能和服务，其中纠错模块是比较重要的功能之一。

5.1 错误纠正过程

对于搜索中的纠错功能来说，纠错过程主要分为以下三个过程：

1. 纠错判断。对于常见的错误，比如常见的拼写错误，使用提前挖掘出来的错误词典，当错误在词典中时进行纠正。如果用户输入的查询没有结果或者结果小于某个阈值，则尝试纠正错误。可以根据不同字段的策略和容忍度配置最小结果数阈值。

2. 自主纠错策略不同。大观数据采用多种纠错策略，主要以拼音纠错和编辑距离纠错为主，并辅以模糊拼音、形态相似字等其他纠错策略。同音字策略是用户输入的错误和候选纠错的拼音相同。编辑距离策略是错误和候选的编辑距离小于一定阈值，结合其他条件进行筛选。

3.候选词的选取。由于各个策略相对独立，不同的策略会给出不同的候选词，因此各个策略对候选词的选取也不同。不同策略之间、不同策略内需要采用不同的评价方法来选取最优结果。

达观科技搜索系统的纠错模块包含了上述的多个策略，各个策略独立运行，针对不同领域、不同业务情况，策略优先级、权重可配置，并可调整纠错的松紧程度。

5.2 系统设计

大观数据EC系统主要分为数据模块、离线建库端、在线检索端三部分。

图8：EC系统模块组成

5.2.1 数据模块

数据模块的主要作用是为后续的离线建库和在线检索提供数据。

数据模块定期对搜索日志进行抽取、统计，并对搜索日志进行归一化处理，得到频数词典；对数据库信息进行整理，得到自定义词典；通过爬虫系统爬取高质量的词条词典。

5.2.2 离线数据库构建

离线建库端利用数据模块准备好的各种词典生成纠错词典，包括拼音纠错词典、编辑距离纠错词典等。根据配置，对于超过一定长度的频率词典，不进行上述操作处理。

5.2.3 在线搜索终端

在线检索端负责实时纠错，按照5.1节的三个步骤进行，若第一次纠错查询结果较差，则采用扩大召回的方法，如二次纠错、片段纠错等，扩大召回率重新纠正错误，进行二次查询，返回更高质量的查询结果。

5.3 误差修正效果评估

从微观角度看，可以通过检查搜索日志中无结果或少结果的纠错情况和点击模型中点击次数少的纠错情况来判断纠错的有效性，发现不良案例，然后对这些不良案例的原因进行归类和总结，并在后期对算法进行改进。

宏观上，可以重点关注搜索性能评估体系中的MAP和MRR评分，通过AB测试查看使用纠错模块或者升级纠错算法后的性能提升情况。

6 结论

在一个完整的搜索引擎体系中，纠错是重要的一环，对提升用户体验和用户满意度有很大帮助，也能弥补大量错误带来的流量流失。大观数据在搜索引擎服务方面拥有丰富的行业经验，可以为合作企业提供优质的搜索服务，充分挖掘企业的数据价值。（大观数据联合创始人 高翔）

科技就像满天的星光，指引我们前行。（题图为作者在库克山拍摄）