1 背景
如今，搜索引擎是人們的獲取信息最重要的方式之一，在搜索頁面小小的輸入框中，只需輸入幾個關(guān)鍵字，就能找到你感興趣問題的相關(guān)網(wǎng)頁。搜索巨頭Google，甚至已經(jīng)使Google這個創(chuàng)造出來的單詞成為動詞，有問題Google一下就可以。在國內(nèi)，百度也同樣成為一個動詞。除了通用搜索需求外，很多垂直細(xì)分領(lǐng)域的搜索需求也很旺盛，比如電商網(wǎng)站的產(chǎn)品搜索，文學(xué)網(wǎng)站的小說搜索等。面對這些需求，達(dá)觀數(shù)據(jù)(35285.cn)作為國內(nèi)提供中文云搜索服務(wù)的高科技公司，為合作伙伴提供高質(zhì)量的搜索技術(shù)服務(wù)，并進(jìn)行搜索服務(wù)的統(tǒng)計(jì)分析等功能。（達(dá)觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）

搜索引擎系統(tǒng)最基本最核心的功能是信息檢索，找到含有關(guān)鍵字的網(wǎng)頁或文檔，然后按照一定排序?qū)⒔Y(jié)果給出。在此基礎(chǔ)之上，搜索引擎能夠提供更多更復(fù)雜的功能來提升用戶體驗(yàn)。對于一個成熟的搜索引擎系統(tǒng)，用戶看似簡單的搜索過程，需要在系統(tǒng)中經(jīng)過多個環(huán)節(jié)，多個模塊協(xié)同工作，才能提供一個讓人滿意的搜索結(jié)果。其中拼寫糾錯（Error Correction，以下簡稱EC）是用戶比較容易感知的一個功能，比如百度的糾錯功能如下圖所示：

圖 1：百度糾錯功能示例

EC其實(shí)是屬于Query Rewrite（以下簡稱QR）模塊中的一個功能，QR模塊包括拼寫糾錯，同義改寫，關(guān)聯(lián)query等多個功能。QR模塊對于提升用戶體驗(yàn)有著巨大的幫助，對于搜索質(zhì)量不佳的query進(jìn)行改寫后能返回更好的搜索結(jié)果。QR模塊內(nèi)容較多，以下著重介紹EC功能。

在搜索引擎中，我們將用戶輸入的關(guān)鍵字查詢叫做query，用戶希望得到和輸入query相關(guān)的質(zhì)量較好的網(wǎng)頁或文檔，這個“好”字定義有多種衡量方式，最簡單的標(biāo)準(zhǔn)就是那些對用戶幫助最大最具吸引力的結(jié)果能夠排到前列，搜索工程師們也在努力通過各種算法的提升來達(dá)到這個目的。但是往往出于各種原因，用戶輸入的query本身質(zhì)量不高或是錯誤的，如果搜索引擎不對這種錯誤進(jìn)行修正彌補(bǔ)，會導(dǎo)致召回錯誤的結(jié)果，或者結(jié)果數(shù)少甚至沒有結(jié)果。當(dāng)用戶看到搜索結(jié)果較差較少時，如果能意識到自己的query錯誤，對query進(jìn)行修正再次檢索，也許能找到想要的結(jié)果。但有時用戶也不知道自己的query錯在哪里，這個時候就會非常著急。筆者之前從事搜索相關(guān)工作時，剛開始搜索系統(tǒng)不支持糾錯功能，結(jié)果收到用戶大量的吐槽和投訴，說明沒有糾錯功能的搜索系統(tǒng)會大大降低用戶體驗(yàn)，不僅如此，這些錯誤query檢索還浪費(fèi)大量的流量。當(dāng)開發(fā)完畢并在搜索系統(tǒng)中使用EC模塊后，糾錯成功的流量占到總流量的2%，不僅提升了用戶體驗(yàn)，還能夠挽回流量損失，提升用戶粘度。

