1背景
如今蛆橡，搜索引擎是人們的獲取信息最重要的方式之一，在搜索頁面小小的輸入框中赋元，只需輸入幾個關(guān)鍵字忘蟹，就能找到你感興趣問題的相關(guān)網(wǎng)頁飒房。搜索巨頭Google，甚至已經(jīng)使Google這個創(chuàng)造出來的單詞成為動詞媚值，有問題Google一下就可以狠毯。在國內(nèi)，百度也同樣成為一個動詞褥芒。除了通用搜索需求外嚼松，很多垂直細分領(lǐng)域的搜索需求也很旺盛，比如電商網(wǎng)站的產(chǎn)品搜索喂很，文學(xué)網(wǎng)站的小說搜索等惜颇。面對這些需求，達觀數(shù)據(jù)(www.datagrand.com)作為國內(nèi)提供中文云搜索服務(wù)的高科技公司少辣，為合作伙伴提供高質(zhì)量的搜索技術(shù)服務(wù)凌摄，并進行搜索服務(wù)的統(tǒng)計分析等功能。（達觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）
搜索引擎系統(tǒng)最基本最核心的功能是信息檢索漓帅，找到含有關(guān)鍵字的網(wǎng)頁或文檔锨亏，然后按照一定排序?qū)⒔Y(jié)果給出。在此基礎(chǔ)之上忙干，搜索引擎能夠提供更多更復(fù)雜的功能來提升用戶體驗器予。對于一個成熟的搜索引擎系統(tǒng)，用戶看似簡單的搜索過程捐迫，需要在系統(tǒng)中經(jīng)過多個環(huán)節(jié)乾翔，多個模塊協(xié)同工作，才能提供一個讓人滿意的搜索結(jié)果施戴。其中拼寫糾錯（Error Correction反浓，以下簡稱EC）是用戶比較容易感知的一個功能，比如百度的糾錯功能如下圖所示：
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??
EC其實是屬于Query Rewrite（以下簡稱QR）模塊中的一個功能赞哗，QR模塊包括拼寫糾錯雷则，同義改寫，關(guān)聯(lián)query等多個功能肪笋。QR模塊對于提升用戶體驗有著巨大的幫助月劈，對于搜索質(zhì)量不佳的query進行改寫后能返回更好的搜索結(jié)果。QR模塊內(nèi)容較多藤乙，以下著重介紹EC功能猜揪。
在搜索引擎中，我們將用戶輸入的關(guān)鍵字查詢叫做query坛梁，用戶希望得到和輸入query相關(guān)的質(zhì)量較好的網(wǎng)頁或文檔湿右，這個“好”字定義有多種衡量方式，最簡單的標(biāo)準就是那些對用戶幫助最大最具吸引力的結(jié)果能夠排到前列罚勾，搜索工程師們也在努力通過各種算法的提升來達到這個目的毅人。但是往往出于各種原因吭狡，用戶輸入的query本身質(zhì)量不高或是錯誤的，如果搜索引擎不對這種錯誤進行修正彌補丈莺，會導(dǎo)致召回錯誤的結(jié)果划煮，或者結(jié)果數(shù)少甚至沒有結(jié)果。當(dāng)用戶看到搜索結(jié)果較差較少時缔俄，如果能意識到自己的query錯誤弛秋，對query進行修正再次檢索，也許能找到想要的結(jié)果俐载。但有時用戶也不知道自己的query錯在哪里蟹略，這個時候就會非常著急。筆者之前從事搜索相關(guān)工作時遏佣，剛開始搜索系統(tǒng)不支持糾錯功能挖炬，結(jié)果收到用戶大量的吐槽和投訴，說明沒有糾錯功能的搜索系統(tǒng)會大大降低用戶體驗状婶，不僅如此意敛，這些錯誤query檢索還浪費大量的流量。當(dāng)開發(fā)完畢并在搜索系統(tǒng)中使用EC模塊后膛虫，糾錯成功的流量占到總流量的2%草姻，不僅提升了用戶體驗，還能夠挽回流量損失稍刀，提升用戶粘度撩独。
2 EC常見錯誤
EC應(yīng)該怎么做？首先我們看一下常見的query錯誤都有哪些账月。
對于英文综膀，最基本的語義元素是單詞，因此拼寫錯誤主要分為兩種捶障，一種是Non-word Error，指單詞本身就是拼錯的纲刀，比如將“happy”拼成“hbppy”项炼，“hbppy”本身不是一個詞。另外一種是Real-word Error示绊，指單詞雖拼寫正確但是結(jié)合上下文語境確是錯誤的锭部，比如“two eyes”寫成“too eyes”，“too”在這里是明顯錯誤的拼寫面褐。
而對于中文拌禾，最小的語義單元是字，往往不會出現(xiàn)錯字的情況展哭，因為現(xiàn)在每個漢字幾乎都是通過輸入法輸入設(shè)備湃窍，不像手寫漢字也許會出錯闻蛀。雖然漢字可以單字成詞，但是兩個或以上的漢字組合成的詞卻是更常見的語義元素您市，這種組合帶來了類似英文的Non-word Error觉痛，比如“洗衣機”寫成“洗一雞”，雖然每個字是對的茵休，但是整體卻不是一個詞薪棒，也就是所謂的別字。漢字也有類似Real-word Error的問題榕莺，比如加薪圣旨俐芯，加薪和圣旨都是正確的詞，但是兩個連在一起確有問題钉鸯，因此很多情況下漢語query糾錯實際上是短語糾錯問題吧史。Query除了純漢字外，現(xiàn)在還會出現(xiàn)中英文混拼錯誤亏拉，中文拼音混拼等錯誤扣蜻。下圖是筆者在搜索日志中找到的一些常見錯誤query：
從上圖可以看出，中文搜索中常見的錯誤query主要包括別字及塘，純拼音莽使，模糊音，拼音漢字混合笙僚，拼音其他符號混合等多種問題芳肌。
3 Query出錯的原因分析
目前最普遍的中文輸入方式是拼音輸入法，用戶輸入拼音肋层，輸入法給出候選詞亿笤，但是由于用戶誤選或無需要候選詞時，query就有可能出錯栋猖。雖然相較之前智能輸入法現(xiàn)在已經(jīng)足夠強大净薛，但仍有一些新的產(chǎn)品、小說蒲拉、影視作品肃拜，輸入法可能會覆蓋不到。比如一些新奇網(wǎng)絡(luò)詞匯的出現(xiàn)雌团，傳統(tǒng)的詞典已經(jīng)無法包括這些詞燃领。還有一些較為陌生的詞，比如“羋月傳”锦援，很多人都是聽朋友介紹很好看猛蔽，結(jié)果去搜索引擎中搜索相關(guān)信息，很多人只知道第一個字發(fā)音是“mi”，但實際是哪個字卻不確定曼库。
除此之外，用戶搜索時也會從網(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，編輯距離的計算操作過程如下圖所示：
4.1.2n元語法模型
語言模型（language mode）在基于統(tǒng)計模型的語音識別月趟，機器翻譯灯蝴，漢語自動分詞和句法分析中有著廣泛的應(yīng)用，目前采用的主要是n元語法模型（n-gram model）孝宗。
一個語言模型構(gòu)建字符串的概率分布p(W)穷躁，假設(shè)p(W)是字符串作為句子的概率，則概率由下邊的公式計算：
其中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ī)則映射到等價類是复，最簡單的方式就是取wi之前n-1個歷史删顶，根據(jù)馬爾科夫假設(shè)，一個詞只和他前面n-1個詞相關(guān)性最高淑廊，這就是n元語法模型逗余。
通常用的n元語法模型包括unigram，bigram季惩，trigram录粱，其中unigram表示這個詞和前面的詞無關(guān)，彼此獨立画拾，計算公式如下：
Bigram表示一個詞只和它前面一個詞有關(guān)啥繁，計算公式如下：
4.2英文糾錯
4.2.1Non-word糾錯
糾錯首先要檢測出錯誤。檢測錯誤的方法有很多種青抛，對于Non-word錯誤可以使用語料庫字典旗闽，如果輸入詞不在字典中，即可以判定為錯詞蜜另。
糾錯過程就是找出和錯詞最相似的一些候選詞适室，然后從中選出正確的糾錯詞。候選詞可以使用上面介紹的編輯距離從語料庫中找出举瑰。統(tǒng)計指出捣辆，80%的錯誤詞的編輯距離是1，并且?guī)缀跛械腻e誤的編輯距離在2以內(nèi)嘶居。
在候選詞中找到最終的糾錯詞罪帖，比較簡單的方法可以根據(jù)候選詞的權(quán)重進行排序，給出權(quán)重最高的詞作為糾錯詞邮屁，這個權(quán)重可以是人工標(biāo)注的結(jié)果整袁，也可以是語料庫統(tǒng)計的詞頻或其他方式。相對復(fù)雜的候選詞選擇方法可以使用統(tǒng)計模型計算佑吝，比如噪聲信道模型坐昙。
噪聲信道模型（NoisyChannel Model）最早是香農(nóng)為了模型化信道的通信問題，在信息熵概念上提出的模型芋忿，目標(biāo)是優(yōu)化噪聲信道中信號傳輸?shù)耐掏铝亢蜏蚀_率炸客。對于自然語言處理而言，信道噪聲模型如下圖戈钢，其中I?表示輸入痹仙，O表示經(jīng)過噪聲信道后的輸出，I'?表示經(jīng)過解碼后最有可能的輸入殉了。
?在自然語言處理中开仰，很多問題都可以歸結(jié)為給定輸出O（有可能包括錯誤信息），在所有可能的輸入I?中找到最可能的那一個作為輸入I’?。
自然語言處理中的機器翻譯众弓，詞性標(biāo)注恩溅，語音識別等多個問題都可以使用信道噪聲模型來解決，對于糾錯問題也可以使用信道噪聲模型來解決谓娃，相應(yīng)的求解問題可以用公式表達：
其中p(x|w)是正確的詞編輯成為錯誤詞x的轉(zhuǎn)移概率脚乡，包括刪除（deletion）、增加（insertion）滨达、替換（substitution）和顛倒（transposition）四種轉(zhuǎn)移矩陣奶稠，這個轉(zhuǎn)移矩陣的概率可以通過統(tǒng)計大量的正確詞和錯誤詞對來得到，轉(zhuǎn)移矩陣的計算公式如下：
將轉(zhuǎn)移矩陣計算公式代入公式5的噪聲信道模型公式中捡遍，根據(jù)不同候選詞和糾錯詞之間的變換關(guān)系選擇轉(zhuǎn)移矩陣類型窒典，就能得到概率最大的候選詞。
4.2.2Real-word糾錯：
有研究報告指出指出有40%~45%的錯誤屬于Real-word Error問題稽莉。Real-word問題中瀑志，每個詞都是正確的，但是組合在一起成為短語或句子時意思卻不對污秆。因此糾錯策略和Non-word有些不同劈猪。首先是候選詞集合的生成，對于句子或短語中每個詞生成候選集合良拼，這個集合包括：1战得，這個詞本身；2庸推，所有和這個詞編輯距離為1的詞常侦；3，同音詞贬媒。集合選定后聋亡，選擇最佳候選對象或組合時，可以使用的方法有噪聲信道模型及特殊分類器际乘。
噪聲信道模型和Non-word糾錯類似坡倔，只是計算目標(biāo)從某個候選詞的最大概率變成不同位置候選詞組合形成的句子p(s)的最大概率，這個問題可以使用HMM（Hidden Markov model脖含，隱馬爾可夫模型）求解罪塔。
Error問題
上圖中，每一數(shù)列是這個位置詞的候選詞集合养葵，其中每個詞的狀態(tài)轉(zhuǎn)移概率可以通過語言模型在語料庫中統(tǒng)計求得征堪。
基于分類方法糾錯，分類器將會根據(jù)多個特征訓(xùn)練出一對Real-word之間的轉(zhuǎn)移模型关拒，常見的分類器包括SVM（Support Vector Machine佃蚜，支持向量機）或者是基于規(guī)則的分類器咳榜，特征可以選擇每個word的unigram，bigram概率等爽锥。
4.3中文糾錯
中文糾錯以英文糾錯為基礎(chǔ)但卻有所不同。在中文中畔柔，一般情況下錯誤詞和正確詞的長度是相同的氯夷，只是指定位置上的某一個字有誤，因此狀態(tài)轉(zhuǎn)移矩陣只有替換一種靶擦。其次是中文詞語往往較短腮考，即使編輯距離只有1，就會有大量的候選詞玄捕，存在較大的轉(zhuǎn)義風(fēng)險捐腿。中文使用拼音作為文字的發(fā)音襟诸，每個字都有固定的發(fā)音（多音字除外），而拼音輸入法占據(jù)中文輸入方式的主導(dǎo)地位，導(dǎo)致錯誤query中的別字同音但字形錯誤藏澳。因此中文糾錯以拼音為基礎(chǔ)，編輯距離等其他方式為輔的策略兴泥。
4.3.1候選詞集合的獲取
對于錯誤的詞的候選詞集合麦备，可以通過數(shù)據(jù)自動挖掘來生成。英文候選詞集合一般通過編輯距離來獲得攀圈，而中文候選詞集合使用和錯誤詞有相同的拼音的詞組成暴凑，比如“嗒衣”這個錯詞的拼音是“dayi”,則可以通過事先挖掘好的拼音是“dayi”的詞組成候選集，比如赘来。
4.3.2候選詞的選擇
對于糾錯候選詞的選擇就是一個對候選詞進行排序现喳，按照一定的排序規(guī)則，把排名最高的候選詞作為最佳糾錯結(jié)果返回犬辰。排序規(guī)則可以使用詞頻等多種特征嗦篱，候選詞按照這些特征規(guī)則進行排序，返回權(quán)重較高的詞幌缝。
對于一個無上下文關(guān)系的詞進行糾錯默色，候選詞的選擇會比較困難，比如上面“嗒衣”這個錯詞的候選詞有很多狮腿，無論按照哪一種方式進行排序腿宰，都存在較為嚴重的轉(zhuǎn)義風(fēng)險，這時可以使用編輯距離等其他方式輔助選擇缘厢。
相對于單獨一個詞的query吃度，由多個詞組成的query糾錯相對更加精準，每個詞存在上下文關(guān)系約束贴硫，整個query的意圖更加明確椿每。通過對query分詞伊者，查找每個詞的候選詞集合，然后使用和英文Real-word糾錯類似的方式糾錯间护。
除了搜索日志query和語料庫的統(tǒng)計挖掘亦渗，搜索系統(tǒng)中的session分析和點擊模型提供的數(shù)據(jù)也能夠為query糾錯服務(wù)。搜索session指的是用戶在某一個時間段內(nèi)的搜索行為汁尺，如果把搜索日志按照時間排序法精，對于某一個用戶的搜索日志來說，可以看到用戶的搜索行為是分段的痴突，每段之間往往有較為明顯的間隔搂蜓，每一段我們稱為一個搜索session。一般來說辽装，用戶在一個session內(nèi)的搜索行為都是為了解決一個問題帮碰，因此在此session內(nèi)用戶輸入的query往往都是相關(guān)的。
點擊模型中的一些統(tǒng)計數(shù)據(jù)可以判斷一個搜索query質(zhì)量的高低拾积，質(zhì)量高的query往往會給出較好的結(jié)果殉挽，用戶點擊的欲望更高。舉例來說拓巧，“度假”（正確）“渡假”（錯誤）這兩個query此再，假設(shè)用戶輸入較多的是錯誤的“渡假”，系統(tǒng)給出結(jié)果會比較差玲销。下圖例子中“渡假”的搜索結(jié)果都沒有命中標(biāo)題输拇，而標(biāo)題往往是用戶最為關(guān)注的信息，如果標(biāo)題中不含有搜索query關(guān)鍵字贤斜，用戶點擊的欲望也會較低策吠。
在這種情況下猴抹，雖然“渡假”的搜索次數(shù)更多，但是點擊模型給出query分數(shù)會比較低锁荔，而候選詞“度假”的query得分就會高一些蟀给，可以輔助其他糾錯方式完成糾錯。
4.4存在的問題
搜索系統(tǒng)許多功能的召回率和準確率是矛盾的阳堕，但是在query糾錯問題中跋理，準確率往往要求更高。拼音query到漢字query的糾錯恬总，往往會存在較大的轉(zhuǎn)義風(fēng)險前普，不同的類型的拼音轉(zhuǎn)換方式（全拼，模糊全拼壹堰，簡拼拭卿，混拼）有著不同程度的轉(zhuǎn)義風(fēng)險骡湖，召回越大則準確率降低，因此使用全拼較為穩(wěn)妥峻厚。（達觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）
5達觀數(shù)據(jù)搜索系統(tǒng)query糾錯技術(shù)介紹
達觀數(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俗慈，不同策略獨立糾錯。達觀數(shù)據(jù)使用多種糾錯策略遣耍，主要使用拼音糾錯和編輯距離糾錯闺阱，并輔助模糊音形近字二次糾錯等其他糾錯策略。同音策略是用戶輸入的錯誤query和候選糾錯query有相同的拼音舵变。編輯距離策略就是錯誤query和候選query之間編輯距離小于一定閾值酣溃，并配合其他條件進行過濾。
3纪隙，候選詞結(jié)果選擇赊豌。因為每個策略比較獨立，不同策略會給出不同的候選詞绵咱，因此對于候選詞的選取碘饼，每個策略有所不同。不同策略之間悲伶，不同策略內(nèi)部需要使用不同的評估方式艾恼，來選擇最優(yōu)結(jié)果。
達觀科技搜索系統(tǒng)的糾錯模塊包括上述多個策略麸锉，每個策略獨立運行蒂萎，針對不同的領(lǐng)域和業(yè)務(wù)情況，策略優(yōu)先級和權(quán)重可配置淮椰，糾錯松緊度可調(diào)節(jié)五慈。
5.2系統(tǒng)設(shè)計
達觀數(shù)據(jù)EC系統(tǒng)主要分為三部分：數(shù)據(jù)模塊纳寂，離線建庫端及在線檢索端。
5.2.1數(shù)據(jù)模塊
數(shù)據(jù)模塊的主要作用是為后面的離線建庫端和在線檢索端提供數(shù)據(jù)泻拦。
數(shù)據(jù)模塊對搜索log定期進行抽取和統(tǒng)計毙芜，對query進行歸一化后給出query頻次詞典。對數(shù)據(jù)庫信息整理給出自定義詞典争拐。通過爬蟲系統(tǒng)爬取優(yōu)質(zhì)詞條詞典腋粥。
5.2.2離線建庫端
離線建庫端使用數(shù)據(jù)模塊準備好的各種詞典生就糾錯詞典，包括拼音糾錯詞典架曹，編輯距離糾錯詞典等隘冲。根據(jù)配置，對頻次詞典中對超出一定長度query上述操作不處理绑雄。
5.2.3在線檢索端
在線檢索端負責(zé)query實時糾錯展辞，根據(jù)5.1節(jié)的三個步驟進行。如果第一次糾錯query查詢結(jié)果較差万牺，使用擴大召回的方式罗珍，比如二次糾錯、片段糾錯等擴大召回重新糾錯脚粟，進行二次查詢并返回質(zhì)量較高的查詢結(jié)果覆旱。
5.3糾錯效果評估
糾錯效果的好壞從微觀上來講，可以查看搜索日志中無結(jié)果或結(jié)果少的糾錯query以及點擊模型中點擊較少的糾錯query等方式發(fā)現(xiàn)bad case核无，在針對這些bad case出現(xiàn)的原因進行分類總結(jié)扣唱，后續(xù)改進算法。
在宏觀上可以關(guān)注搜索效果評估系統(tǒng)中的MAP和MRR分數(shù)团南，使用AB test画舌，查看使用糾錯模塊后或糾錯算法升級后的帶來的效果提升。
6結(jié)語
一個完善的搜索引擎系統(tǒng)中已慢，糾錯功能是重要的一環(huán)曲聂，對提升用戶體驗及用戶滿意度有很大的幫助，亦能補救大量錯誤query所帶來的流量損失佑惠。達觀數(shù)據(jù)在搜索引擎服務(wù)上有著豐富的行業(yè)經(jīng)驗朋腋，能夠為合作企業(yè)提供高質(zhì)量的搜索服務(wù)，充分挖掘企業(yè)的數(shù)據(jù)價值膜楷。（達觀數(shù)據(jù)聯(lián)合創(chuàng)始人高翔）
