顓 悅，熊錦華，馬宏遠(yuǎn)，程舒楊，程學(xué)旗

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所，北京 100190 2. 中國科學(xué)院大學(xué)，北京 100190 3. 國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

一種支持混合語言的并行查詢糾錯(cuò)方法

顓 悅1,2，熊錦華1，馬宏遠(yuǎn)3，程舒楊1，程學(xué)旗1

(1. 中國科學(xué)院 計(jì)算技術(shù)研究所，北京 100190 2. 中國科學(xué)院大學(xué)，北京 100190 3. 國家計(jì)算機(jī)網(wǎng)絡(luò)應(yīng)急技術(shù)處理協(xié)調(diào)中心，北京 100029)

中文信息檢索系統(tǒng)中的查詢語句包含中文字、拼音、英文等多種形式，而有些查詢語句過長，不利于糾錯(cuò)處理?，F(xiàn)有的查詢糾錯(cuò)方法不能很好的解決中文檢索系統(tǒng)中的混合語言與中文長查詢的問題。為了解決上述兩個(gè)問題，該文提出了一種支持混合語言的并行糾錯(cuò)方法。該方法通過對混合語言統(tǒng)一編碼，建立統(tǒng)一編碼語言模型和異構(gòu)字符詞典樹，并根據(jù)語言特點(diǎn)制定相應(yīng)的編輯規(guī)則對查詢詞語進(jìn)行統(tǒng)一處理，其中，針對中文長查詢，提出雙向并行的糾錯(cuò)模型。為了并行處理查詢語句，我們在字符詞典樹和語言模型的基礎(chǔ)上提出了逆向字符詞典樹和逆向語言模型的概念。模型中使用的訓(xùn)練語料庫是從用戶查詢?nèi)罩尽⒕W(wǎng)頁點(diǎn)擊日志、網(wǎng)頁鏈接信息等文件中提取的高質(zhì)量文本。實(shí)驗(yàn)表明，與單向查詢糾錯(cuò)相比，支持混合語言的并行糾錯(cuò)方法在準(zhǔn)確率上提升了9%，召回率降低了3%，在速度上提升了40%左右。

查詢糾錯(cuò)；詞典樹；語言模型；并行糾錯(cuò)

1 引言

查詢糾錯(cuò)是針對信息檢索系統(tǒng)中查詢語句的拼寫糾錯(cuò)。據(jù)統(tǒng)計(jì)，英文搜索引擎的查詢中有10%～15%含有拼寫錯(cuò)誤[1]，查詢語句直接影響信息檢索系統(tǒng)返回結(jié)果的可靠性與準(zhǔn)確性，所以現(xiàn)有的很多信息檢索系統(tǒng)都會對查詢語句進(jìn)行糾錯(cuò)處理，確保返回的檢索信息能夠滿足用戶需要，提高用戶檢索效率和檢索結(jié)果命中率。

中文信息檢索系統(tǒng)中的查詢詞類型一般有：中文、拼音、英文等形式。中文查詢中會出現(xiàn)同音字錯(cuò)誤、近音字錯(cuò)誤、形近字錯(cuò)誤、拼音轉(zhuǎn)漢字、拼音中字母缺失、前后字置換、漢字缺失等現(xiàn)象；英文查詢按照錯(cuò)誤類型不同，分為非詞錯(cuò)誤(Non-word Errors)和真詞錯(cuò)誤(Real-word Errors)[2]。非詞錯(cuò)誤是指拼寫錯(cuò)誤的詞不存在，例如，將“the”錯(cuò)誤拼寫為“tha”；真詞錯(cuò)誤是指那些拼寫錯(cuò)誤后的詞仍然是合法的情況，例如，將“the”錯(cuò)誤拼寫為“then”。