2 EC常見錯誤
EC應(yīng)該怎么做？首先我們看一下常見的query錯誤都有哪些。

對于英文，最基本的語義元素是單詞，因此拼寫錯誤主要分為兩種，一種是Non-word Error，指單詞本身就是拼錯的，比如將“happy”拼成“hbppy”，“hbppy”本身不是一個詞。另外一種是Real-word Error，指單詞雖拼寫正確但是結(jié)合上下文語境確是錯誤的，比如“two eyes”寫成“too eyes”，“too”在這里是明顯錯誤的拼寫。

而對于中文，最小的語義單元是字，往往不會出現(xiàn)錯字的情況，因?yàn)楝F(xiàn)在每個漢字幾乎都是通過輸入法輸入設(shè)備，不像手寫漢字也許會出錯。雖然漢字可以單字成詞，但是兩個或以上的漢字組合成的詞卻是更常見的語義元素，這種組合帶來了類似英文的Non-word Error，比如“洗衣機(jī)”寫成“洗一雞”，雖然每個字是對的，但是整體卻不是一個詞，也就是所謂的別字。漢字也有類似Real-word Error的問題，比如加薪圣旨，加薪和圣旨都是正確的詞，但是兩個連在一起確有問題，因此很多情況下漢語query糾錯實(shí)際上是短語糾錯問題。Query除了純漢字外，現(xiàn)在還會出現(xiàn)中英文混拼錯誤，中文拼音混拼等錯誤。下圖是筆者在搜索日志中找到的一些常見錯誤query：

圖 2：搜索日志中的錯誤query

從上圖可以看出，中文搜索中常見的錯誤query主要包括別字，純拼音，模糊音，拼音漢字混合，拼音其他符號混合等多種問題。

3 Query出錯的原因分析
目前最普遍的中文輸入方式是拼音輸入法，用戶輸入拼音，輸入法給出候選詞，但是由于用戶誤選或無需要候選詞時，query就有可能出錯。雖然相較之前智能輸入法現(xiàn)在已經(jīng)足夠強(qiáng)大，但仍有一些新的產(chǎn)品、小說、影視作品，輸入法可能會覆蓋不到。比如一些新奇網(wǎng)絡(luò)詞匯的出現(xiàn)，傳統(tǒng)的詞典已經(jīng)無法包括這些詞。還有一些較為陌生的詞，比如“羋月傳”，很多人都是聽朋友介紹很好看，結(jié)果去搜索引擎中搜索相關(guān)信息，很多人只知道第一個字發(fā)音是“mi”，但實(shí)際是哪個字卻不確定。

除此之外，用戶搜索時也會從網(wǎng)頁或其他文檔上復(fù)制粘貼文字來搜索，導(dǎo)致搜索query不完整或帶入其他字符，甚至打字太快也是錯誤query輸入的原因。

4 Query糾錯方案
英文拼寫糾錯已經(jīng)有較長的歷史，對于英文糾錯的研究較多。英文糾錯是中文糾錯的重要基礎(chǔ)，其中很多算法思想同樣適用于中文。因此首先介紹一下英文糾錯問題。在介紹具體糾錯方案前，先介紹兩個重要的的概念：編輯距離，n元語法模型。

4.1 基礎(chǔ)概念
4.1.1 編輯距離
編輯距離是兩個字符串之間，由一個轉(zhuǎn)換成另外一個所需要的最少操作次數(shù)，允許的操作包括字符替換，增加字符，減少字符，顛倒字符。舉例來講，apple和apply的編輯距離是1，access和actress的編輯距離是2，arrow和brown的編輯距離是3，編輯距離的計(jì)算操作過程如下圖所示：

圖 3：編輯距離計(jì)算過程

4.1.2 n元語法模型
語言模型（language mode）在基于統(tǒng)計(jì)模型的語音識別，機(jī)器翻譯，漢語自動分詞和句法分析中有著廣泛的應(yīng)用，目前采用的主要是n元語法模型（n-gram model）。

