楊蘇穩(wěn) 張曉如

摘要：針對(duì)用戶使用搜索引擎輸入關(guān)鍵詞查詢信息時(shí)，由于輸入法的原因或者不小心輸入錯(cuò)誤關(guān)鍵詞等，致使搜索結(jié)果不符合用戶預(yù)期的問題，提出基于搜索引擎日志的中文糾錯(cuò)方法。首先對(duì)用戶網(wǎng)絡(luò)日志展開研究，對(duì)數(shù)據(jù)進(jìn)行預(yù)處理，將用戶常見錯(cuò)誤分為兩人類：一類為拼音引起的錯(cuò)誤，針對(duì)該類錯(cuò)誤，參考并改進(jìn)了基于拼音索引的中文模糊匹配算法進(jìn)行糾錯(cuò);另一類為多字、少字、異位及別字引起的錯(cuò)誤，針對(duì)該類錯(cuò)誤，設(shè)計(jì)了模糊匹配方法結(jié)合最小編輯距離方法進(jìn)行糾錯(cuò)。經(jīng)過實(shí)驗(yàn)驗(yàn)證，證明了該糾錯(cuò)方法的有效性，該方法能夠一定程度上提升用戶體驗(yàn)，滿足實(shí)際工程需要。

關(guān)鍵詞：搜索引擎日志;中文糾錯(cuò);模糊匹配;最小編輯距離

DOI：10.11907/rjdk.192456 開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼（OSID）：

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2020）006-0182-06

0 引言

隨著大數(shù)據(jù)時(shí)代的到來，越來越多的數(shù)據(jù)充斥著整個(gè)互聯(lián)網(wǎng)，如何在海量數(shù)據(jù)中找到有用信息已變得越來越迫切。搜索引擎的出現(xiàn)極大地方便了用戶進(jìn)行信息查找，然而，用戶在查詢輸入時(shí)，由于輸入法的原因或者不細(xì)心等，總會(huì)存在輸入錯(cuò)別字、多字甚至少字的現(xiàn)象。因此，對(duì)查詢?cè)~進(jìn)行校正是提高查詢效率的重要手段。為了提升用戶體驗(yàn)，本文設(shè)計(jì)了基于搜索引擎日志的中文糾錯(cuò)方案。

中文文本校對(duì)相對(duì)于英文文本校對(duì)起步較晚，目前中文文本糾錯(cuò)主要是針對(duì)字級(jí)別和詞級(jí)別的糾錯(cuò)，常用的有基于概率統(tǒng)計(jì)的方法、基于機(jī)器學(xué)習(xí)的方法、基于規(guī)則的方法和基于混合的方法。

（1）基于概率統(tǒng)計(jì)的方法?；诟怕式y(tǒng)計(jì)的糾錯(cuò)方法是利用大規(guī)模語料提取文字、詞以及詞性的上下文關(guān)聯(lián)度、搭配等特征，然后基于此進(jìn)行文本糾錯(cuò)。常見的概率模型有N-gram語言模型、最大熵模型等，但是統(tǒng)計(jì)模型存在難以獲得大規(guī)模訓(xùn)練語料以及數(shù)據(jù)稀疏表示等問題。陳智鵬等通過建立N-gram模型得到候選集，根據(jù)TF/IDF計(jì)算權(quán)重排序獲得最優(yōu)解推薦給用戶，實(shí)現(xiàn)自動(dòng)糾錯(cuò);馬金山等提出使用N-gram模型局部查錯(cuò)法與依存分析全局查錯(cuò)法對(duì)文本進(jìn)行自動(dòng)校對(duì);徐白在考慮輸入詞串上下文的同時(shí)，統(tǒng)計(jì)研究查詢串特征，融合N-gram相似性、拼音相似度等因素進(jìn)行排序，實(shí)現(xiàn)文本的自動(dòng)校對(duì)功能。