根據(jù)李亞楠、王斌對新浪愛問搜索引擎的查詢?nèi)罩痉治鯷3]可知，不考慮重復(fù)查詢時(shí)，查詢的平均字長為8.18；考慮重復(fù)查詢時(shí)，查詢的平均字長為6.14；不考慮重復(fù)查詢時(shí)，查詢平均詞數(shù)為4.14，考慮重復(fù)查詢時(shí)，查詢的平均詞數(shù)為3.07；包含三個(gè)詞的查詢最多，占24.055%。此外，對國內(nèi)某商業(yè)搜索引擎的查詢?nèi)罩痉治觯?012年1月14日查詢詞(隨機(jī)抽取1萬查詢詞)的平均字長為8.58(考慮重復(fù)查詢)；2012年5月14日查詢詞(隨機(jī)抽取1萬查詢詞)的平均字長為8.19(考慮重復(fù)查詢)。通過以上分析可知中文搜索引擎的查詢詞往往很長，而現(xiàn)在的信息檢索系統(tǒng)為了減少糾錯(cuò)時(shí)間，限定糾錯(cuò)查詢語句的長度，對于過長的語句，不進(jìn)行糾錯(cuò)。我們需要解決信息檢索系統(tǒng)中長查詢語句的糾錯(cuò)處理問題。

針對以上問題，本文提出一種支持混合語言的并行查詢糾錯(cuò)方法，解決中文混合語言和長查詢的糾錯(cuò)問題。首先，為了解決混合語言的糾錯(cuò)問題，本文提出一種偽編碼的方法，該方法把英文單詞和常用字符組合作為獨(dú)立詞進(jìn)行編碼，從而對中文、英文和其他字符組合統(tǒng)一編碼；其次，提出并行糾錯(cuò)模型來快速的處理中文長查詢語句。并行糾錯(cuò)模型把查詢語句長度超過一定閾值M的查詢分為兩段長度相近的查詢語句，然后啟動正向查詢糾錯(cuò)模塊和逆向查詢糾錯(cuò)模塊分別從正向與逆向并行處理。正向和逆向的查詢糾錯(cuò)模塊使用制定的編輯規(guī)則來處理查詢語句。在對語句進(jìn)行編輯處理的過程中會生成多種候選狀態(tài)，每個(gè)候選狀態(tài)中會保存候選項(xiàng)和操作代價(jià)W等狀態(tài)信息。最后，根據(jù)候選狀態(tài)的操作代價(jià)W給出推薦的查詢語句。

本文提出的方法使用了字符詞典樹和語言模型來分別判定詞語本身的信息和詞語所在上下文的信息。模型使用的訓(xùn)練語料是從用戶查詢?nèi)罩?、網(wǎng)頁點(diǎn)擊日志、網(wǎng)頁鏈接信息等文件中提取的高質(zhì)量文本。為了逆向處理查詢語句，我們在正向字符詞典樹和正向語言模型的基礎(chǔ)上提出了逆向字符詞典樹和逆向語言模型的概念。根據(jù)中文和英文的特點(diǎn)，分別制定了中文處理規(guī)則和英文處理規(guī)則。實(shí)驗(yàn)表明，并行查詢糾錯(cuò)模型比單向查詢糾錯(cuò)模型快了40%左右，準(zhǔn)確率提升9%左右。

本文內(nèi)容的組織結(jié)構(gòu)如下：第二部分總結(jié)相關(guān)工作；第三部分介紹面向混合語言的并行查詢糾錯(cuò)的方法；第四部分給出實(shí)驗(yàn)及結(jié)果分析；第五部分進(jìn)行總結(jié)。

2 相關(guān)工作

查詢糾錯(cuò)主要用于分析用戶輸入查詢中的錯(cuò)誤，并在合理的時(shí)間范圍內(nèi)返回其正確形式，因此主要考慮響應(yīng)時(shí)間和返回結(jié)果的正確性這兩個(gè)方面。當(dāng)前中文信息檢索系統(tǒng)中主要進(jìn)行兩種類型的查詢糾錯(cuò)任務(wù)：英文查詢糾錯(cuò)和中文查詢糾錯(cuò)。

英文查詢糾錯(cuò)技術(shù)主要分為兩種：基于詞語的拼寫糾錯(cuò)和基于上下文信息的糾錯(cuò)技術(shù)?；谠~語的拼寫糾錯(cuò)注重對單個(gè)詞拼寫錯(cuò)誤的糾正，經(jīng)典的方法有編輯距離方法[4-5]、K-gram重合度方法[6-7]以及基于語音的拼寫糾錯(cuò)方法[8]；基于上下文信息的糾錯(cuò)的目標(biāo)不僅包含詞典以外的拼寫錯(cuò)誤的單詞，還包含上下文中使用不當(dāng)?shù)膯卧~，這種方法主要利用語言模型對查詢中每個(gè)關(guān)鍵詞評估，并選出最優(yōu)的組合形式，其中經(jīng)典的方法有基于噪聲信道模型的查詢糾錯(cuò)[9-10]、基于貝葉斯分類器的查詢糾錯(cuò)[11]和基于最大熵模型的查詢糾錯(cuò)[12-13]。

