基于错误模式挖掘的中文搜索引擎查询纠错方法及系统

摘要

本发明提供一种基于错误模式挖掘的中文搜索引擎查询纠错方法。该方法通过挖掘搜索引擎查询日志中的错误模式并建模，有效的改善了查询纠错系统中查询及其正确形式之间转换概率的预估精度；利用隐马尔科夫模型进行查询纠错，通过隐含状态的转移实现对查询的切分和纠错，提高了查询纠错的准确率和速度。

说明书

技术领域

本发明涉及自然语言处理，尤其涉及中文搜索引擎查询纠错方法。

背景技术

在过去的十年里，网络信息量一直呈几何级数式速度增长，搜索引擎 已经成为了人们从大量的网页中获取有用信息的主要途径之一。据CNNIC 发布的《第30次中国互联网络发展状况统计报告》中统计，截至2012年 6月底，中国搜索引擎用户规模达到4.29亿，在网民中渗透率为79.7%， 较2011年底增长2121万人，半年增长率为5.2%。

现有的搜索引擎使用模式中，用户主要以输入关键词的方式来获取包 含该关键词的网页信息。据文献统计，英文搜索引擎的查询中有10%～15% 含有拼写错误；据对某中文搜索引擎查询日志的统计，查询中存在同音别 字、近音别字、拼音、英文拼写等多种错误。在不对查询词进行纠错处理 的情况下，搜索引擎的关键字匹配技术对于用户输入的错误查询词，一般 很难获取到用户所需的信息。搜索引擎查询纠错技术主要用于分析用户输 入的查询词中包含的错误，并对查询词中的错误进行纠正返回正确结果。 查询纠错技术对于改善用户的搜索体验，有着十分重要的作用，已被广泛 应用于百度、Google、Bing等各大搜索引擎中。常见的英文拼写错误包括 单词错误（在词典中找不到该单词）和上下文错误（将一个单词输成为另 一个单词，不符合当前上下文语境的需要）。查询纠错实际上就是首先判 断查询的拼写正确性，然后对于错误的查询给出其正确形式的过程。

常用的英文查询纠错方法包括：基于噪声信道模型的查询纠错方法和 基于隐马尔科夫模型的查询纠错方法。在基于噪声信道模型的查询纠错方 法（参见参考文献1和2）中，基于正确的词典，为查询中的每个词条生 成候选词集合，利用噪声信道模型计算出在给定的查询条件下候选词条出 现的概率，然后综合考虑编辑距离和语言模型挑选出最优的候选词条组 合。在基于隐马尔科夫模型的查询纠错方法（可参见参考文献3）中，将 查询中的字符看作观察状态，而该查询的所有可能的正确形式看作隐含状 态，并利用状态之间的切换进行纠错，选出与该查询对应的最优隐含状态。 在上述方法中，往往采用粗粒度的编辑距离估计查询及其正确形式之间的 转换概率，这造成了概率预估精度不准并且候选词条过多等问题。

此外，在上述的英文查询纠错技术中，英文单词之间有空格作为天然 的分隔符，并且英文查询中往往仅包含英文字母及标点，故而在采用噪声 信道模型或隐马尔科夫模型时，仅需考虑获取和查询中词条在一定编辑距 离范围以内的候选词条即可。然而在中文查询纠错技术中，用户输入的查 询中往往并不存在词条之间的分隔符，且错误的查询中可能包含的有汉 字、拼音和英文。目前的中文查询纠错方法，往往采用模糊音匹配的方法， 将中文查询词转换为其模糊音，并通过模糊音匹配找到与其相近的候选， 并输出正确集合中存在的候选词。这种方法无法处理正确集合以外的中文 查询错误，也无法处理中英文、拼音和中文共存的情况。而实际上在中文 搜索引擎中，汉字的查询错误类型有多种，例如同音别字、近音别字、形 近别字、汉字误写为拼音、前后字位置颠倒、多字漏字等。当汉字误写为 拼音时，也可能发生英文错误类型中所包含的字母缺失、字母写错、字母 多余、缺少空格、前后字位置颠倒等错误。可见，上述的英文查询纠错方 法以及基于模糊音匹配的中文查询纠错方法难以满足中文查询纠错的实 际需求。

上述参考文献列表如下：

参考文献1：M.Kernighan,K.Church and W.Gale.A spelling correction program  based on a noisy channel model.In Proceeding of COLING1990,pages205-210,1990.

参考文献2：S.Cucerzan and E.Brill.Spelling correction as an iterative process  that exploits the collective knowledge of web users.In Proceedings of the2004Conference  on Empirical Methods in Natural Language Processing,pages293-300,2004.

参考文献3：P.Taylor.Hidden Markov models for grapheme to phoneme  conversion.Procs INTERSPEECH,2005.

发明内容

因此，本发明的目的在于克服上述现有技术的缺陷，提出了一种基于 错误模式挖掘的中文搜索引擎查询纠错方法。