（2）基于機(jī)器學(xué)習(xí)的方法?；跈C(jī)器學(xué)習(xí)的方法可以理解為排除有歧義詞的過程，對(duì)待校對(duì)的目標(biāo)詞建立混淆集，用混淆集替換相應(yīng)位置上的漢字產(chǎn)生候選集，然后根據(jù)相關(guān)規(guī)則對(duì)候選集進(jìn)行排序?qū)崿F(xiàn)校對(duì)功能。排序規(guī)則可以為一種或多種，如利用上下文特征、統(tǒng)計(jì)語言模型或?qū)追N因素相結(jié)合等。張磊等提出一種快速的中文模糊詞匹配算法，實(shí)現(xiàn)了基于相似詞集代換與語言模型評(píng)分的自動(dòng)校對(duì)方法，能夠檢查并糾正加字、減字及字串替換等錯(cuò)誤;張照煌提出利用混淆集替換的方法實(shí)現(xiàn)文本自動(dòng)校對(duì)，首先根據(jù)相似字特征生成混淆集，然后利用混淆集替換對(duì)應(yīng)位置上的字生成候選集，最后利用統(tǒng)計(jì)模型對(duì)候選集進(jìn)行打分，根據(jù)評(píng)分高低對(duì)候選集進(jìn)行排序。

（3）基于規(guī)則或語義學(xué)知識(shí)的方法。在研究基于規(guī)則或語義學(xué)知識(shí)進(jìn)行自動(dòng)校對(duì)的過程中，一般先對(duì)大規(guī)模語料文本進(jìn)行觀察和統(tǒng)計(jì)，對(duì)其字、詞、詞法、句法、語義和語用錯(cuò)誤進(jìn)行分析與總結(jié)，通過總結(jié)錯(cuò)誤發(fā)生的共同規(guī)律，得到能夠反映錯(cuò)誤的一般產(chǎn)生式規(guī)則集。在進(jìn)行文本校對(duì)時(shí)，直接運(yùn)用這些產(chǎn)生式集進(jìn)行查錯(cuò)判斷，若出現(xiàn)錯(cuò)誤，再通過相關(guān)運(yùn)算得到錯(cuò)字詞的替換集，并從替換集中選擇一個(gè)概率最大的詞作為修正的候選詞。易蓉湘等通過對(duì)大量漢語錯(cuò)誤文本的分析，總結(jié)出錯(cuò)字詞規(guī)律和產(chǎn)生式規(guī)則，并基于這些規(guī)則實(shí)現(xiàn)文本查錯(cuò)與糾錯(cuò)功能。

（4）基于混合的方法?；诨旌系姆椒?，顧名思義就是綜合使用上述方法。由于錯(cuò)誤類型種類繁多，無法一一對(duì)其規(guī)律進(jìn)行總結(jié)，因此僅使用一種方法很難覆蓋所有錯(cuò)誤問題。為了更好地解決該問題，一般采用混合方法，如采用規(guī)則與統(tǒng)計(jì)相結(jié)合的方法。劉亮亮等提出一種多特征融合的模型，然后利用規(guī)則判斷中文文本中的真詞錯(cuò)誤;段建勇等提出基于統(tǒng)計(jì)與特征相結(jié)合的查詢糾錯(cuò)方法，對(duì)用戶輸入的查詢?cè)~建模，生成混淆集，再利用混淆集排序模型選出最優(yōu)結(jié)果推薦給用戶，達(dá)到查錯(cuò)、糾錯(cuò)的目的;Subramaniam等利用查詢?nèi)罩窘⒄Z言模型，并結(jié)合最小編輯距離進(jìn)行糾錯(cuò);王斯宇等提出基于混淆集及上下文特征的方法進(jìn)行糾錯(cuò)。

通過分析國(guó)內(nèi)外研究現(xiàn)狀發(fā)現(xiàn)，上述糾錯(cuò)方法還存在以下不足：①未對(duì)錯(cuò)誤原因及類型進(jìn)行詳細(xì)的分類與總結(jié);②提出的糾錯(cuò)方法只針對(duì)常見的大部分錯(cuò)誤，并未綜合考慮所有錯(cuò)誤類別，無法對(duì)少數(shù)但現(xiàn)實(shí)存在的錯(cuò)誤類型進(jìn)行處理;③盡管有些方法融合了多種糾錯(cuò)方法，但沒有形成完整、清晰的糾錯(cuò)流程。

針對(duì)上述糾錯(cuò)方法存在的不足，本文進(jìn)行如下改進(jìn)：

第一，通過對(duì)搜索引擎日志的研究，總結(jié)搜索引擎日志中的常見錯(cuò)誤，分析導(dǎo)致錯(cuò)誤的原因，并將其分為兩類：①全拼音、半拼音、音相似錯(cuò)誤、鍵相鄰錯(cuò)誤及方言差異導(dǎo)致的錯(cuò)誤均為拼音的聲母、韻母或音調(diào)部分發(fā)生錯(cuò)誤而導(dǎo)致的;②多字、少字、異位及別字引起的錯(cuò)誤。