在英文糾錯(cuò)技術(shù)中，編輯距離方法和K-gram重合度方法著重于單個(gè)詞語的糾錯(cuò)，能夠快速的找到與錯(cuò)誤單詞相似的詞典規(guī)范詞，這兩種方法無法處理上下文包含使用不當(dāng)?shù)恼_單詞的情況；基于噪聲信道模型的糾錯(cuò)、基于貝葉斯分類器的糾錯(cuò)和基于最大熵模型的糾錯(cuò)能夠解決這一問題。目前英文糾錯(cuò)技術(shù)僅考慮了英文搜索引擎中查詢包含的錯(cuò)誤，即英文單詞的拼寫錯(cuò)誤、使用不當(dāng)和空格的缺失等，中文搜索引擎中包含的錯(cuò)誤類型更多，語言的形式更復(fù)雜，簡單的套用上述方法無法達(dá)到很好的效果。

現(xiàn)有的中文查詢糾錯(cuò)方法多采用將查詢詞內(nèi)的中文字轉(zhuǎn)換為拼音，然后查找詞典中拼音與該查詢詞拼音字符串相似或相同的候選詞條，最后通過詞頻或語言模型的方式?jīng)Q定候選詞條是否為糾錯(cuò)結(jié)果。

周博等人在專利中對如何糾正中文搜索引擎中的英文查詢提出了一種解決方法[14]。該專利的做法是，通過詞典來判斷查詢是否包含錯(cuò)誤的英文單詞： 以空格作為英文單詞的分隔符，將查詢分割為單詞，并在一定編輯距離范圍內(nèi)搜索每個(gè)單詞的混淆集。然而，這種方法并未具體談及如何區(qū)分拼音和英文，只是采用英文詞典來簡單的對英文單詞進(jìn)行判斷，極有可能將類似于英文單詞的拼音串糾錯(cuò)成為英文詞語，不能很好的處理中文搜索引擎中包含多種語言形式的錯(cuò)誤。

為了提高糾錯(cuò)的速度，李曉東在文獻(xiàn)[15]中使用多字驅(qū)動詞典、基于拼音hash詞典的糾錯(cuò)算法以及字符串匹配糾錯(cuò)算法來處理查詢詞中出現(xiàn)的同音別字、多字漏字等錯(cuò)誤。然而，這種方法與上述方法類似，都只能處理查詢中僅包含單個(gè)詞條的情況，同時(shí)也沒有考慮到中文搜索引擎中包含的多種錯(cuò)誤形式。

上述方法沒有考慮到中文信息檢索系統(tǒng)中包含了包括中文、拼音、英文、數(shù)字等多種語言組合形式，同時(shí)對于中文長查詢沒有提出很好的解決辦法。我們受到以上相關(guān)工作的啟發(fā)，提出了一種支持混合語言的并行查詢糾錯(cuò)方法。

3 支持混合語言的并行糾錯(cuò)方法

3.1 混合語言編碼

中文查詢糾錯(cuò)是以漢字為單位進(jìn)行糾錯(cuò)處理，漢字是由拼音指定的，每個(gè)漢字可以對應(yīng)一串或幾串(多音字)拼音字母組合。英文查詢糾錯(cuò)是以英文單詞為單位進(jìn)行處理。英文是由英文字母組合而成，每個(gè)英文單詞對應(yīng)一串字母組合?？梢酝ㄟ^對英文單詞進(jìn)行編碼，把英文單詞和漢字映射到統(tǒng)一的編碼區(qū)域，從而對英文和中文進(jìn)行統(tǒng)一處理。在unicode編碼中,英文字母的編碼范圍：0x0041—0x007a。中文常用字的編碼范圍：Ox4E00—0x9FFF(表1)。對于中文搜索引擎，0x9FFF以上的unicode字符可以不進(jìn)行處理。