本发明的目的是通过以下技术方案实现的：

一方面，根据本发明的一个实施例中提供了一种中文搜索引擎查询纠 错方法，包括：

步骤1，基于搜索引擎查询日志挖掘错误查询及其正确形式的查询对， 建立错误模型；所述错误模型是基于对错误模式发生的概率统计而建立 的，所述错误模式发生的概率反映的是将某种正确形式写为某种错误形式 的可能性的大小；

步骤2，基于搜索引擎查询日志构建语言模型；

步骤3，以用户输入的查询作为隐马尔科夫模型的观察状态序列，基 于所建立的错误模型产生可能的隐含状态并计算发射概率，基于所建立的 语言模型计算初始状态概率和隐含状态转换概率，以及基于隐马尔科夫模 型获取该查询对应的最优隐含状态序列，将其作为该查询对应的正确形 式。

上述方法中，所述步骤1可包括：

步骤11，基于查询日志挖掘错误查询及其正确形式的查询对(Q,C)；

步骤12，从所述查询对(Q,C)的对应错误分段(q₁q₂q₃...q_m,c₁c₂c₃...c_m)获取错 误模式(e₁e₂e₂...e_m)，其中e_i对应错误模式c_i→q_i，该错误模式代表将正确形式 c_i写成错误形式q_i的情况；

步骤13，通过统计的方式建立n_e元错误模型，其中，在错误模式 (e₁e₂e₂...e_m)中e_i发生的概率仅取决于其前n_e-1个错误模式

$P\left(e_i\right|e_1{e}_2{e}_3...e_{i-1})=P\left(e_i\right|e_{i-n_e+1}{e}_{i-n_e+2}...e_{i-1}).$

上述方法中，所述步骤11可包括基于搜索引擎查询日志中执行下列 步骤：

a)用户搜索查询Q时，点击了纠错推荐C，该(Q,C)对即为错误 查询及其正确形式的查询对；

b)用户搜索查询Q时，其点击链接的标题、摘要中包含查询Q的 纠错形式C，该(Q,C)对即为错误查询及其正确形式的查询对；

c)用户搜索查询Q时，其点击链接的标题、摘要中未包含Q的 所有分词结果，而包含了与Q编辑距离相近的字段C，当(Q,C)之间 的编辑距离小于一定阈值时，将其作为错误查询及其正确形式的查 询对处理；和/或

d)用户搜索查询Q后无点击行为，而在同一会话中的其他查询 C产生点击行为，当(Q,C)之间的编辑距离小于一定阈值时，将其作 为错误查询及其正确形式的查询对处理。

上述方法中，所述步骤11还可包括：对查询Q进行编辑，其中对于英 文字母的编辑方式有匹配、替换、插入、删除、前后字交换、拼音转汉字 等，对于中文字的编辑方式有匹配、同音字替换、近音字替换、形近字替 换、前后字交换、尾字补全等，采用动态规划算法获得由查询Q到其正确 形式C编辑距离最小的编辑方式，从而进一步挖掘更多的错误模式 (c₁→q₁,c₂→q₂,c₃→q₃,...,c_m→q_m)。

上述方法中，所述步骤13）中n_e为2，错误模式e_i发生的概率为：错 误模式e_i-1与e_i在所获取的错误模式中连续出现的次数和错误模式e_i-1与任 一错误模式在所获取的错误模式中连续出现的次数的比值。

上述方法中，所述步骤3可包括：

步骤31）以用户输入的查询作为隐马尔科夫模型的观察状态序列 O₁O₂O₃...O_m，利用所述语言模型计算隐马尔科夫模型的初始状态概率；

步骤32）利用错误模型产生可能的隐含状态，并计算隐马尔科夫模型 的发射概率；

步骤33）利用语言模型计算隐马尔科夫模型的隐含状态转换概率；

步骤34）基于上述的观察状态序列，初始状态概率、可能的隐含状态、 隐含状态转换概率、发射概率，利用隐马尔科夫模型获取该查询对应的最 优隐含状态序列。

上述方法中，所述步骤31）中，所述初始状态概率为观察状态O₁对 应的隐含状态S₁的概率分布π={π_i}，

${\pi }_i=P(S_1=s_1^i),1\le i\le N$

π_i≥0

$\underset{i=1}{\overset{N}{\Sigma }}{\pi }_i=1$

其中，隐含状态S₁代表观察状态O₁对应的正确形式，S₁可有N个值， 代表隐含状态S₁取第i个值的概率，其为在搜索引擎查询日 志中出现在首位的次数与在搜索引擎查询日志中出现的次数的比值。

上述方法中，所述步骤32）可包括：