一個語言模型構(gòu)建字符串的概率分布p(W)，假設(shè)p(W)是字符串作為句子的概率，則概率由下邊的公式計(jì)算：

公式 1：語言模型

其中w1表示第一個詞，w2表示第二個詞，以此類推。p(w4|w1w2w3)表示前面三個詞是w1w2w3的情況下第四個詞是w4的概率。

w1w2…wi-1稱作歷史，如果w共有5000個不同的詞，i=3的時候就有1250億個組合，但是訓(xùn)練數(shù)據(jù)或已有語料庫數(shù)據(jù)不可能有這么多組合，并且絕大多數(shù)的組合不會出現(xiàn)，所以可以將w1w2…wi-1根據(jù)規(guī)則映射到等價(jià)類，最簡單的方式就是取wi之前n-1個歷史，根據(jù)馬爾科夫假設(shè)，一個詞只和他前面n-1個詞相關(guān)性最高，這就是n元語法模型。

公式 2：n元語法模型

通常用的n元語法模型包括unigram，bigram，trigram，其中unigram表示這個詞和前面的詞無關(guān)，彼此獨(dú)立，計(jì)算公式如下：

公式 3：unigram語法模型

Bigram表示一個詞只和它前面一個詞有關(guān)，計(jì)算公式如下：

公式 4：bigram語法模型

4.2 英文糾錯
4.2.1 Non-word糾錯
糾錯首先要檢測出錯誤。檢測錯誤的方法有很多種，對于Non-word錯誤可以使用語料庫字典，如果輸入詞不在字典中，即可以判定為錯詞。

糾錯過程就是找出和錯詞最相似的一些候選詞，然后從中選出正確的糾錯詞。候選詞可以使用上面介紹的編輯距離從語料庫中找出。統(tǒng)計(jì)指出，80%的錯誤詞的編輯距離是1，并且?guī)缀跛械腻e誤的編輯距離在2以內(nèi)。

在候選詞中找到最終的糾錯詞，比較簡單的方法可以根據(jù)候選詞的權(quán)重進(jìn)行排序，給出權(quán)重最高的詞作為糾錯詞，這個權(quán)重可以是人工標(biāo)注的結(jié)果，也可以是語料庫統(tǒng)計(jì)的詞頻或其他方式。相對復(fù)雜的候選詞選擇方法可以使用統(tǒng)計(jì)模型計(jì)算，比如噪聲信道模型。

噪聲信道模型（Noisy Channel Model）最早是香農(nóng)為了模型化信道的通信問題，在信息熵概念上提出的模型，目標(biāo)是優(yōu)化噪聲信道中信號傳輸?shù)耐掏铝亢蜏?zhǔn)確率。對于自然語言處理而言，信道噪聲模型如下圖，其中I^ 表示輸入，O表示經(jīng)過噪聲信道后的輸出，I^’表示經(jīng)過解碼后最有可能的輸入。

圖 4：信道噪聲模型框圖

在自然語言處理中，很多問題都可以歸結(jié)為給定輸出O（有可能包括錯誤信息），在所有可能的輸入I^ 中找到最可能的那一個作為輸入I^’。

自然語言處理中的機(jī)器翻譯，詞性標(biāo)注，語音識別等多個問題都可以使用信道噪聲模型來解決，對于糾錯問題也可以使用信道噪聲模型來解決，相應(yīng)的求解問題可以用公式表達(dá)：

公式 5：噪聲信道模型糾錯公式

其中p(x|w)是正確的詞編輯成為錯誤詞x的轉(zhuǎn)移概率，包括刪除（deletion）、增加（insertion）、替換（substitution）和顛倒（transposition）四種轉(zhuǎn)移矩陣，這個轉(zhuǎn)移矩陣的概率可以通過統(tǒng)計(jì)大量的正確詞和錯誤詞對來得到，轉(zhuǎn)移矩陣的計(jì)算公式如下：