本論文中把0x9FFF以上的編碼unicode編碼用做英文單詞的編碼，從而把英文單詞和中文字轉(zhuǎn)化到字符序列進(jìn)行統(tǒng)一處理。英文單詞有幾十萬個(gè)，在中文搜索引擎中，用戶查詢詞涉及到的英文單詞涵蓋范圍沒有那么廣泛，只需要統(tǒng)計(jì)查詢?nèi)罩局谐Ｓ玫挠⑽膯卧~進(jìn)行編碼即可。除了英文外，也可以對查詢中常出現(xiàn)的字母、數(shù)字等符號的組合進(jìn)行編碼，例如，“360buy”、“taobao”等，作為文字單位進(jìn)行編碼。

表1 unicode中文編碼范圍

在支持混合語言的并行糾錯(cuò)方法中，使用上述編碼方式對訓(xùn)練文本中的數(shù)據(jù)進(jìn)行預(yù)處理，使用編碼后的訓(xùn)練數(shù)據(jù)構(gòu)建下文所提出的字符詞典樹和語言模型，從而統(tǒng)一處理了中文、英文和其他常用字符組合的糾錯(cuò)問題。

3.2 并行糾錯(cuò)模型

對于中文長查詢，采用單一方向的查詢糾錯(cuò)模型進(jìn)行處理，糾錯(cuò)時(shí)間會相應(yīng)的增加，糾錯(cuò)模型的準(zhǔn)確率也會相應(yīng)降低。為了解決這一問題，本模塊提出了雙向并行糾錯(cuò)模型。

并行糾錯(cuò)處理是從查詢詞的兩端同步進(jìn)行糾錯(cuò)，對于正向(從句子的左端到右端)查詢糾錯(cuò)模塊需要建立正向字符詞典樹與正向的語言模型，然后根據(jù)編輯規(guī)則，對查詢詞語從左到右進(jìn)行糾錯(cuò)處理；逆向(從句子的右端到左端)查詢糾錯(cuò)模塊需要建立逆向的字符詞典樹與逆向的語言模型，從查詢語句的右端開始進(jìn)行糾錯(cuò)處理。當(dāng)正向的糾錯(cuò)處理模塊與逆向的糾錯(cuò)處理模塊在切分點(diǎn)P處重合時(shí)，對重合部分拼接，最終得到一條完整的糾錯(cuò)語句。并行糾錯(cuò)模型的處理過程如圖1所示。

圖1 雙向糾錯(cuò)模型處理過程

3.2.1 構(gòu)建詞典樹與語言模型

3.2.1.1 構(gòu)建字符詞典樹

字符詞典樹是一種快速檢索的多叉樹結(jié)構(gòu)，利用字符串的公共前綴來節(jié)約存儲空間。字符詞典樹的根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)以外的每個(gè)節(jié)點(diǎn)只包含一個(gè)字符。如果從根節(jié)點(diǎn)到某個(gè)節(jié)點(diǎn)構(gòu)成的字符串是一個(gè)偽編碼處理后的合法詞語，則標(biāo)記該節(jié)點(diǎn)為完成節(jié)點(diǎn)并在此節(jié)點(diǎn)上存儲對應(yīng)的詞語信息。整個(gè)字符詞典樹上的節(jié)點(diǎn)分為完成狀態(tài)節(jié)點(diǎn)與非完成狀態(tài)節(jié)點(diǎn)，“和”這個(gè)詞語在字符詞典樹種對應(yīng)的拼音串路徑為：h-e,在節(jié)點(diǎn)e會標(biāo)記為完成節(jié)點(diǎn)，并在此節(jié)點(diǎn)存儲：“和”、“喝”…等詞語信息。如圖2所示,虛線代表沒畫出來的分支。

(a) 正向字符詞典樹 (b) 逆向字符詞典樹圖2 字符詞典樹

本文在正向字符詞典樹的基礎(chǔ)上，提出了逆向字符詞典樹的概念。逆向字符詞典樹是把詞語對應(yīng)的拼音字符串倒轉(zhuǎn)，然后存儲路徑上的詞語信息。例如，“很”對應(yīng)的拼音字符串為:“hen”，倒轉(zhuǎn)后變?yōu)椤皀eh”；先前所述的字符詞典樹是在字符“n”處標(biāo)記為完成節(jié)點(diǎn)并存儲“很，狠，恨…”等詞語，逆向的字符詞典樹則在字符“h”節(jié)點(diǎn)處標(biāo)記為完成節(jié)點(diǎn)，并存儲“很，狠，恨…”等詞語。逆向字符詞典樹中的節(jié)點(diǎn)類型同樣分為完成節(jié)點(diǎn)與未完成節(jié)點(diǎn)。

