達觀資料搜尋引擎的Query自動糾錯技術和架構

1 背景

如今，搜尋引擎是人們的擷取資訊最重要的方式之一，在搜尋頁面小小的輸入框中，隻需輸入幾個關鍵字，就能找到你感興趣問題的相關網頁。搜尋巨頭Google，甚至已經使Google這個創造出來的單詞成為動詞，有問題Google一下就可以。在國内，百度也同樣成為一個動詞。除了通用搜尋需求外，很多垂直細分領域的搜尋需求也很旺盛，比如電商網站的産品搜尋，文學網站的小說搜尋等。面對這些需求，達觀資料(www.datagrand.com)作為國内提供中文雲搜尋服務的高科技公司，為合作夥伴提供高品質的搜尋技術服務，并進行搜尋服務的統計分析等功能。（達觀資料聯合創始人高翔）

搜尋引擎系統最基本最核心的功能是資訊檢索，找到含有關鍵字的網頁或文檔，然後按照一定排序将結果給出。在此基礎之上，搜尋引擎能夠提供更多更複雜的功能來提升使用者體驗。對于一個成熟的搜尋引擎系統，使用者看似簡單的搜尋過程，需要在系統中經過多個環節，多個子產品協同工作，才能提供一個讓人滿意的搜尋結果。其中拼寫糾錯（Error Correction，以下簡稱EC）是使用者比較容易感覺的一個功能，比如百度的糾錯功能如下圖所示：

圖 1：百度糾錯功能示例

EC其實是屬于Query Rewrite（以下簡稱QR）子產品中的一個功能，QR子產品包括拼寫糾錯，同義改寫，關聯query等多個功能。QR子產品對于提升使用者體驗有着巨大的幫助，對于搜尋品質不佳的query進行改寫後能傳回更好的搜尋結果。QR子產品内容較多，以下着重介紹EC功能。

在搜尋引擎中，我們将使用者輸入的關鍵字查詢叫做query，使用者希望得到和輸入query相關的品質較好的網頁或文檔，這個“好”字定義有多種衡量方式，最簡單的标準就是那些對使用者幫助最大最具吸引力的結果能夠排到前列，搜尋工程師們也在努力通過各種算法的提升來達到這個目的。但是往往出于各種原因，使用者輸入的query本身品質不高或是錯誤的，如果搜尋引擎不對這種錯誤進行修正彌補，會導緻召回錯誤的結果，或者結果數少甚至沒有結果。當使用者看到搜尋結果較差較少時，如果能意識到自己的query錯誤，對query進行修正再次檢索，也許能找到想要的結果。但有時使用者也不知道自己的query錯在哪裡，這個時候就會非常着急。筆者之前從事搜尋相關工作時，剛開始搜尋系統不支援糾錯功能，結果收到使用者大量的吐槽和投訴，說明沒有糾錯功能的搜尋系統會大大降低使用者體驗，不僅如此，這些錯誤query檢索還浪費大量的流量。當開發完畢并在搜尋系統中使用EC子產品後，糾錯成功的流量占到總流量的2%，不僅提升了使用者體驗，還能夠挽回流量損失，提升使用者粘度。

2 EC常見錯誤

EC應該怎麼做？首先我們看一下常見的query錯誤都有哪些。

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

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

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

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

3 Query出錯的原因分析

目前最普遍的中文輸入方式是拼音輸入法，使用者輸入拼音，輸入法給出候選詞，但是由于使用者誤選或無需要候選詞時，query就有可能出錯。雖然相較之前智能輸入法現在已經足夠強大，但仍有一些新的産品、小說、影視作品，輸入法可能會覆寫不到。比如一些新奇網絡詞彙的出現，傳統的詞典已經無法包括這些詞。還有一些較為陌生的詞，比如“芈月傳”，很多人都是聽朋友介紹很好看，結果去搜尋引擎中搜尋相關資訊，很多人隻知道第一個字發音是“mi”，但實際是哪個字卻不确定。

除此之外，使用者搜尋時也會從網頁或其他文檔上複制粘貼文字來搜尋，導緻搜尋query不完整或帶入其他字元，甚至打字太快也是錯誤query輸入的原因。

4 Query糾錯方案

英文拼寫糾錯已經有較長的曆史，對于英文糾錯的研究較多。英文糾錯是中文糾錯的重要基礎，其中很多算法思想同樣适用于中文。是以首先介紹一下英文糾錯問題。在介紹具體糾錯方案前，先介紹兩個重要的的概念：編輯距離，n元文法模型。

4.1 基礎概念

4.1.1編輯距離

編輯距離是兩個字元串之間，由一個轉換成另外一個所需要的最少操作次數，允許的操作包括字元替換，增加字元，減少字元，颠倒字元。舉例來講，apple和apply的編輯距離是1，access和actress的編輯距離是2，arrow和brown的編輯距離是3，編輯距離的計算操作過程如下圖所示：

圖 3：編輯距離計算過程

4.1.2 n元文法模型

語言模型（language mode）在基于統計模型的語音識别，機器翻譯，漢語自動分詞和句法分析中有着廣泛的應用，目前采用的主要是n元文法模型（n-gram model）。