第二，針對(duì)錯(cuò)別字的錯(cuò)誤類型提出一整套糾錯(cuò)流程，針對(duì)不同的錯(cuò)誤類型，采用不同糾錯(cuò)方法進(jìn)行處理。

第三，針對(duì)上述第一類錯(cuò)誤，本文參考曹犟等提出的基于拼音索引的中文模糊匹配算法進(jìn)行糾錯(cuò)，但該方法僅考慮了拼音的聲母或韻母及音調(diào)變化導(dǎo)致的錯(cuò)誤，而忽略了鍵盤輸入時(shí)字母相對(duì)位置導(dǎo)致的錯(cuò)誤。為此，本文改進(jìn)了基于拼音糾錯(cuò)的算法，增加了對(duì)鍵相鄰錯(cuò)誤的糾錯(cuò)。針對(duì)上述第二類錯(cuò)誤，本文融合傳統(tǒng)模糊匹配方法與最小編輯距離方法進(jìn)行糾錯(cuò)。

1 相關(guān)技術(shù)介紹

發(fā)現(xiàn)并總結(jié)用戶常見輸入錯(cuò)誤，是針對(duì)不同錯(cuò)誤類別設(shè)計(jì)糾錯(cuò)方法的基礎(chǔ)。通過對(duì)查詢?nèi)罩镜姆治?，用戶常見輸人錯(cuò)誤主要有全拼音錯(cuò)誤、半拼音錯(cuò)誤、音相似錯(cuò)誤、鍵相鄰錯(cuò)誤、方言差異導(dǎo)致的錯(cuò)誤，以及別字、多字、少字及字間顛倒導(dǎo)致的錯(cuò)誤等。其中全拼音、半拼音、音相似錯(cuò)誤、鍵相鄰錯(cuò)誤及方言差異導(dǎo)致的錯(cuò)誤均為拼音的聲母、韻母或音調(diào)部分發(fā)生錯(cuò)誤而導(dǎo)致的，一般采用拼音糾錯(cuò)的方法進(jìn)行糾正。曹犟等提出的基于拼音索引的糾錯(cuò)方法能夠有效解決此類問題。別字、多字、少字及字間顛倒導(dǎo)致的錯(cuò)誤則一般使用模糊匹配或最小編輯距離方法進(jìn)行糾錯(cuò)。

1.1 基于拼音編輯距離的糾錯(cuò)方法

1.1.1 基于拼音編輯距離的定義

對(duì)于一個(gè)漢字的音節(jié)而言，它與另外一個(gè)音節(jié)的差異可分為3種：聲母差異、韻母差異和聲調(diào)差異。其音節(jié)的聲母、韻母和聲調(diào)取值的可能性都是有限的，可利用枚舉方式定義音節(jié)從一種取值轉(zhuǎn)換為另一種取值的編輯距離。所以，對(duì)于一個(gè)給定音節(jié)，很容易找到所有與其編輯距離為.的音節(jié)。例如，要找到所有與/lan2/編輯距離為1的音節(jié)，則取值只可能是：①聲母改變1個(gè)距離單位，韻母和聲調(diào)不變;②韻母改變1個(gè)距離單位，聲母和聲調(diào)不變;③聲母和韻母都不變，僅聲調(diào)改變1個(gè)距離單位。音節(jié)編輯距離最后均轉(zhuǎn)化為排列組合問題。

1.1.2 拼音糾錯(cuò)示例

通過對(duì)網(wǎng)絡(luò)日志的分析可知，拼音錯(cuò)誤是輸人中的主要錯(cuò)誤，但在拼音錯(cuò)誤中，還可以作細(xì)化分類。

（1）音同而誤。音同而誤是指拼音相同而發(fā)生的替換錯(cuò)誤。這類錯(cuò)誤由于拼音輸入法的原因經(jīng)常發(fā)生，且很難區(qū)別。

例如：現(xiàn)在乘汽車必需攜帶身份證嗎？

分析：句中“必需”是“必須”的同音替換錯(cuò)誤。

（2）音同聲不同而誤。即因音調(diào)不同而發(fā)生的錯(cuò)誤。

例如：百毒的創(chuàng)始人是誰？