3.2.1.2 構(gòu)建語言模型

正向的語言模型表示在一系列活動出現(xiàn)之后的概率[16]，n-gram語言模型表示第n個(gè)詞的概率是由已經(jīng)產(chǎn)生的n-1個(gè)詞決定的。以三元語法模型為例，我們可以認(rèn)為一個(gè)詞的概率只依賴于它前面的兩個(gè)詞，那么當(dāng)n>2時(shí)，一個(gè)長度為L個(gè)基元(基元可指字、詞、短語)構(gòu)成的語句s出現(xiàn)的概率可以表示為式(1)。

(1)

(2)

由于訓(xùn)練語料庫中的數(shù)據(jù)是根據(jù)網(wǎng)頁日志和查詢?nèi)罩镜玫降模荒芨采w所有自然語言，會出現(xiàn) p(s)=0的情況，需要使用平滑技術(shù)來解決這種零概率問題。在此使用Witten-Bell平滑的方法，在此方法中，n階平滑模型被遞歸的定義為n階最大的似然模型和n-1階平滑模型的線性插值，如式(3)所示。

(3)

(4)

(5)

逆向的語言模型表示在一系列活動出現(xiàn)之前的概率，逆向語言模型的構(gòu)建是從句子尾部開始處理。正向語言模型是根據(jù)歷史信息來估計(jì)當(dāng)前詞語出現(xiàn)的概率，逆向語言模型在正向語言模型的基礎(chǔ)上進(jìn)行變形，根據(jù)未來信息來估計(jì)當(dāng)前詞語出現(xiàn)的概率。對于由L個(gè)基元(基元可指字、詞、短語)構(gòu)成的語句s出現(xiàn)的概率p(s)表示為式(6)。

(6)

其中，wi(0<=i<=L)產(chǎn)生的概率是由未來信息wi+1wi+2...wL決定的。

對于逆向語言模型同樣使用平滑技術(shù)來解決零概率問題。在此使用Witten-Bell變形的平滑方法來處理數(shù)據(jù)平滑問題。

3.2.2 編輯規(guī)則處理

對于查詢語句s,先把s轉(zhuǎn)化為字符序列(中文轉(zhuǎn)換為拼音形式、英文和數(shù)字等形式保持不變)，然后逐個(gè)字符進(jìn)行編輯處理。如果字符是中文字符，則對其進(jìn)行中文規(guī)則編輯；如果字符是英文字符，則對其進(jìn)行英文規(guī)則編輯。中文編輯處理比較嚴(yán)格，英文處理時(shí)則寬松一些。限制中文編輯是因?yàn)閷χ形钠匆暨M(jìn)行替換、插入等操作會生成龐大的中文字符集，一方面增大了存儲空間，另一方面會形成大量完全偏離原始查詢詞的糾錯(cuò)結(jié)果。

中文規(guī)則編輯包括同音匹配、多音匹配、近音替換、刪除;形近字替換、前后字符交換。其中同音匹配是指在中文字符僅對應(yīng)一種拼音形式時(shí)，將該字符替換為其拼音；多音匹配是指在中文字符對應(yīng)多種拼音形式時(shí)，將該字符替換為其多個(gè)拼音形式；近音替換是指將中文字轉(zhuǎn)換為其近似拼音；形近字替換是將中文字轉(zhuǎn)換為其形近字的拼音，對應(yīng)的形近字可在形近字表中查詢。英文規(guī)則編輯包括匹配、替換、插入、刪除、前后字符交換。其中匹配是指編輯所得的字符串即為該英文字符；替換是指將該英文字母替換為除該字母以外的其他25個(gè)英文字母；插入是指在英文字母后插入26個(gè)英文字母，產(chǎn)生26個(gè)字符串作為編輯結(jié)果。