对于给定的观察状态序列O₁O₂O₃...O_m，所述隐含状态序列S₁S₂S₃...S_m中某 一状态S_i的取值取决于观察状态O_i所对应的错误模式的发生概率，将其发 生概率大于某一阈值的每个错误模式中的正确形式作为观察状态O_i的可 能的隐含状态，并且将该错误模式的发生概率作为隐马尔科夫模型中的发 射概率，其代表将该隐含状态错写成观察状态O_i的概率，其中1<i<=m。

上述方法中，所述步骤33）可包括：

对于某一隐含状态序列S₁S₂S₃...S_m，利用所建立的语言模型计算其中某 一个状态S_i发生概率如下：

$P(S_i=s_i|S_{i-n_l+1}{S}_{i-n_l+2}...S_{i-1})=P\left(s_i\right|s_{i-n_l+1}{s}_{i-n_l+2}...s_{i-1}),$其中n_l为所建立的语言模型 的阶数；将该概率作为隐含状态转换概率。

又一方面，根据本发明的又一个实施例中提供了一种中文搜索引擎查 询纠错系统，包括：

错误模型装置，基于搜索引擎查询日志挖掘错误查询及其正确形式的 查询对，建立错误模型；所述错误模型是基于对错误模式发生的概率统计 而建立的，所述错误模式发生的概率反映的是将某种正确形式写为某种错 误形式的可能性的大小；

语言模型装置，基于搜索引擎查询日志构建语言模型；

隐马尔科夫模型装置，以用户输入的查询作为隐马尔科夫模型的观察 状态序列，基于所建立的错误模型产生可能的隐含状态并计算发射概率， 基于所建立的语言模型计算初始状态概率和隐含状态转换概率，以及基于 隐马尔科夫模型获取该查询对应的最优隐含状态序列，将其作为该查询对 应的正确形式。

又一方面，本发明还提供一种中文搜索引擎检索方法，所述方法包括：

接收用户输入的查询；

利用上述的查询纠错方法，获取该查询对应的正确形式；

以所获得的正确形式进行检索并将检索结果返回给用户。

又一方面，本发明还提供一种中文搜索引擎，其包括上述的查询纠错 系统。

与现有技术相比，本发明的优点在于：

1.针对中文搜索引擎查询中包含多种不同的错误模式，通过挖掘搜索 引擎查询日志中的多种错误模式并建模，有效的改善了查询纠错中查询及 其正确形式之间转换概率的预估精度。

2.采用隐马尔科夫模型实现中文查询纠错，并利用隐含状态的转移实 现对查询的切分和纠错，能够处理中文查询中包含有汉字、拼音和英文等 情况。

3.在给定隐马尔科夫模型的初始概率、状态转移概率、发射概率的情 况下，采用剪枝的维特比算法计算最优的隐含状态序列，提高了查询纠错 的准确率和速度。

附图说明

以下参照附图对本发明实施例作进一步说明，其中：

图1为根据本发明实施例的中文搜索引擎查询纠错方法的流程示意 图；

图2为根据本发明实施例的剪枝的维特比算法流程示意图；

图3为给定观察状态序列到达某一隐含状态的可能路径示意图。

具体实施方式

为了使本发明的目的，技术方案及优点更加清楚明白，以下结合附图 通过具体实施例对本发明进一步详细说明。应当理解，此处所描述的具体 实施例仅仅用以解释本发明，并不用于限定本发明。

为了更好地理解本发明，首先对马尔科夫模型、隐马尔科夫模型以及 基于隐马尔科夫模型的查询纠错方法、N-gram语言模型的基本原理进行简 单的示意性介绍。

1.N阶马尔科夫模型

对于给定一个随机变量序列S₁，S₂，S₃…，其中St的取值仅由S_t-N, S_t-N+1,…,S_t-1决定，即：P(S_t=s|S₁=s₁,S₂=s₂… S_t-1=s_t-1)=P(S_t=s|S_t-N=s_t-NS_t-N+1=s_t-N+1...S_t-1=s_t-1)，简单来说，就是现在的状态 只取决于该状态之前的N个状态。

而对于一个状态转换序列而言，P(s₁s₂…s_T)=P(s₁)P(s₂|s₁)…P(s_T|s_T-Ns_T-N+1...s_T-1)。

但是，有时状态转换序列s₁s₂…s_T并不能直接得到，而采用隐马尔科 夫模型，可通过观察数据来发现隐藏在观察数据之后的状态转换序列。以 语音识别为例，当观察到语音信号o₁,o₂,o₃时，根据这组语音信号推测源 端发送的句子s₁s₂s₃，也就是在所有可能的句子中找出概率最大的。即在 已知o₁,o₂,o₃,...的情况下，求使得条件概率P(s₁,s₂,s₃,...|o₁,o₂,o₃...)达到最 大值的那个句子s₁,s₂,s₃...。对于自动纠错，就是要根据带有拼写错误的语 句推测该语句想表达的正确意思。

2.隐马尔科夫模型（Hidden Markov Model，HMM）

