基于搜索引擎日志的中文糾錯方法研究

楊蘇穩 張曉如

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

關鍵詞：搜索引擎日志;中文糾錯;模糊匹配;最小編輯距離

DOI：10.11907/rjdk.192456 開放科學（資源服務）標識碼（OSID）：

中圖分類號：TP391文獻標識碼：A 文章編號：1672-7800（2020）006-0182-06

0 引言

隨著大數據時代的到來，越來越多的數據充斥著整個互聯網，如何在海量數據中找到有用信息已變得越來越迫切。搜索引擎的出現極大地方便了用戶進行信息查找，然而，用戶在查詢輸入時，由于輸入法的原因或者不細心等，總會存在輸入錯別字、多字甚至少字的現象。因此，對查詢詞進行校正是提高查詢效率的重要手段。為了提升用戶體驗，本文設計了基于搜索引擎日志的中文糾錯方案。

中文文本校對相對于英文文本校對起步較晚，目前中文文本糾錯主要是針對字級別和詞級別的糾錯，常用的有基于概率統計的方法、基于機器學習的方法、基于規則的方法和基于混合的方法。

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

（2）基于機器學習的方法。基于機器學習的方法可以理解為排除有歧義詞的過程，對待校對的目標詞建立混淆集，用混淆集替換相應位置上的漢字產生候選集，然后根據相關規則對候選集進行排序實現校對功能。排序規則可以為一種或多種，如利用上下文特征、統計語言模型或將幾種因素相結合等。張磊等提出一種快速的中文模糊詞匹配算法，實現了基于相似詞集代換與語言模型評分的自動校對方法，能夠檢查并糾正加字、減字及字串替換等錯誤;張照煌提出利用混淆集替換的方法實現文本自動校對，首先根據相似字特征生成混淆集，然后利用混淆集替換對應位置上的字生成候選集，最后利用統計模型對候選集進行打分，根據評分高低對候選集進行排序。

（3）基于規則或語義學知識的方法。在研究基于規則或語義學知識進行自動校對的過程中，一般先對大規模語料文本進行觀察和統計，對其字、詞、詞法、句法、語義和語用錯誤進行分析與總結，通過總結錯誤發生的共同規律，得到能夠反映錯誤的一般產生式規則集。在進行文本校對時，直接運用這些產生式集進行查錯判斷，若出現錯誤，再通過相關運算得到錯字詞的替換集，并從替換集中選擇一個概率最大的詞作為修正的候選詞。易蓉湘等通過對大量漢語錯誤文本的分析，總結出錯字詞規律和產生式規則，并基于這些規則實現文本查錯與糾錯功能。

（4）基于混合的方法?；诨旌系姆椒ǎ櫭剂x就是綜合使用上述方法。由于錯誤類型種類繁多，無法一一對其規律進行總結，因此僅使用一種方法很難覆蓋所有錯誤問題。為了更好地解決該問題，一般采用混合方法，如采用規則與統計相結合的方法。劉亮亮等提出一種多特征融合的模型，然后利用規則判斷中文文本中的真詞錯誤;段建勇等提出基于統計與特征相結合的查詢糾錯方法，對用戶輸入的查詢詞建模，生成混淆集，再利用混淆集排序模型選出最優結果推薦給用戶，達到查錯、糾錯的目的;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 結語

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