分析：句中“百毒”就是因?yàn)椤?du2/”與“/du4/”拼音相同而聲調(diào)不同造成的替換錯(cuò)誤。

（3）音似而誤。音似而誤是指因拼音相似而造成的替換錯(cuò)誤，通常是由于聲母或韻母發(fā)生改變而造成的替換錯(cuò)誤，也可能是因?yàn)榉窖圆町惢蛳噜忔I造成的輸入錯(cuò)誤。

例l：牛德華今年有幾場(chǎng)演唱會(huì)？

分析：句中“牛德華”就是因?yàn)榉窖灾胁粎^(qū)分“L/N”而造成的錯(cuò)誤。

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

分析：句中“從生”是因?yàn)椤?eong2/”和“/ehong2/”音似而發(fā)生的替換錯(cuò)誤。

根據(jù)上述總結(jié)，在拼音錯(cuò)誤中，要么是拼音聲調(diào)發(fā)生改變，要么是拼音聲母或韻母發(fā)生改變，根據(jù)定義的拼音編輯距離可知，/Lin2/與/Ling2/的編輯距離為l，/Lin2/與/Lan2/的編輯距離也為1，但從發(fā)音機(jī)制上來說，前者的可能性更大，后者的可能很小。如果僅依據(jù)之前定義的拼音編輯距離進(jìn)行計(jì)算，則會(huì)出現(xiàn)不合理現(xiàn)象。因此，本文參考并改進(jìn)了曹犟等提出的基于拼音改良的編輯距離，對(duì)不同的拼音錯(cuò)誤賦予不同的替換代價(jià)。

1.1.3 基于拼音改良的編輯距離糾錯(cuò)方法

根據(jù)基于拼音改良的編輯距離糾錯(cuò)方法定義可知，/lan2/與/nan2/的編輯距離為1，/lan2/與/pan2/的編輯距離也為l，但是/lan2/與/nan2/的發(fā)音機(jī)制更接近。因此，基于拼音改良的編輯距離方法具體計(jì)算方式如下：

（1）替換代價(jià)小于1。音調(diào)變化導(dǎo)致的差異小于l。不管哪種拼音輸入法，都不要求用戶輸入音調(diào)，且音調(diào)錯(cuò)誤比較普遍，因此本文認(rèn)為其差異小于一般的聲母與韻母之間的差異。在本實(shí)驗(yàn)中賦予0.5的替換代價(jià)。

發(fā)音相似且特別容易發(fā)生替換錯(cuò)誤的聲母與韻母之間的差異小于l。在聲母或韻母發(fā)生改變的拼音錯(cuò)誤中，其中有4對(duì)聲母與5對(duì)韻母發(fā)生錯(cuò)誤替換的可能性遠(yuǎn)大于其它的。4對(duì)聲母分別為z/zh、c/ch、s/sh、l/n，5對(duì)韻母分別為ing/in、ang/an、eng/en、un/ui、ei/ai。本實(shí)驗(yàn)中對(duì)這9對(duì)替換錯(cuò)誤也賦予0.5的替換代價(jià)。

在實(shí)驗(yàn)最后，將所有替換代價(jià)都乘以2，以得到整數(shù)結(jié)果的編輯距離，且不影響不同串之間的相似度比較。

（2）替換代價(jià)等于l。對(duì)于除上述替換代價(jià)小于l中的4對(duì)聲母、5對(duì)韻母與相鄰鍵間發(fā)生的替換錯(cuò)誤外的其它錯(cuò)誤，均按照上文定義的拼音編輯距離進(jìn)行計(jì)算。

（3）替換代價(jià)大于l。對(duì)于同一音節(jié)，若其聲母與韻母同時(shí)發(fā)生改變，則在計(jì)算編輯距離時(shí)給予一個(gè)正的懲罰值（本文實(shí)驗(yàn)中取值為2）。根據(jù)該規(guī)則，對(duì)于音節(jié)串P₁=A₁A₂A₃…A_n（其中A_i，i=1，2，…，n代表一個(gè)音節(jié)），如果音節(jié)A₁的聲母和韻母同時(shí)發(fā)生差異為l的錯(cuò)誤替換，得到新的音節(jié)串P₂=A₁，A₂A₃…A_n，P₂與P₁的編輯距離則需乘以一個(gè)懲罰值2，結(jié)果為4。若音節(jié)A₂與音節(jié)A₃的聲母或韻母發(fā)生差異為l的錯(cuò)誤替換，得到新的音節(jié)串P₃=A₁A₂，A₃，…A_n，則P₃與P₁的編輯距離為2。