假设给定观察序列o₁,o₂…o_t，隐藏在观察数据之后的状态转换序列为 s₁，s₂，…s_t，其中，s_t只依赖于s_t-1，o_t只依赖于s_t，该隐马尔科夫模型中 的马尔可夫链为一阶马尔可夫链。

则可得联合概率（对于给定的观察序列o₁,o₂…o_t，其隐含状态序列为 s₁s₂…s_t的概率）为：

使得概率P(o₁o₂…o_ts₂…s_t)最大的s₁s₂…s_t即为观察序列o₁,o₂…o_t对应 的最优隐含状态序列。

其中，隐马尔科夫的参数为

初始状态概率(π_s1)：π_k=P(S₁=k)k=1,2,…M，π_k表示初始状态S₁初始取值为k的概率；

隐含状态转换概率a_k,l=P(s_t+1=l|S_t=k)，k,l=1,2,…M，a_k,l表示 当S_t取值为k时S_t+1取值为l的概率；

发射概率b_k(u)=p(o_t=u|s_t=k)u=1,2,…N,k=1,2,…,M,b_k(u)表 示当S_t取值为k时o_t取值为u的概率；其中N和M是给定的。

从上述公式可以看出，对于某个观察状态o_i，其对应的某个隐含状态 s_i发生的概率实际上为从s_i到o_i的发射概率（即将s_i错写成o_i的概率）与 从s_i-1到s_i的状态转换概率的乘积。发生概率最大的隐含状态即为该观察 状态o_i最有可能的正确形式，可用于对o_i进行纠错。

3.基于隐马尔科夫模型的查询纠错

基于隐马尔科夫模型的查询纠错实际上就是利用隐马尔科夫模型为 用户查询寻找其最有可能的正确形式。在基于隐马尔科夫模型的查询纠错 中，观察状态序列为用户查询，如假设用户输入的查询为“不不惊心”； 观察状态o_i为用户查询中的第i个字，例如“不不惊心”中的“不”；隐含 状态S_i为观察状态o_i对应的任一可能的正确形式，例如“步”、“不”、“部”、 “布”等；隐含状态序列表示对用户查询的任一可能的纠错结果（也可以 理解为用户查询的任一候选正确形式），例如“步步惊心”、“不不精心”“步 步精心”“布布惊心”等。

其中，需要确定的隐马尔科夫模型的参数：

初始状态概率，例如，S₁初始取值“步”的概率，S₁初始取值“不” 的概率，S₁初始取值“部”的概率等。

隐含转换状态概率，例如，当S₁取值为“步”时，S₂取值为“步”的 概率；当S₁取值为“步”时，S₂取值为“不”的概率；当S₁取值为“步” 时，S₂取值为“部”的概率；当S₃取值为“惊”时，S₄取值为“心”的概 率；当S₃取值为“惊”时，S₄取值为“新”的概率，等等。在下面介绍的 本发明的实施例中，将利用语言模型来计算转换状态概率。

发射概率，例如“步”被错写成“不”的概率，“部”被错写成“不” 的概率，“布”被错写成“不”的概率。实际上表示某一隐含状态被错写 成观察状态的概率。

4.N-gram语言模型

语言模型构建的是字符串s的概率分布P(s)，其反映的是当字符串s 作为句子出现时出现的概率。通常二元语言模型（bi-gram）可以看作每个 单词只有一个状态的马尔科夫链，即通过观察前一个单词推知后一个单 词。三元语言模型（tri-gram）可看作每个单词有两个状态的马尔科夫链， 即通过观察前两个单词推知后一个单词，依次可推广到N元语言模型。其 中，三元语言模型又称作二阶马尔科夫模型，N元语言模型又叫N-1阶马 尔科夫模型。对于Bi-gram模型，s为w₁w₂…w_n，P(s)可以表示为：

$p\left(s\right)=p(w_1,w_2···w_n)=p\left(w_1\right)\underset{k=2}{\overset{n}{\Pi }}p\left(w_k\right|w_{k-1}),$可以通过对训练文本中连续词语 w_k-1w_k出现的统计来估计该概率，例如

其中，count(w_k-1w_k)表示连续词语对w_k-1w_k在训练文本中出现的次数， M为训练文本中单词的总数。

从上文介绍可以看出，基于隐马尔科夫模型的查询纠错中主要是确定 初始状态概率、隐含状态转换概率、发射概率等参数，以及在确定参数后， 利用隐马尔科夫模型寻找给定的观察状态序列对应的最优隐含状态序列， 即估计出用户查询对应的正确形式。其中隐马尔科夫模型各参数的估计方 法和预估精度会直接影响查询纠错的准确率和速度。