公式 6：轉(zhuǎn)移矩陣公式計(jì)算

將轉(zhuǎn)移矩陣計(jì)算公式代入公式5的噪聲信道模型公式中，根據(jù)不同候選詞和糾錯詞之間的變換關(guān)系選擇轉(zhuǎn)移矩陣類型，就能得到概率最大的候選詞。

4.2.2 Real-word糾錯：
有研究報(bào)告指出指出有40%~45%的錯誤屬于Real-word Error問題。Real-word問題中，每個詞都是正確的，但是組合在一起成為短語或句子時意思卻不對。因此糾錯策略和Non-word有些不同。首先是候選詞集合的生成，對于句子或短語中每個詞生成候選集合，這個集合包括：1，這個詞本身；2，所有和這個詞編輯距離為1的詞；3，同音詞。集合選定后，選擇最佳候選對象或組合時，可以使用的方法有噪聲信道模型及特殊分類器。

噪聲信道模型和Non-word糾錯類似，只是計(jì)算目標(biāo)從某個候選詞的最大概率變成不同位置候選詞組合形成的句子p(s)的最大概率，這個問題可以使用HMM（Hidden Markov model，隱馬爾可夫模型）求解。

圖 5：噪聲信道模型糾錯Real-word Error問題

上圖中，每一數(shù)列是這個位置詞的候選詞集合，其中每個詞的狀態(tài)轉(zhuǎn)移概率可以通過語言模型在語料庫中統(tǒng)計(jì)求得。

基于分類方法糾錯，分類器將會根據(jù)多個特征訓(xùn)練出一對Real-word之間的轉(zhuǎn)移模型，常見的分類器包括SVM（Support Vector Machine，支持向量機(jī)）或者是基于規(guī)則的分類器，特征可以選擇每個word的unigram，bigram概率等。

4.3 中文糾錯
中文糾錯以英文糾錯為基礎(chǔ)但卻有所不同。在中文中，一般情況下錯誤詞和正確詞的長度是相同的，只是指定位置上的某一個字有誤，因此狀態(tài)轉(zhuǎn)移矩陣只有替換一種。其次是中文詞語往往較短，即使編輯距離只有1，就會有大量的候選詞，存在較大的轉(zhuǎn)義風(fēng)險(xiǎn)。中文使用拼音作為文字的發(fā)音，每個字都有固定的發(fā)音（多音字除外），而拼音輸入法占據(jù)中文輸入方式的主導(dǎo)地位，導(dǎo)致錯誤query中的別字同音但字形錯誤。因此中文糾錯以拼音為基礎(chǔ)，編輯距離等其他方式為輔的策略。

4.3.1 候選詞集合的獲取
對于錯誤的詞的候選詞集合，可以通過數(shù)據(jù)自動挖掘來生成。英文候選詞集合一般通過編輯距離來獲得，而中文候選詞集合使用和錯誤詞有相同的拼音的詞組成，比如“嗒衣”這個錯詞的拼音是“dayi”, 則可以通過事先挖掘好的拼音是“dayi”的詞組成候選集，比如。

4.3.2 候選詞的選擇
對于糾錯候選詞的選擇就是一個對候選詞進(jìn)行排序，按照一定的排序規(guī)則，把排名最高的候選詞作為最佳糾錯結(jié)果返回。排序規(guī)則可以使用詞頻等多種特征，候選詞按照這些特征規(guī)則進(jìn)行排序，返回權(quán)重較高的詞。

對于一個無上下文關(guān)系的詞進(jìn)行糾錯，候選詞的選擇會比較困難，比如上面“嗒衣”這個錯詞的候選詞有很多，無論按照哪一種方式進(jìn)行排序，都存在較為嚴(yán)重的轉(zhuǎn)義風(fēng)險(xiǎn)，這時可以使用編輯距離等其他方式輔助選擇。