1.1.4 拼音串查詢擴(kuò)展及糾錯(cuò)過程

設(shè)用戶輸入的查詢串為H=S₁S₂S₃…S_i…S_n（其中S_i，i=1，2，…，n代表一個(gè)漢字），其拼音串為P：A₁A₂A₃…A_i…A_n（其中A_i，i=1，2，…，n代表一個(gè)拼音），m為錯(cuò)別字音節(jié)A_j的替換音節(jié)，且m≠A。，則所有因A_i發(fā)生錯(cuò)誤而被替換的拼音串為P=A₁A₂A₃…m…A_n（其中A_i，i=1，2，…，n代表一個(gè)拼音）。由于最終返回給用戶的結(jié)果不可能為所有糾正值，只需推薦TOP-K個(gè)即可，那么替換字S_i的音節(jié)m的編輯距離也不可能取所有情況，本次實(shí)驗(yàn)只取距離為1的音節(jié)集合。

在檢索時(shí)，首先分別檢索P_j1=A₁A₂A₃…A_j-1和P_j2=A_j+1A_j+2…A_n出現(xiàn)的位置，然后作比較，若在某個(gè)文本中，串P_j1與串P_j2同時(shí)出現(xiàn)，且P_j1的位置在串P_j2位置的j+1位之前，則將該文本加入候選集中，最終根據(jù)排序模型生成排序并推薦給用戶。因此，最終將基于拼音的編輯距離糾錯(cuò)問題轉(zhuǎn)化為兩個(gè)查詢字串的精確匹配問題。

1.2 基于模糊匹配的糾錯(cuò)方法

對(duì)于形似字錯(cuò)誤和多字、少字及異位錯(cuò)誤，目前并沒有一般性的規(guī)律可循，拼音糾錯(cuò)方法也無法發(fā)揮作用，因此本文采用模糊匹配方法進(jìn)行糾錯(cuò)。

定義l形似字：已知兩個(gè)漢字W₁、W₂，若W₁、W₂之間的形相似度SSim（W₁，W₂）>A，則W₁與W₂互為形相似字。

本文從相似度的角度出發(fā)，通過對(duì)大規(guī)模語料的計(jì)算，得到與錯(cuò)誤查詢?cè)~相似度最高的詞作為錯(cuò)誤查詢?cè)~串的替換詞集合，并推薦給用戶。在用戶參與確認(rèn)的情況下，形成正誤詞對(duì)，提高糾錯(cuò)的準(zhǔn)確性。另一方面，建立自適應(yīng)語料庫，將現(xiàn)有語料庫中不存在的新詞添加到語料中，實(shí)現(xiàn)語料庫的不斷更新，以及新詞的登錄與糾錯(cuò)。

已知S=W₁W₂…W_n為當(dāng)前查詢串，P=C₁C₂…C_n為待匹配串，則S與P的相似度為：

在實(shí)際應(yīng)用中，主要通過設(shè)置閾值判斷兩個(gè)詞串是否匹配，若大于設(shè)置的閾值，則查詢?cè)~S與待匹配串P匹配成功，并將P推薦給用戶作為糾正建議，否則匹配失敗。

1.3 最小編輯距離糾錯(cuò)方法

編輯距離又稱為L(zhǎng)eveinshtein距離，是由俄羅斯科學(xué)家Levenshtein在1965年提出的。以字符串為例，查詢字符串a(chǎn)與匹配字符串b的編輯距離是將a轉(zhuǎn)換成b的最小操作次數(shù)，這里的操作包括3種：①插人一個(gè)字符;②刪除一個(gè)字符;③替換一個(gè)字符。

例如：計(jì)算忠心耿和忠心耿耿的編輯距離，操作如下：忠心耿->忠心耿耿，添加字符耿，需要做1次操作，編輯距離為l。

1.3.1 算法基本原理及步驟

s[1…n]和t[1…m]分別代表查詢串與待匹配串，求串s[1…n]轉(zhuǎn)換到串t[1…m]所需執(zhí)行的最小操作次數(shù)，一般用動(dòng)態(tài)規(guī)劃方法求得。其算法一般基本步驟為：