图1给出了根据本发明一个实施例的基于错误模式挖掘的中文搜索引 擎查询纠错方法。该方法包括步骤1基于搜索引擎查询日志挖掘错误查询 及其正确形式的查询对，建立错误模型（即估计不同错误模式的发生的概 率），以用于隐马尔科夫模型中隐含状态的产生和发射概率的计算；步骤2 基于搜索引擎查询日志构建语言模型，以用于计算隐马尔科夫模型中初始 状态概率和隐含状态转换概率；以及步骤3以用户输入的查询为观察状态 序列，基于所建立的错误模型和语言模型确定可能的隐含状态、发射概率、 初始状态概率和隐含状态转换概率，利用隐马尔科夫模型获取该查询对应 的最优隐含状态序列。

现参考图1，更具体地，在步骤1，基于搜索引擎查询日志挖掘错误 查询及其正确形式的查询对，建立错误模型，也就是估计不同错误模式的 发生的概率。

步骤（11）基于查询日志挖掘错误查询及其正确形式的查询对；

可以通过下列途径来从搜索引擎查询日志中挖掘错误查询及其正确 形式的查询对：

a)用户搜索查询Q时，点击了纠错推荐C，该(Q,C)对即为错误查询 及其正确形式的查询对；

b)用户搜索查询Q时，其点击链接的标题、摘要中包含查询Q的纠 错形式C，该(Q,C)对即为错误查询及其正确形式的查询对；

c)用户搜索查询Q时，其点击链接的标题、摘要中未包含Q的所有 分词结果，而包含了与Q编辑距离相近的字段C，当(Q,C)之间的编辑距离 小于一定阈值时，可将其作为错误查询及其正确形式的查询对处理；

d)用户搜索查询Q后无点击行为，而在同一会话中的其他查询C产 生点击行为，当(Q,C)之间的编辑距离小于一定阈值时，可将其作为错误查 询及其正确形式的查询对处理。

步骤（12）建立错误模型，也就是对错误模式建模，估计不同错误模 式的发生的概率。

错误模型的建立是基于(Q,C)的对应错误分段(q₁q₂q₃...q_m,c₁c₂c₃...c_m)中错 误模式(e₁e₂e₂...e_m)发生的概率统计，q_m是代表的是查询Q的第m个分段，其 中，e_i对应错误模式c_i→q_i。简单而言，错误模式可以理解为表示将正确形 式c_i写成错误形式q_i的情况，错误模式发生的概率反映的是将某种正确形 式写为某种错误形式的可能性的大小，例如将正确的“A”写成错误的“B” 的可能性是多少。

步骤（12）主要可包括：

（12a）从错误查询及其正确形式的查询对(Q,C)的对应错误分段 (q₁q₂q₃...q_m,c₁c₂c₃...c_m)获取错误模式(e₁e₂e₂...e_m)，即能够获得对应的错误模式 (c₁→q₁,c₂→q₂,c₃→q₃,...,c_m→q_m)。例如，从查询对（泰囡，泰囧）中获得的 错误模式为泰->泰，囡->囧；从查询对（bubujingxin，步步惊心）中获取 的错误模式为（bu->步，bu->步，jing->惊，xin->心）。

此外，为了更好的解决中文查询纠错中的问题，汉字和英文字母的错 误模式是不同的，其中汉字的错误模式为同音别字、近音别字、形近别字、 前后字交换、尾字缺少等，英文字母的错误模式为字母缺失、字母写错、 字母多余、缺少空格、前后字位置颠倒、拼音转汉字等；汉字和英文字母 的正确模式均为相同符号的匹配。因此，还可以通过下面的方式尽可能挖 掘出更多的错误模式，也就是说在构建汉字的错误模式时会考虑同音别 字、近音别字等，英文字母的错误模式的构建会考虑字母缺失等。例如可 通过如下方式来获取可能的错误模式：对查询Q进行编辑，其中对于英文 字母的编辑方式有匹配、替换、插入、删除、前后字交换、拼音转汉字等， 对于中文字的编辑方式有匹配、同音字替换、近音字替换、形近字替换、 前后字交换、尾字补全等，采用动态规划算法获得由查询Q到其正确形式C 编辑距离最小的编辑方式，那么对于查询Q中的每一个英文字母、拼音段 或中文字q_i能够在C中找到对应的英文字母、拼音段、中文字c_i，也即能 够获得对应的错误模式(c₁→q₁,c₂→q₂,c₃→q₃,...,c_m→q_m)。

（12b）对所获取的错误模式(e₁e₂e₂...e_m)进行概率统计以建立错误模型， 其中e_i对应错误模式c_i→q_i。对错误模式建模就是通过统计错误模式的出现 次数来进行估计错误模式发生的概率。在此，通过统计的方式获得n_e元错 误模型，也即为在错误模式(e₁e₂e₂...e_m)中e_i发生的概率仅取决于其前n_e-1个 错误模式$(e_{i-n_e+1}{e}_{i-n_e+2}...e_{i-1}):$

$P\left(e_i\right|e_1{e}_2{e}_3...e_{i-1})=P\left(e_i\right|e_{i-n_e+1}{e}_{i-n_e+2}...e_{i-1})$