根據(jù)相應(yīng)的規(guī)則進(jìn)行編輯后，查找字符詞典樹，如果編輯后的序列在字符詞典樹中存在對應(yīng)的中文詞語，則把當(dāng)前狀態(tài)標(biāo)記為完成狀態(tài)并加入到完成狀態(tài)隊(duì)列和未完成狀態(tài)隊(duì)列；否則標(biāo)記為未完成狀態(tài)并加入未完成狀態(tài)隊(duì)列。這里把完成狀態(tài)詞語同時(shí)加入到完成狀態(tài)隊(duì)列和未完成狀態(tài)隊(duì)列，主要是為了保存最大匹配和最小匹配生成的所有狀態(tài)，確保分詞的準(zhǔn)確性(圖3)。

狀態(tài)隊(duì)列中的每個(gè)狀態(tài)都保存著當(dāng)前狀態(tài)的操作代價(jià)W，在本模型中，操作代價(jià)是編輯操作的代價(jià)與語言模型概率的線性組合，具體形式如式(7)所示。其中edit_cost代表編輯操作的代價(jià)，ngram_cost代表語言模型計(jì)算的概率，α,β∈[0,1]且α+β=1。

(7)

圖3 EditModule函數(shù)處理過程

3.2.3 確定切分點(diǎn)

并行糾錯(cuò)模型中的切分點(diǎn)P是通過計(jì)算詞語之間的互信息得到的。對于中文長查詢，掃描字符串，計(jì)算相鄰兩個(gè)詞語之間的互信息。對有序漢字串AB中漢字A、B之間的互信息定義為式(8)。

(8)

其中P(A,B)為漢字串AB出現(xiàn)的概率，P(A)為漢字A出現(xiàn)的概率，P(B)為漢字B出現(xiàn)的概率。如果I(A,B)>0，則AB間是正相關(guān)，當(dāng)I(A,B)大于某個(gè)給定閾值，可認(rèn)為AB基本成詞；如果I(A,B)=0,則AB間是不相關(guān)的；如果I(A,B)<0，則AB間是互斥的，這時(shí)AB間基本不會結(jié)合成詞。

本文中，從長查詢的中間部分向左端、右兩端依次計(jì)算字與字之間的互信息，選取兩端長度相差最小的切分點(diǎn)。然后分別從查詢詞的兩端開始進(jìn)行查詢糾錯(cuò)處理，直到查詢切分點(diǎn)處結(jié)束。

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

4.1 實(shí)驗(yàn)數(shù)據(jù)集

本實(shí)驗(yàn)的訓(xùn)練數(shù)據(jù)是從某中文商業(yè)搜索引擎的查詢?nèi)罩?、用戶點(diǎn)擊日志，網(wǎng)頁鏈接文本等日志文件中獲取的，字符詞典樹的訓(xùn)練數(shù)據(jù)約135萬條，偽編碼的詞條有21萬條數(shù)據(jù)，語言模型的訓(xùn)練數(shù)據(jù)有 1 400萬條。

從某搜索引擎查詢?nèi)罩局须S機(jī)抽取的3 675條查詢數(shù)據(jù)作為測試數(shù)據(jù)，其中含有字母組合100條，數(shù)字組合49條，字母數(shù)字組合35條，漢字、字母、數(shù)字組合的查詢詞語有3 059條。3 675條查詢數(shù)據(jù)中錯(cuò)誤的查詢詞有173條，占整個(gè)查詢數(shù)量的4.7%。當(dāng)設(shè)定切分查詢語句的長度閾值為6時(shí)，3 675條查詢數(shù)據(jù)中有1 812條查詢?yōu)殚L查詢，占整個(gè)查詢的49.3%。

4.2 評估方法

本實(shí)驗(yàn)將采用正確率(Precision)、召回率(Recall)、F值(F measure)這三個(gè)指標(biāo)來評估系統(tǒng)，其含義具體如式(9)～(11)所示。

(11)

其中，Ns代表查詢糾錯(cuò)模塊進(jìn)行糾錯(cuò)的查詢數(shù)量；Nmc代表查詢糾錯(cuò)系統(tǒng)輸出的正確糾錯(cuò)的數(shù)量；Nmt代表測試集中包含的錯(cuò)誤查詢數(shù)量。

4.3 實(shí)驗(yàn)對比