（1）構(gòu)造行數(shù)為m+l、列數(shù)為n+1的矩陣，用來保存完成某個(gè)轉(zhuǎn)換需要執(zhí)行的操作次數(shù)，matrix[n][m]的值即為將串S[1…n]轉(zhuǎn)換到串t[1…m]需要執(zhí)行的操作次數(shù)。

（2）初始化matrix第一行為0到n，第一列為0到m。Matrix[0][j]表示第l行第j-1列的值，該值表示將串s[1…0]轉(zhuǎn)換為t[1…j）所需執(zhí)行的操作次數(shù)，很顯然將一個(gè)空串轉(zhuǎn)換為一個(gè)長(zhǎng)度為j的串，只需執(zhí)行j次的增加操作即可，所以matrix[0][j]）的值應(yīng)該是j，其它值依此類推。

（3）掃描每個(gè)從1到n的s[i]字符。

（4）掃描每個(gè)從1到m的s[j]字符。

（5）將串s與串t的每一個(gè)字符進(jìn)行兩兩比較，如果相等，則定義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]轉(zhuǎn)換到串t[1…m]所需執(zhí)行的最小操作次數(shù)。

由上述得到動(dòng)態(tài)規(guī)劃公式為：

2 改進(jìn)的糾錯(cuò)策略

2.1 糾錯(cuò)流程設(shè)計(jì)

通過對(duì)用戶查詢?nèi)罩镜姆治隹偨Y(jié)，用戶常見輸入錯(cuò)誤主要有全拼音錯(cuò)誤、半拼音錯(cuò)誤、音相似錯(cuò)誤、鍵相鄰錯(cuò)誤、方言差異導(dǎo)致的錯(cuò)誤，以及別字、多字、少字及字間顛倒導(dǎo)致的錯(cuò)誤等，單一糾錯(cuò)方法無法對(duì)其一一進(jìn)行糾正。為此，本文提出一套完整的糾錯(cuò)流程，首先將上述錯(cuò)誤類型分為兩大類，然后針對(duì)不同類別設(shè)計(jì)不同的糾錯(cuò)方法。其中全拼音、半拼音、音相似錯(cuò)誤、鍵相鄰錯(cuò)誤及方言差異導(dǎo)致的錯(cuò)誤均為拼音的聲母、韻母或音調(diào)部分發(fā)生錯(cuò)誤而導(dǎo)致的，針對(duì)該類錯(cuò)誤，本文參考并改進(jìn)了曹犟等提出的基于拼音索引的中文模糊匹配算法進(jìn)行糾錯(cuò);另一類為多字、少字、異位及別字引起的錯(cuò)誤，針對(duì)該類錯(cuò)誤，本文設(shè)計(jì)了融合模糊匹配方法與最小編輯距離的方法進(jìn)行糾錯(cuò)。查詢?cè)~串糾錯(cuò)流程如圖l所示。

查錯(cuò)與糾錯(cuò)是文本校對(duì)中密不可分的兩部分，具體步驟如下：①獲取用戶查詢串并進(jìn)行分詞;②利用N-gram模型判斷分詞后的散串是否合理;③若為合理的串，轉(zhuǎn)入步驟⑧輸出查詢結(jié)果，否則轉(zhuǎn)入步驟④;④判斷查詢串是否為拼音錯(cuò)誤，若是，轉(zhuǎn)入步驟⑤，否則轉(zhuǎn)入步驟⑦;⑤將錯(cuò)誤的散串按照漢字拼音表轉(zhuǎn)化為拼音串，對(duì)于多音字則需按照多音字表轉(zhuǎn)化為相應(yīng)的拼音串;⑥根據(jù)定義的基于拼音的編輯距離計(jì)算方式對(duì)錯(cuò)誤的查詢串按照編輯距離進(jìn)行擴(kuò)展，得到錯(cuò)誤查詢串的混淆集，然后對(duì)所有擴(kuò)展的查詢串進(jìn)行精確匹配，得到查詢結(jié)果后，首先作去重處理，然后按照編輯距離大小進(jìn)行排序，形成候選集后，轉(zhuǎn)人步驟⑧;⑦采用模糊匹配與最小編輯距離方法對(duì)別字進(jìn)行糾正，并將結(jié)果放人候選集中;⑧根據(jù)排序模型對(duì)候選集進(jìn)行排序，并顯示給用戶。