n_e元为大于0的自然数，这个值是可以自行设定的，就如同N-gram 语言模型中的元数一样。比如说，假定错误模型为2元（即n_e=2），在错 误模式（bu->步，bu->步，jing->惊，xin->心）中，错误模式（xin->心） 取决于（jing->惊）后出现（xin->心）的概率，而如果设定错误模型为3 元，则错误模式（xin->心）取决于（bu->步，jing->惊）后面出现（xin-> 心）的概率。例如，对于2元的错误模型，错误模式（xin->心）出现的概 率为：错误模式（jing->惊）与（xin->心）在所获取的错误模式中连续出 现的次数和错误模式（jing->惊）与任一错误模式在所获取的错误模式中 连续出现的次数的比值。

该错误模型中每个错误模式发生的概率可以用于计算隐马尔科夫模 型中的发射概率。在基于隐马尔科夫模型的查询纠错中，所述隐马尔科夫 模型中的发射概率反映的是将隐含状态S_i错写成观察状态O_i的概率分布， 如上文所述，其可对应于错误模式s_i→o_i的概率分布，s_i为隐含状态S_i的取 值，o_i为观察状态O_i的取值，该概率反映的是将s_i错写成o_i的可能性的大 小。

而且还可以利用错误模型来产生可能的隐含状态，例如以用户输入的 查询作为隐马尔科夫模型中的观察状态序列O₁O₂O₃...O_m，其对应的隐含状态 序列S₁S₂S₃...S_m中某一状态S_i的取值可来自于观察状态O_i所对应的错误模 式。例如，在观察状态O_i所对应的一个错误模式中，观察状态O_i为错误形 式，可以将该错误形式对应的正确形式作为观察状态O_i的可能的隐含状 态，并且如上文所述，可以将该错误模式的发生概率（其反映将该正确形 式写出错误形式O_i的可能性大小）作为隐马尔科夫模型中的某个发射概 率，其代表将该隐含状态错写成观察状态O_i的概率，其中1<i<=m。

上述错误模型主要用于隐马尔科夫模型中隐含状态的产生（也可参见 下文对步骤（32）的相关描述）和发射概率计算，相对于采用粗粒度的编 辑距离产生的隐马尔科夫模型隐含状态而言，可以提高隐含状态产生概率 计算的预估精度。编辑距离只能区分不同编辑方式的概率，这主要是因为 编辑距离通常由人工设定，不可能对每种错误模式都进行考虑。例如在错 误模式xin->心，出现在错误模式(bu->步，bu->步，jing->惊)后面的概率， 远高于其他的错误模式，如xin->新，而对于编辑距离而言，二者是相同 的。第二，采用错误模型来产生隐含状态，可以有效的降低计算复杂度， 这主要是因为采用错误模型计算出来的隐含状态分布概率较为精细，具有 区分度，故而可以舍弃概率较低的隐含状态，大大降低了考虑所有编辑方 式而产生的无用隐含状态的计算复杂度。第三，由于保留的错误模式概率 较高，故而在资源有限（内存资源、时间资源）的情况下，保留同等数量 的隐含状态，采用错误模式的纠错系统具有更高的准确率和速度。

在步骤2，基于搜索引擎查询日志构建语言模型，以用于计算隐马尔 科夫模型中初始状态概率和隐含状态转换概率。

在自然语言处理领域，最常见的语言模型为N-gram语言模型，可以 采用树的结构进行存储，也可以采用hash表的形式存储，结构不限。如上 文背景知识所介绍的，Ngram语言模型可以看作（N-1）阶马尔可夫模型， 即当前词的概率取决于在其之前出现的（N-1）个词。该概率主要以统计 文本词频的方式来获取。例如，以查询日志作为训练文本建立Bi-gram语 言模型，词语对w_k-1w_k出现的概率为：

其中，count(w_k-1w_k)表示连续词语对w_k-1w_k在训练文本中出现的次数， M为训练文本中单词的总数。p(w₁)的概率为训练文本中w₁在首位出现的 次数与w₁在训练文本中出现的次数的比值。

因此，对于隐马尔科夫模型中，某一隐含状态序列S₁S₂S₃...S_m，通过基 于查询日志建立的语言模型，可以得到状态s_i-1s_i出现的概率，该概率可以 作为隐马尔科夫模型中从隐含状态s_i-1到隐含状态s_i的转换概率。也可以 通过该语言模型得到初始状态s₁的概率分布，并可以将其作为隐马尔科夫 模型中初始状态概率（具体可参见步骤3）。

在步骤3，将用户输入的查询作为隐马尔科夫模型的观察状态序列， 将用户查询的可能的正确形式作为隐马尔科夫模型的隐含状态序列，在给 定观察状态序列、可能的隐含状态、初始状态概率、隐含状态转移概率、 发射概率的情况下，利用隐马尔科夫模型中隐含状态的转移实现对查询的 切分和纠错，并采用剪枝的维特比算法计算与该观察状态序列对应的最优 的隐含状态序列，也即为对该查询的最优的纠错结果序列。