一個語言模型建構字元串的機率分布p(W)，假設p(W)是字元串作為句子的機率，則機率由下邊的公式計算：

公式 1：語言模型

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

w1w2...wi-1稱作曆史，如果w共有5000個不同的詞，i=3的時候就有1250億個組合，但是訓練資料或已有語料庫資料不可能有這麼多組合，并且絕大多數的組合不會出現，是以可以将w1w2...wi-1根據規則映射到等價類，最簡單的方式就是取wi之前n-1個曆史，根據馬爾科夫假設，一個詞隻和他前面n-1個詞相關性最高，這就是n元文法模型。

公式 2：n元文法模型

通常用的n元文法模型包括unigram，bigram，trigram，其中unigram表示這個詞和前面的詞無關，彼此獨立，計算公式如下：

公式 3：unigram文法模型

Bigram表示一個詞隻和它前面一個詞有關，計算公式如下：

公式 4：bigram文法模型

4.2 英文糾錯

4.2.1 Non-word糾錯

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

糾錯過程就是找出和錯詞最相似的一些候選詞，然後從中選出正确的糾錯詞。候選詞可以使用上面介紹的編輯距離從語料庫中找出。統計指出，80%的錯誤詞的編輯距離是1，并且幾乎所有的錯誤的編輯距離在2以内。

在候選詞中找到最終的糾錯詞，比較簡單的方法可以根據候選詞的權重進行排序，給出權重最高的詞作為糾錯詞，這個權重可以是人工标注的結果，也可以是語料庫統計的詞頻或其他方式。相對複雜的候選詞選擇方法可以使用統計模型計算，比如噪聲信道模型。

噪聲信道模型（Noisy Channel Model）最早是香農為了模型化信道的通信問題，在資訊熵概念上提出的模型，目标是優化噪聲信道中信号傳輸的吞吐量和準确率。對于自然語言處理而言，信道噪聲模型如下圖，其中I表示輸入，O表示經過噪聲信道後的輸出，I'表示經過解碼後最有可能的輸入。

圖 4：信道噪聲模型框圖

在自然語言進行中，很多問題都可以歸結為給定輸出O（有可能包括錯誤資訊），在所有可能的輸入I中找到最可能的那一個作為輸入I'。

自然語言進行中的機器翻譯，詞性标注，語音識别等多個問題都可以使用信道噪聲模型來解決，對于糾錯問題也可以使用信道噪聲模型來解決，相應的求解問題可以用公式表達：

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

其中p(x|w)是正确的詞編輯成為錯誤詞x的轉移機率，包括删除（deletion）、增加（insertion）、替換（substitution）和颠倒（transposition）四種轉移矩陣，這個轉移矩陣的機率可以通過統計大量的正确詞和錯誤詞對來得到，轉移矩陣的計算公式如下：

公式 6：轉移矩陣公式計算

将轉移矩陣計算公式代入公式5的噪聲信道模型公式中，根據不同候選詞和糾錯詞之間的變換關系選擇轉移矩陣類型，就能得到機率最大的候選詞。

4.2.2 Real-word糾錯：

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

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

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

上圖中，每一數列是這個位置詞的候選詞集合，其中每個詞的狀态轉移機率可以通過語言模型在語料庫中統計求得。

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

4.3 中文糾錯

中文糾錯以英文糾錯為基礎但卻有所不同。在中文中，一般情況下錯誤詞和正确詞的長度是相同的，隻是指定位置上的某一個字有誤，是以狀态轉移矩陣隻有替換一種。其次是中文詞語往往較短，即使編輯距離隻有1，就會有大量的候選詞，存在較大的轉義風險。中文使用拼音作為文字的發音，每個字都有固定的發音（多音字除外），而拼音輸入法占據中文輸入方式的主導地位，導緻錯誤query中的别字同音但字形錯誤。是以中文糾錯以拼音為基礎，編輯距離等其他方式為輔的政策。

4.3.1候選詞集合的擷取

對于錯誤的詞的候選詞集合，可以通過資料自動挖掘來生成。英文候選詞集合一般通過編輯距離來獲得，而中文候選詞集合使用和錯誤詞有相同的拼音的詞組成，比如“嗒衣”這個錯詞的拼音是“dayi”, 則可以通過事先挖掘好的拼音是“dayi”的詞組成候選集，比如<dayi:大一，大衣，大意，大姨，搭衣，答疑..>。

4.3.2候選詞的選擇

對于糾錯候選詞的選擇就是一個對候選詞進行排序，按照一定的排序規則，把排名最高的候選詞作為最佳糾錯結果傳回。排序規則可以使用詞頻等多種特征，候選詞按照這些特征規則進行排序，傳回權重較高的詞。

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

相對于單獨一個詞的query，由多個詞組成的query糾錯相對更加精準，每個詞存在上下文關系限制，整個query的意圖更加明确。通過對query分詞，查找每個詞的候選詞集合，然後使用和英文Real-word糾錯類似的方式糾錯。