2.2 改進(jìn)的拼音糾錯(cuò)策略

曹犟等提出的拼音糾錯(cuò)方法僅考慮了拼音的聲母、韻母及音調(diào)變化導(dǎo)致的錯(cuò)誤，而忽略了鍵盤輸入時(shí)字母相對(duì)位置導(dǎo)致的錯(cuò)誤。通過對(duì)用戶網(wǎng)絡(luò)日志錯(cuò)字詞的研究發(fā)現(xiàn)，約7%的錯(cuò)誤是由于鍵盤相鄰鍵敲擊錯(cuò)誤導(dǎo)致的，如“考慮”與“老慮”。因此，本文在曹犟等提出的拼音糾錯(cuò)方法基礎(chǔ)上進(jìn)行改進(jìn)，具體改進(jìn)方法如下：相鄰鍵發(fā)生替換錯(cuò)誤的差異小于1。除上述9種易發(fā)生聲母及韻母錯(cuò)誤替換的情況外，在利用鍵盤輸人時(shí)，由于鍵盤按鍵距離較近，很容易發(fā)生相鄰鍵輸入錯(cuò)誤。如聲母“k”與“l(fā)”相鄰，因此容易輸入錯(cuò)誤，但是“k”與“p”距離較遠(yuǎn)，發(fā)生錯(cuò)誤的概率遠(yuǎn)小于被誤輸為“l(fā)”的概率。因此，本文對(duì)相鄰鍵間的差異賦予0.5的替換代價(jià)。

2.3 改進(jìn)的拼音糾錯(cuò)步驟

對(duì)于系統(tǒng)判定為拼音錯(cuò)的查詢?cè)~，先檢查拼音錯(cuò)誤，利用定義的拼音編輯距離方法進(jìn)行糾錯(cuò)并給出糾錯(cuò)建議。具體步驟如下：①執(zhí)行分詞操作，將用戶輸入的查詢?cè)~串切割成查詢段;②將僅出現(xiàn)中文錯(cuò)誤的查詢段按照漢字拼音表注音成帶聲調(diào)的拼音串;③對(duì)于查詢段中既出現(xiàn)單字又出現(xiàn)拼音串的情況，保留拼音串位置，將單字轉(zhuǎn)化成拼音，并與其組合成完整的拼音串;④根據(jù)拼音編輯距離的具體方法及規(guī)則求出編輯距離最近的拼音集合;⑤根據(jù)拼音串的查詢擴(kuò)展方法求出步驟④中拼音集合的候選集;⑥將得到的拼音候選集進(jìn)行音字轉(zhuǎn)換，形成漢字候選集;⑦根據(jù)相關(guān)排序模型對(duì)候選集進(jìn)行打分，根據(jù)分?jǐn)?shù)高低將糾錯(cuò)建議返回給用戶。

3 實(shí)驗(yàn)結(jié)果與分析

3.1數(shù)據(jù)集選取

實(shí)驗(yàn)數(shù)據(jù)來源于搜狗實(shí)驗(yàn)室提供的日志文件，其格式包括時(shí)間、用戶ID、查詢?cè)~、返回結(jié)果排名、用戶點(diǎn)擊序號(hào)、頁面URL等。具體格式如表1所示。

由表1可知，網(wǎng)絡(luò)日志中包含較多信息，由于本文實(shí)驗(yàn)只涉及到其中的查詢?cè)~部分，因此首先挑選出連續(xù)3天的查詢?nèi)罩緮?shù)據(jù)，使用MapReduce腳本提取其中的查詢?cè)~串，然后對(duì)提取的查詢?cè)~串進(jìn)行去噪、去重、去敏感詞等處理后，形成共約260萬條有效的查詢數(shù)據(jù)。

本文從260萬條有效查詢數(shù)據(jù)中隨機(jī)抽取40萬條連續(xù)記錄，對(duì)其進(jìn)行編號(hào)并根據(jù)拼音表注音形成查詢文件記錄。查詢文件結(jié)構(gòu)如表2所示。

本文使用的詞典共收錄詞組約9萬條，每個(gè)詞語都有相應(yīng)的拼音注音，且3字以上的詞語標(biāo)注拼音縮寫。詞典結(jié)構(gòu)如表3所示。

在詞典中新增兩列信息，分別為查詢?cè)~頻與日志中出現(xiàn)次數(shù)，形成語料庫文件，本次實(shí)驗(yàn)共形成語料90753條。語料庫結(jié)構(gòu)如表4所示。