實(shí)驗(yàn)中，QueryCorrection是根據(jù)我們前期提出的一種面向中文搜索引擎混雜語言的查詢糾錯(cuò)方法及系統(tǒng)[1]實(shí)現(xiàn)的。ReverseQueryCorrection是在逆向字符詞典樹與逆向語言模型基礎(chǔ)上，從查詢語句尾部(從右向左)進(jìn)行糾錯(cuò)的模型。ParallelQueryCorrection是我們提出的雙向并行糾錯(cuò)模型。實(shí)驗(yàn)數(shù)據(jù)如表2所示。

表2 QueryCorrection、ReverseQueryCorrection和ParallelQueryCorrection實(shí)驗(yàn)對比

從實(shí)驗(yàn)結(jié)果上來看，對于中文長查詢，單向糾錯(cuò)會消弱每個(gè)詞語的操作代價(jià)，從而容易把正確的查詢詞語糾成錯(cuò)誤的候選。而Parallel Query Correction模型通過把長查詢變?yōu)槎滩樵?，增?qiáng)了每個(gè)詞語的操作代價(jià)，提高了正確率。

但是，Parallel Query Correction模型在使用互信息將長查詢切分為短查詢的同時(shí)，查詢詞語的上下文信息也會相應(yīng)的減少，一些局部正確但是整體有誤的查詢語句不能夠得到正確的修改，造成了正確糾錯(cuò)數(shù)量的減少。此外，長查詢語句的不適當(dāng)切分也會減少正確糾錯(cuò)的數(shù)量，降低了召回率，總體上看，召回率降低了3%。從速度上看，Parallel Query Correction采用雙向的糾錯(cuò)方法，使得糾錯(cuò)速度比單向查詢糾錯(cuò)模型快了40%左右。

5 結(jié)束語

本文提出了一種支持混合語言的并行查詢糾錯(cuò)方法。我們提出了對包含中文、拼音、英文等混合語言的統(tǒng)一處理的解決方法。在正向字符詞典樹和正向語言模型的基礎(chǔ)上提出了逆向字符詞典樹和逆向語言模型的概念。通過編輯操作獲得查詢詞的候選項(xiàng)集合，通過編輯距離權(quán)重和語言模型概率的線性組合來獲取候選項(xiàng)。引入雙向糾錯(cuò)模型來處理中文長查詢的速度問題。實(shí)驗(yàn)表明，與單向查詢糾錯(cuò)相比，支持混合語言的并行糾錯(cuò)方法在準(zhǔn)確率上提升了9%，召回率降低了3%，在速度上提升了40%左右。

為了進(jìn)一步提高響應(yīng)時(shí)間，下一步的工作將圍繞多路并行糾錯(cuò)進(jìn)行相關(guān)研究，展示出更充分的實(shí)驗(yàn)評測結(jié)果。此外，可以考慮通過挖掘用戶的搜索日志中有用的反饋信息，如用戶點(diǎn)擊信息，研究如何利用這一信息改進(jìn)查詢糾錯(cuò)系統(tǒng)，進(jìn)一步提高其準(zhǔn)確率和召回。

[1] 程舒楊,熊錦華,公帥等.一種面向中文搜索引擎混雜語言的查詢糾錯(cuò)方法及系統(tǒng)：中國, 201210320575.[P].2013-01-09.

[2] Zhang Lei, Zhou Ming, HuangChangning, et al. Automatic Detection and Correction of Typed Errors in Chinese text [C]//Proceedings of the Applied Linguistics, 2001(1).

[3] 李亞楠，王斌.一個(gè)中文搜索引擎的查詢?nèi)罩痉治鯷C].中國.數(shù)字圖書館論壇.2008.

[4] Levenshtein V I. Binary codes capable of correcting deletions, insertions, and reversals [J]. Soviet PhysicsDoklady, 1966, 10(8): 707-710.

[5] Wagner R A, Fischer M J. The string-to-string correction problem [J]. Journal of the Association for Computing Machinery, 1974, 21(1): 168-173.

[6] Riseman E M, Hanson A R. A contextualpostprocessing system for error correction using binary n-grams [J]. IEEE Transactions on Computers, 1974, 23(5): 480-493.

[7] Zobel J, Dart P. Finding approximate matches in large lexicons [J]. Software-Practice and Experience, 1995, 25(3): 331-345.