例如，假设用户查询Q为观察状态序列O₁O₂O₃...O_m，其中每一个观察状 态对应的是用户查询Q中的字符，用户查询的正确形式S₁S₂S₃...S_m是对应于 所述观察状态序列O₁O₂O₃...O_m的隐含状态，对于给定的O_i，S_i可以有多种取 值。

步骤（31）利用所建立的语言模型计算初始状态概率。

在给定所述观察状态序列O₁O₂O₃...O_m的情况下，计算所述隐马尔科夫模 型初始状态概率分布π={π_i}，即为S₁的概率分布，S₁指的是观察状态O₁对应的正确形式，假设S₁可以有N个取值，则对应每种取值有不同的概 率：

${\pi }_i=P(S_1=s_1^i),1\le i\le N$

π_i≥0

$\underset{i=1}{\overset{N}{\Sigma }}{\pi }_i=1$

其中为S₁的第i种状态取值，可利用上述语言模型计算出概率 代表隐含状态S₁取第i个值的概率，其可以为在 搜索引擎查询日志中出现在首位的次数与在搜索引擎查询日志中出现的 次数的比值。并且为了方便处理，可对其进行归一化，也即为：

$P^{\prime }(S_1=s_1^i)=P\left(s_1^i\right)$

${\pi }_i=P(S_1=s_1^i)=\frac{P^{\prime }(S_1=s_1^i)}{\underset{j=1}{\overset{N}{\Sigma }}{P}^{\prime }(S_1=s_1^j)}=\frac{P^{\prime }\left(s_1^i\right)}{\underset{j=1}{\overset{N}{\Sigma }}{P}^{\prime }\left(s_1^j\right)}$

步骤（32），利用所建立的错误模型产生可能的隐含状态，并确定发 射概率。

对于给定的观察状态序列O₁O₂O₃...O_m，所述隐含状态序列S₁S₂S₃...S_m中某 一状态S_i的取值取决于观察状态O_i所对应的错误模式中概率较高的E种错 误模式，其中E的值取决于概率大于某一阈值的观察状态O_i所对应的错误 模式的个数E′，如E′大于某一固定数值K，则E=K，否则E=E′。

例如，从观察状态O_i所对应的错误模式中，选择其发生概率大于某一 阈值的每个错误模式中的正确形式作为观察状态O_i的可能的隐含状态，并 且将该错误模式的发生概率作为隐马尔科夫模型中的发射概率，其代表将 该隐含状态错写成观察状态O_i的概率。

步骤33）利用所建立的语言模型计算隐马尔科夫模型的隐含状态转换 概率。

隐马尔科夫模型的状态转移概率，也可以理解为从一个隐含状态转换 到下一个隐含状态的概率分布，可以利用所建立的语言模型来进行计算。 例如，对于某一隐含状态序列S₁S₂S₃...S_m，计算其中某一个状态S_i发生概率 如下：

$P(S_i=s_i|S_{i-n_l+1}{S}_{i-n_l+2}...S_{i-1})=P\left(s_i\right|s_{{i-n}_l+1}{s}_{{i-n}_l+2}...s_{i-1}),$其中n_l为所建立的语言模型 的阶数。对于N阶马尔可夫模型，隐含状态的产生概率应该取决于它的前 N个状态。

例如，对于某一隐含状态序列S₁S₂S₃...S_m，假设所建立的为2元语言模 型，那么可以将在搜索查询日志中这两个状态值s_i-1s_i连续出现的概率，作 为隐马尔科夫模型中从隐含状态s_i-1到隐含状态s_i的状态转换概率。

步骤(34)基于上述的观察状态序列，可能的隐含状态、初始状态概率、 隐含状态转换概率、发射概率，利用隐马尔科夫模型获取该查询对应的最 优隐含状态序列，利用隐马尔科夫模型中隐含状态的转移实现对查询的切 分和纠错，并采用剪枝的维特比算法计算最优的隐含状态序列，也即为最 优的纠错结果序列。

在此，利用隐马尔科夫模型隐含状态的转移来实现查询的切分和纠 错，首先基于前一观察状态计算所得的多个最优隐含状态产生当前观察状 态对应的可能隐含状态，然后利用隐含状态之间的转移来对原始查询进行 尝试切分，所谓尝试切分是指判断从上一次的切分位置到当前隐含状态的 路径是否能够构成词，从而能够很好的处理中文查询中包含有汉字、拼音 和英文等情况。此外，在产生隐含状态的过程中，也考虑到了汉字和英文 字母的不同错误模式。