3.2 實(shí)驗(yàn)過程及結(jié)果分析

測(cè)試集由搜狗實(shí)驗(yàn)室提供用戶日志中的查詢?cè)~串及人工添加數(shù)據(jù)組成。首先從查詢?nèi)罩局羞x取常用且出現(xiàn)在語料庫中的查詢?cè)~作為測(cè)試集的一部分;其次，由于查詢中某些錯(cuò)誤類型數(shù)量非常少，本文通過人工添加的方式加以補(bǔ)充;最后利用選取的測(cè)試數(shù)據(jù)根據(jù)上述糾錯(cuò)流程進(jìn)行實(shí)驗(yàn)，獲得錯(cuò)誤查詢串的糾正串，如圖2所示。

在不同規(guī)模的測(cè)試集下，準(zhǔn)確率和召回率也不同，本文共選取6組不同規(guī)模的測(cè)試集，大小分別為10K、30K、50K、70K、90K、110K，糾錯(cuò)結(jié)果如圖3所示。

從圖3可以看出，本文提出的搜索引擎中文糾錯(cuò)方法的準(zhǔn)確率和召回率都較高，因此該方法可以有效糾正用戶在進(jìn)行搜索引擎查詢時(shí)不小心輸入錯(cuò)誤查詢?cè)~的問題，并根據(jù)用戶搜索意圖返回正確的搜索結(jié)果。

將本文改進(jìn)的方法與僅使用拼音編輯距離糾錯(cuò)及模糊匹配的方法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如圖4所示。

之后將本文改進(jìn)的方法與僅使用單一統(tǒng)計(jì)方法進(jìn)行比較。如陳智鵬等提出的完全通過分析上下文統(tǒng)計(jì)信息的方法，根據(jù)中文語言特點(diǎn)，在對(duì)大規(guī)模中文語料庫建立N-gram模型的基礎(chǔ)上，通過計(jì)算TF/DF權(quán)重的方式獲得最優(yōu)糾錯(cuò)結(jié)果，實(shí)現(xiàn)對(duì)搜索引擎中關(guān)鍵詞的自動(dòng)查錯(cuò)與糾錯(cuò)。實(shí)驗(yàn)結(jié)果如圖5所示。

從實(shí)驗(yàn)結(jié)果可以得到以下結(jié)論：

（1）測(cè)試集大小直接影響實(shí)驗(yàn)的準(zhǔn)確率和召回率，本文提出的糾錯(cuò)方法在測(cè)試集為110K時(shí)，準(zhǔn)確率和召回率均達(dá)到最高。

（2）通過圖4實(shí)驗(yàn)可知，本文針對(duì)第二類錯(cuò)誤使用模糊匹配結(jié)合最小編輯距離的方法，能夠彌補(bǔ)單獨(dú)使用模糊匹配方法無法解決字間顛倒問題的缺陷，能更有效地糾正由于多字、少字、異位及別字引起的錯(cuò)誤。

（3）通過圖3與圖5對(duì)比可知，本文提出的糾錯(cuò)方法相比基于N-gram模型的糾錯(cuò)方法，在測(cè)試集達(dá)到110K時(shí)準(zhǔn)確率提高了4.8%。

4 結(jié)語

本文提出基于搜索引擎日志的糾錯(cuò)方法，該方法首先對(duì)日志進(jìn)行分析與分類，總結(jié)出不同錯(cuò)誤類型，并基于此提出糾錯(cuò)方案。針對(duì)因輸入法導(dǎo)致的拼音錯(cuò)誤，本文參考并改進(jìn)曹犟等提出的基于拼音改良的編輯方法進(jìn)行糾錯(cuò);針對(duì)多字、少字、異位及別字引起的錯(cuò)誤，本文使用模糊匹配結(jié)合最小編輯距離方法進(jìn)行糾錯(cuò)。通過實(shí)驗(yàn)，本文方法在實(shí)際中具有一定可行性，一定程度上提升了用戶滿意度。但該方法還存在一定不足，例如對(duì)新的網(wǎng)絡(luò)流行語會(huì)出現(xiàn)誤判等。后期將會(huì)考慮實(shí)時(shí)更新常見的流行語等，以進(jìn)一步提升糾錯(cuò)方法的準(zhǔn)確性。