除了搜尋日志query和語料庫的統計挖掘，搜尋系統中的session分析和點選模型提供的資料也能夠為query糾錯服務。搜尋session指的是使用者在某一個時間段内的搜尋行為，如果把搜尋日志按照時間排序，對于某一個使用者的搜尋日志來說，可以看到使用者的搜尋行為是分段的，每段之間往往有較為明顯的間隔，每一段我們稱為一個搜尋session。一般來說，使用者在一個session内的搜尋行為都是為了解決一個問題，是以在此session内使用者輸入的query往往都是相關的。

點選模型中的一些統計資料可以判斷一個搜尋query品質的高低，品質高的query往往會給出較好的結果，使用者點選的欲望更高。舉例來說，“度假”（正确）“渡假”（錯誤）這兩個query，假設使用者輸入較多的是錯誤的“渡假”，系統給出結果會比較差。下圖例子中“渡假”的搜尋結果都沒有命中标題，而标題往往是使用者最為關注的資訊，如果标題中不含有搜尋query關鍵字，使用者點選的欲望也會較低。

圖 6：錯誤query“渡假”的結果少，品質差

圖 7：正确query“度假”的結果多，品質好

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

4.4 存在的問題

搜尋系統許多功能的召回率和準确率是沖突的，但是在query糾錯問題中，準确率往往要求更高。拼音query到漢字query的糾錯，往往會存在較大的轉義風險，不同的類型的拼音轉換方式（全拼，模糊全拼，簡拼，混拼）有着不同程度的轉義風險，召回越大則準确率降低，是以使用全拼較為穩妥。（達觀資料聯合創始人高翔）

5 達觀資料搜尋系統query糾錯技術介紹

達觀資料在搜尋引擎等大資料技術上有着深厚的積累，搜尋引擎提供多種功能及服務，其中糾錯子產品是比較重要的功能之一。

5.1 糾錯過程

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

1， Query糾錯判斷。對于常見錯誤，例如常見的拼寫錯誤，使用事先挖掘好的錯誤query字典，當query在此字典中時糾錯。如果使用者輸入的query查詢無結果或結果較少于一定門檻值時，嘗試糾錯，可以根據不同領域的政策和容忍度，配置最少結果數門檻值。

2，不同政策獨立糾錯。達觀資料使用多種糾錯政策，主要使用拼音糾錯和編輯距離糾錯，并輔助模糊音形近字二次糾錯等其他糾錯政策。同音政策是使用者輸入的錯誤query和候選糾錯query有相同的拼音。編輯距離政策就是錯誤query和候選query之間編輯距離小于一定門檻值，并配合其他條件進行過濾。

3，候選詞結果選擇。因為每個政策比較獨立，不同政策會給出不同的候選詞，是以對于候選詞的選取，每個政策有所不同。不同政策之間，不同政策内部需要使用不同的評估方式，來選擇最優結果。

達觀科技搜尋系統的糾錯子產品包括上述多個政策，每個政策獨立運作，針對不同的領域和業務情況，政策優先級和權重可配置，糾錯松緊度可調節。

5.2 系統設計

達觀資料EC系統主要分為三部分：資料子產品，離線建庫端及線上檢索端。

圖 8：EC系統子產品構成

5.2.1資料子產品

資料子產品的主要作用是為後面的離線建庫端和線上檢索端提供資料。

資料子產品對搜尋log定期進行抽取和統計，對query進行歸一化後給出query頻次詞典。對資料庫資訊整理給出自定義詞典。通過爬蟲系統爬取優質詞條詞典。

5.2.2離線建庫端

離線建庫端使用資料子產品準備好的各種詞典生就糾錯詞典，包括拼音糾錯詞典，編輯距離糾錯詞典等。根據配置，對頻次詞典中對超出一定長度query上述操作不處理。

5.2.3線上檢索端

線上檢索端負責query實時糾錯，根據5.1節的三個步驟進行。如果第一次糾錯query查詢結果較差，使用擴大召回的方式，比如二次糾錯、片段糾錯等擴大召回重新糾錯，進行二次查詢并傳回品質較高的查詢結果。

5.3 糾錯效果評估

糾錯效果的好壞從微觀上來講，可以檢視搜尋日志中無結果或結果少的糾錯query以及點選模型中點選較少的糾錯query等方式發現bad case，在針對這些bad case出現的原因進行分類總結，後續改進算法。

在宏觀上可以關注搜尋效果評估系統中的MAP和MRR分數，使用AB test，檢視使用糾錯子產品後或糾錯算法更新後的帶來的效果提升。

6結語

一個完善的搜尋引擎系統中，糾錯功能是重要的一環，對提升使用者體驗及使用者滿意度有很大的幫助，亦能補救大量錯誤query所帶來的流量損失。達觀資料在搜尋引擎服務上有着豐富的行業經驗，能夠為合作企業提供高品質的搜尋服務，充分挖掘企業的資料價值。（達觀資料聯合創始人高翔）

技術猶如滿天繁星，指引我們前行。（題圖筆者攝于Mt Cook）

了解更多大資料技術和服務盡請通路達觀資料(www.datagrand.com)