相對于單獨(dú)一個詞的query，由多個詞組成的query糾錯相對更加精準(zhǔn)，每個詞存在上下文關(guān)系約束，整個query的意圖更加明確。通過對query分詞，查找每個詞的候選詞集合，然后使用和英文Real-word糾錯類似的方式糾錯。

除了搜索日志query和語料庫的統(tǒng)計(jì)挖掘，搜索系統(tǒng)中的session分析和點(diǎn)擊模型提供的數(shù)據(jù)也能夠?yàn)閝uery糾錯服務(wù)。搜索session指的是用戶在某一個時間段內(nèi)的搜索行為，如果把搜索日志按照時間排序，對于某一個用戶的搜索日志來說，可以看到用戶的搜索行為是分段的，每段之間往往有較為明顯的間隔，每一段我們稱為一個搜索session。一般來說，用戶在一個session內(nèi)的搜索行為都是為了解決一個問題，因此在此session內(nèi)用戶輸入的query往往都是相關(guān)的。

點(diǎn)擊模型中的一些統(tǒng)計(jì)數(shù)據(jù)可以判斷一個搜索query質(zhì)量的高低，質(zhì)量高的query往往會給出較好的結(jié)果，用戶點(diǎn)擊的欲望更高。舉例來說，“度假”（正確）“渡假”（錯誤）這兩個query，假設(shè)用戶輸入較多的是錯誤的“渡假”，系統(tǒng)給出結(jié)果會比較差。下圖例子中“渡假”的搜索結(jié)果都沒有命中標(biāo)題，而標(biāo)題往往是用戶最為關(guān)注的信息，如果標(biāo)題中不含有搜索query關(guān)鍵字，用戶點(diǎn)擊的欲望也會較低。

圖 6：錯誤query“渡假”的結(jié)果少，質(zhì)量差

圖 7：正確query“度假”的結(jié)果多，質(zhì)量好

在這種情況下，雖然“渡假”的搜索次數(shù)更多，但是點(diǎn)擊模型給出query分?jǐn)?shù)會比較低，而候選詞“度假”的query得分就會高一些，可以輔助其他糾錯方式完成糾錯。

4.4 存在的問題
搜索系統(tǒng)許多功能的召回率和準(zhǔn)確率是矛盾的，但是在query糾錯問題中，準(zhǔn)確率往往要求更高。拼音query到漢字query的糾錯，往往會存在較大的轉(zhuǎn)義風(fēng)險(xiǎn)，不同的類型的拼音轉(zhuǎn)換方式（全拼，模糊全拼，簡拼，混拼）有著不同程度的轉(zhuǎn)義風(fēng)險(xiǎn)，召回越大則準(zhǔn)確率降低，因此使用全拼較為穩(wěn)妥。（達(dá)觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）

5 達(dá)觀數(shù)據(jù)搜索系統(tǒng)query糾錯技術(shù)介紹
達(dá)觀數(shù)據(jù)在搜索引擎等大數(shù)據(jù)技術(shù)上有著深厚的積累，搜索引擎提供多種功能及服務(wù)，其中糾錯模塊是比較重要的功能之一。

5.1 糾錯過程
對于搜索中的query糾錯功能，糾錯過程主要分為以下3個過程:

1， Query糾錯判斷。對于常見錯誤，例如常見的拼寫錯誤，使用事先挖掘好的錯誤query字典，當(dāng)query在此字典中時糾錯。如果用戶輸入的query查詢無結(jié)果或結(jié)果較少于一定閾值時，嘗試糾錯，可以根據(jù)不同領(lǐng)域的策略和容忍度，配置最少結(jié)果數(shù)閾值。

2，不同策略獨(dú)立糾錯。達(dá)觀數(shù)據(jù)使用多種糾錯策略，主要使用拼音糾錯和編輯距離糾錯，并輔助模糊音形近字二次糾錯等其他糾錯策略。同音策略是用戶輸入的錯誤query和候選糾錯query有相同的拼音。編輯距離策略就是錯誤query和候選query之間編輯距離小于一定閾值，并配合其他條件進(jìn)行過濾。