图2给出了根据本发明一个优选实施例的剪枝的维特比方法的流程 图。在该方法中，在计算最优隐含状态序列S₁S₂S₃...S_m时，对于到达某个隐 含状态S_i的E种错误模式的路径，仅保存概率高于一定阈值或固定个数的 最优路径，从而确保所保留的当前隐含状态及其构成路径的质量，在保证 计算速度的同时，也提高了准确率。需要说明的是到达某个隐含状态S_i的 某个错误模式e_i的最优路径个数取决于语言模型的阶数，其上限值随语言 模型阶数的增长而减少。

更具体地，将用户输入的查询作为隐马尔科夫模型的观察状态序列 O₁O₂O₃...O_m，首先利用上文所述的方法获取观察状态o₁可能的隐含状态s₁（202），利用所建立的语言模型计算初始状态概率分布（204），接着初始 化i为2（206），并利用所建立的错误模型获取观察状态o_i可能对应的隐 含状态（208）；在210，计算每个可能的隐含状态s_i的概率；其中 在对应观察状态O_i的隐含状态中，每个隐含状态的概率取决于状态 转移概率和错误模式概率的乘积，也即为：

$P\left(s_i^k\right|S_1{S}_2...S_{i-1},O_i)=P(S_i=s_i^k|S_1{S}_2...S_{i-1})\times P\left(e_i^k\right|E_1{E}_2...E_{i-1})$

在212中，对于到达某个隐含状态S_i的E种错误模式的路径（即从前 续隐含状态到达现有隐含状态Si的隐含状态序列），仅保存该路径对应的 隐含状态序列发生的概率高于一定阈值或固定个数的最优路径。

如图3所示，给定观察状态序列O₁O₂O₃...O_m，其中某个观察状态o_i对应 的隐含状态Si可以取多个值，那么对于该观察状态序列对应多个可能的隐 含状态序列S₁S₂S₃...S_m。从图3可以看出到达某个隐含状态S_i的有多条路径， 每条路径对应从前续隐含状态到达现有隐含状态Si的一个隐含状态序列。

需要说明的是到达某个隐含状态S_i的某个错误模式e_i的最优路径个数 取决于语言模型的阶数。当语言模型的阶数较高时，其概率估计精度高， 可以保留较少的最优路径，当语言模型的阶数较低时，其概率估计精度随 之降低，因而需要保留较多的最优路径。

然后将i加1（214），并判断i是否小于等于m（216），如果是，则返 回到步骤210继续执行至步骤216，否则结束，输出该查询对应的最优隐 含状态序列（218）。

应指出，在上文描述的各种示例中，虽然经常以1阶隐马尔科夫模型、 2阶语言模型、2阶错误模型来进行举例说明，但本领域人员应理解，其 目的不是对隐马尔科夫模型、语言模型、错误模型的阶数进行任何限制。 基于上文实施例的描述，本领域技术人员可以对上述模型的阶数进行任意 变化或调整。

在本发明的又一个实施例中，还提供了一种基于错误模式挖掘的中文 搜索引擎查询纠错系统，包括:

错误模型装置，基于搜索引擎查询日志挖掘错误查询及其正确形式的 查询对，建立错误模型；所述错误模型是基于对错误模式发生的概率统计 而建立的，所述错误模式发生的概率反映的是将某种正确形式写为某种错 误形式的可能性的大小；

语言模型装置，基于搜索引擎查询日志构建语言模型；

隐马尔科夫模型装置，以用户输入的查询作为隐马尔科夫模型的观察 状态序列，基于所建立的错误模型产生可能的隐含状态并计算发射概率， 基于所建立的语言模型计算初始状态概率和隐含状态转换概率，以及基于 隐马尔科夫模型获取该查询对应的最优隐含状态序列。

在又一个实施例中，还提供了一种中文搜索引擎检索方法，所述方法 包括：接收用户输入的查询；利用上文所述的查询纠错方法，获取该查询 对应的正确形式；并且以所获得的正确形式进行检索并将检索结果返回给 用户。

在又一个实施例中，还提供了一种中文搜索引擎，该中文搜索引擎在 接收到用户输入的查询时，利用上文所述的查询纠错方法，获取该查询对 应的正确形式；然后以所获得的正确形式进行检索并将检索结果返回给用 户。

通过上述本发明具体实施例，可以看出本发明针对中文搜索引擎查询 中包含多种不同的错误模式，通过挖掘搜索引擎查询日志中的多种错误模 式并建模，有效的改善了查询纠错系统中查询及其正确形式之间转换概率 的预估精度；在此基础上构建了基于隐马尔科夫模型的中文查询纠错系 统，利用隐含状态的转移实现对查询的切分和纠错，并采用剪枝的维特比 算法计算最优的隐含状态序列，从而改进了查询纠错系统中查询及其正确 形式之间转换概率的预估精度，提高了查询纠错的准确率和速度。

虽然本发明已经通过优选实施例进行了描述，然而本发明并非局限于 这里所描述的实施例，在不脱离本发明范围的情况下还包括所做出的各种 改变以及变化。