[8] Rogers H J, Willett P. Searching for historical word forms in text databases using spelling-correction methods: reverse error and phonetic coding methods [J]. Journal of Documentation, 1991, 47(4): 333-353.

[9] Duan H, Hsu B P. Online spelling correction for query completion [C]//Proceedings of the 20th International Conference on World Wide Web: WWW 2011. New York, NY, USA: ACM, 2011: 117-126.

[10] Sun X, Gao J, Micol D, et al. Learning phrase-based spelling error models fromclickthrough data [C]//Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics: ACL 2010. Stroudsburg, PA, USA: Association for Computational Linguistics, 2010: 266-274.

[11] Toutanova K, Moore R C. Pronunciation modeling for improved spelling correction [C]//Proceedings of the 40th Annual Meeting on Association for Computational Linguistics. Stroudsburg, PA, USA: Association for Computational Linguistics, 2002: 144-151.

[12] Golding A R. A Bayesian hybrid method for context-sensitive spelling correction [C]//Proceedings of the 3rd Workshop on Very Large Corpora. Stroudsburg, PA, USA: Association for Computational Linguistics, 1995: 39-53.

[13] Li M, Zhu M, Zhang Y, et al. Exploring distributional similarity based models for query spelling correction [C]//Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics. Stroudsburg, PA, USA: Association for Computational Linguistics, 2006: 1025-1032.

[14] 周博,劉奕群,張敏,等.一種中文搜索引擎中查詢詞的拼寫校正方法:中國, 200810224323.3.[P].2009-2-18.

[15] 李曉東.搜索引擎中中文分詞與糾錯(cuò)模塊的設(shè)計(jì)與實(shí)現(xiàn)[D].北京交通大學(xué)碩士學(xué)位論文,2008.

[16] 宗成慶 .統(tǒng)計(jì)自然語言處理[M].北京:清華大學(xué)出版社,2008: 75-93.

Aparallel Query Correction Method for Mixed Language

ZHUAN Yue1,2, XIONG Jinhua1, MA Hongyuan3, CHENG Shuyang1, CHENG Xueqi1

(1. Institute of Computing Technology， Chinese Academy of Sciences, Beijing 100190， China; 2. University of Chinese Academy of Sciences, Beijing 100190, China; 3. National Computer Network Emergency Response Technical Team Coordination Center of China, Beijing 100029, China)

Query in Chinese information retrieval system often contains Chinese, Chinese phonetic alphabet and English etc. Existing method can not solve the issue of mixed language and long Chinese query. In order to solve these problems, we propose a parallel query correction method for mixed language. The method establishes language model with mixed language and built the heterogeneous character dictionary tree according to the corresponding edit rules to process the query words. For the long Chinese query, we put forward spell correction model of two-way parallel. For paralle processing, we put forward the concept of reverse character dictionary tree and reverse language model. The training corpus used in the model is extracted from the user query log, click log, web links and other information. Experiment shows that the parallel query correction method for mixed language increases the accuracy by 9%, reduces the recall by 3%, and, especially, speeds up the processing by 40% compared to single pass query correction.

spell correction; dictionary tree; language module; parallel spell check

顓悅(1988-)，碩士，主要研究領(lǐng)域?yàn)樽匀徽Z言處理。E?mail：zhuan＿yue@163．com熊錦華(1972-)，通訊作者，博士，副研究員，主要研究領(lǐng)域?yàn)榛ヂ?lián)網(wǎng)搜索與挖掘，大規(guī)模數(shù)據(jù)處理，分布式計(jì)算。E?mail：xjh@ict．a(chǎn)c．cn馬宏遠(yuǎn)(1981—)，博士，主要研究領(lǐng)域?yàn)樾畔z索、智能信息處理。E?mail：mahongyuan@foxmail．com

1003-0077(2016)02-0099-08

2013-08-09 定稿日期： 2014-01-09

國家重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃(973計(jì)劃)項(xiàng)目(2014CB340406，2012CB316303，2013CB329602)；國家自然科學(xué)基金(61173064，61300206)；國家科技支撐計(jì)劃項(xiàng)目(2015BAK20B03)；國家科技支撐計(jì)劃課題(2011BAH11B02)；國家242專項(xiàng)(2013G129)；國家科技支撐專項(xiàng)(2012BAH46B04)

TP391

A