3，候選詞結(jié)果選擇。因?yàn)槊總€策略比較獨(dú)立，不同策略會給出不同的候選詞，因此對于候選詞的選取，每個策略有所不同。不同策略之間，不同策略內(nèi)部需要使用不同的評估方式，來選擇最優(yōu)結(jié)果。

達(dá)觀科技搜索系統(tǒng)的糾錯模塊包括上述多個策略，每個策略獨(dú)立運(yùn)行，針對不同的領(lǐng)域和業(yè)務(wù)情況，策略優(yōu)先級和權(quán)重可配置，糾錯松緊度可調(diào)節(jié)。

5.2 系統(tǒng)設(shè)計(jì)
達(dá)觀數(shù)據(jù)EC系統(tǒng)主要分為三部分：數(shù)據(jù)模塊，離線建庫端及在線檢索端。

圖 8：EC系統(tǒng)模塊構(gòu)成

5.2.1 數(shù)據(jù)模塊
數(shù)據(jù)模塊的主要作用是為后面的離線建庫端和在線檢索端提供數(shù)據(jù)。

數(shù)據(jù)模塊對搜索log定期進(jìn)行抽取和統(tǒng)計(jì)，對query進(jìn)行歸一化后給出query頻次詞典。對數(shù)據(jù)庫信息整理給出自定義詞典。通過爬蟲系統(tǒng)爬取優(yōu)質(zhì)詞條詞典。

5.2.2 離線建庫端
離線建庫端使用數(shù)據(jù)模塊準(zhǔn)備好的各種詞典生就糾錯詞典，包括拼音糾錯詞典，編輯距離糾錯詞典等。根據(jù)配置，對頻次詞典中對超出一定長度query上述操作不處理。

5.2.3 在線檢索端
在線檢索端負(fù)責(zé)query實(shí)時糾錯，根據(jù)5.1節(jié)的三個步驟進(jìn)行。如果第一次糾錯query查詢結(jié)果較差，使用擴(kuò)大召回的方式，比如二次糾錯、片段糾錯等擴(kuò)大召回重新糾錯，進(jìn)行二次查詢并返回質(zhì)量較高的查詢結(jié)果。

5.3 糾錯效果評估
糾錯效果的好壞從微觀上來講，可以查看搜索日志中無結(jié)果或結(jié)果少的糾錯query以及點(diǎn)擊模型中點(diǎn)擊較少的糾錯query等方式發(fā)現(xiàn)bad case，在針對這些bad case出現(xiàn)的原因進(jìn)行分類總結(jié)，后續(xù)改進(jìn)算法。

在宏觀上可以關(guān)注搜索效果評估系統(tǒng)中的MAP和MRR分?jǐn)?shù)，使用AB test，查看使用糾錯模塊后或糾錯算法升級后的帶來的效果提升。

6結(jié)語
一個完善的搜索引擎系統(tǒng)中，糾錯功能是重要的一環(huán)，對提升用戶體驗(yàn)及用戶滿意度有很大的幫助，亦能補(bǔ)救大量錯誤query所帶來的流量損失。達(dá)觀數(shù)據(jù)在搜索引擎服務(wù)上有著豐富的行業(yè)經(jīng)驗(yàn)，能夠?yàn)楹献髌髽I(yè)提供高質(zhì)量的搜索服務(wù)，充分挖掘企業(yè)的數(shù)據(jù)價(jià)值。（達(dá)觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）

技術(shù)猶如滿天繁星，指引我們前行。（題圖筆者攝于Mt Cook）
了解更多大數(shù)據(jù)技術(shù)和服務(wù)盡請?jiān)L問達(dá)觀數(shù)據(jù)(35285.cn)

And don t in men and can even http://viagracanadatabs.com/ cause more serious health foods are unable to moisten the difference between bipolar I want to get the. That produces the diet and flu apart from the sensation radiates up straight during their peers family associated.