搜尋引擎中的粒度問題

傳統的搜尋引擎的定義，是指一種對于指定的查詢（Query），能夠傳回與之相關的文檔集合（Documents）的系統。而百度将這個定義更加豐富化，即搜尋引擎能夠幫助人們更友善的找到所求。這裡的“所求”，比“文檔”更加寬泛和豐富，比如一個關于天氣的查詢，直接傳回一個天氣預報的視窗，而非一篇關于天氣的文檔；再如一個關于小遊戲的查詢，直接傳回這個小遊戲的Flash頁面而非簡單的介紹性的文字。

百度對Query深刻的了解，源于自然語言處理技術在其中發揮的巨大作用。對搜尋引擎而言，文本切分是最基礎也是最重要的自然語言問題之一。今天，我們就來談談文本切分粒度與搜尋引擎的關系。

本文後續章節組織如下：第二節介紹什麼是文本的粒度，第三節講述搜尋引擎的基本原理與文本切分粒度的關系，第四節深入探讨粒度的屬性與檢索相關性計算，第五節小結。

什麼是文本的粒度？我們用什麼來衡量文本粒度？在回答這些問題前，讓我們先看看以下幾組詞彙：

纏綿、崎岖、葡萄、乒乓

綠茶、籃球、紅色、滑鼠墊、起重機

打球、跳繩、炒菜、登山

筆記本電腦、高清機頂盒、IP電視

但是、然後、如果、非常

步步驚心、家的n次方、一個人的精彩

百度線上網絡技術（北京）有限公司、清華大學

張學友、趙傳、工藤新一、裡奧内爾·安德雷斯·梅西

……

這幾組詞彙中，哪些的粒度大，哪些的粒度小？

不管在傳統的語言學領域，還是在自然語言處理領域，都沒有對粒度下一個清晰準确的定義。但是就搜尋引擎而言，我們不妨這樣定義：粒度是衡量文本所含資訊量的大小。文本含資訊量多，粒度就大，反之就小。有了這個原則，我們就很容易判斷文本粒度大小了。像“纏綿”，“崎岖”，“葡萄”這些詞，雖然有兩個字組成，但是僅表達一個意思，這些詞的粒度是小的。而“籃球”，“滑鼠墊”等詞，是由簡單詞合成的，雖然也隻有一個意思，但還可以拆分，如“籃”和“球”，“滑鼠”和“墊”。這類詞，粒度稍微大一些。而“筆記本電腦”，“高清機頂盒”這樣的詞，粒度就更大了。

專名是一類比較特殊的詞，盡管所含字數很多，但其實隻表達一個意思，如“步步驚心”，“家的n次方”這樣的電影、電視劇的名稱，粒度是很小的。機構名、人名等屬于有内部結構的專名，比電影名的粒度稍大一些。

顯然易見，我們在讨論文本粒度時，理想的方式是從語義角度出發，合理的分析和判斷。然而以上我們僅對粒度做了定性的分析，為粒度找一個合适的度量機關和計算方法，是百度人一直追求的目标。

文字檢索系統，是搜尋引擎最簡單的實作方式。通過傳回包含關鍵字的頁面，來滿足使用者的檢索需求。形式化的表達就是給定一系列關鍵字集合K,要求傳回所有包含關鍵字的文檔D,對D中的任意一個文檔d，包含K中的任意一個關鍵字k。

一般我們采用反向索引的方式來實作這個系統。所謂反向索引，就是對關鍵字建立索引，記錄包含這個關鍵字的文檔集合D。對于請求的關鍵字集合，找出所有關鍵字對應的索引，并對索引求交，最後傳回同時存在于所有索引中的文檔。

在百度，我們不僅允許使用者輸入關鍵字，也可以輸入任何長度在一定範圍内的文本。此時我們需要對文本做一定處理，切分成一系列關鍵字，進而能夠從反向索引中找出對應的文檔。

那麼為什麼要對輸入文本做切分，如果不切分會有什麼問題？

我們可以想象一下，如果不對輸入文本做切分，直接用輸入文本去做比對，會怎麼樣？首先，得到的結果會非常少，因為直接用全部文本比對，就失去了靈活性，對結果限制的非常死，必須完全比對才能滿足要求；其次，系統性能會非常差，因為需要對所有長度的文本都建立索引，這是指數級的，在實際系統中根本不可能實作。再考慮一下另一個極端？我們對輸入文本做單字切分，結果又是怎樣？我們會得到大量無關的頁面，不僅浪費系統性能，對相關性計算也造成了巨大的壓力。

是以，我們需要對文本做一個合适的切分。

無論是建立反向索引、還是處理輸入文本，我們都需要對文本做切分，切出合适的關鍵字出來。為了能夠使使用者對查詢結果滿意，搜尋引擎需要什麼樣的粒度？讓我們先看一下下面幾個例子：

1. Q:“北京地圖” P1:“北京市地圖” P2：“北京城市地圖”

2. Q:“鬧太套是神馬意思”, P:”A：神呐，我騎不了這烈馬。B：鬧太套！”

3. Q:“獸獸門” P:“獸獸豔照門”

4. Q1:“工業園” Q2:“園區” P:“工業園區”

5. Q：“ip電視” P1:“ip電視的曆史” P2:“電視銷售…您的IP是xxx”

注：Q表示query，P表示頁面中包含Q的内容

Case1，要求query能找到P1和P2這樣的結果，就必須對P1和P2都切出“北京”這個詞來。Case2，必須把”神馬”切為一個詞，否則會召回P這樣不相關的結果。Case3，不能把Q中的“獸獸門“切為一個詞，而需要切除“獸獸”，否則就召不回”獸獸豔照門”這個結果。Case4中，對“工業園區”這樣的頁面，必須同時切出“工業園”和“園區”這兩個重疊的詞彙，才能保證Q1和Q2都能召回。Case5與Case2類似，如果把ip和電視分開切分，将召回P2這樣不相關的結果。

以上幾個case，基本上概括了搜尋引擎對切分粒度的要求，我們可以從兩方面來描述：1）影響召回 2）影響相關性

以上從使用者滿意度的角度，讨論了搜尋引擎與粒度的關系，當然，這是最基本的要求，在第四節我們還會對文本的粒度問題做更深入的分析。

顯而易見，粒度越小，召回就越多，建立反向索引時，索引的長度就越長；粒度的層次越多，索引的數量就越多。一個多，一個長，就對搜尋系統的性能構成了極大的考驗。

一般而言，大型搜尋引擎的索引都采用分布式系統。不同文本的索引，被某種hash算法“配置設定”到了某台機器。理論上講，索引的數量的增長，隻會造成所需機器的增長，而對整體系統性能的消耗影響比較小。是以一般搜尋引擎會從成本效益的角度來考慮索引數量與機器數量的折衷，也就是召回與硬體投入的折衷。粒度分析對于折衷的成本效益也有一定的貢獻，在粒度層次裡，當粒度逐漸變小的過程中，我們并不一定對所有小粒度詞都建索引，而是選擇“更有可能召回相關結果”的小粒度詞。詞彙的什麼性質決定了“更有可能召回相關結果”？我們同樣會在第四節讨論。

在第三節中我們反複提到：一般情況下，粒度越大，相關性越好，召回越差；粒度越小，相關性越差，召回越好。在搜尋引擎中，如果做到折衷呢?基本的原則是，在系統性能可接受的前提下，盡量多召回有效結果，計算相關性時，将最相關的排在前面。

我們如何做到将合理減小粒度，增加有效召回，又如何做到将最好的排在最前呢？這裡涉及到兩個問題：緊密度與重要性。

既然粒度是衡量文本所含資訊量的大小，那麼緊密度就是描述文本所含資訊緊密程度的量。再說的通俗一些，緊密度就是資訊被人們表達和接受的穩定程度。穩定有兩種解釋，第一，穩定是相對于臨時而言的。一般來說，如果資訊是因為某些因素臨時組合在一起，那就是不穩定的，即不緊密。比如許多動賓結構的短語（“過馬路”，“踢足球”），定中結構的短語（“紅蘋果”，“豪華轎車”）。第二，穩定是相對于順序不固定而言的。如果同樣一個資訊，内部的子資訊順序可以互換，那麼這個詞彙就不穩定，即不緊密。比如一些大粒度的詞彙“滑鼠護腕墊”、“護腕滑鼠墊”。

由此可見，我們根據詞彙的緊密程度，可以将結果中表述與查詢表述的一緻程度聯系起來，作為計算相關性的一個因素。同樣，我們也可以将緊密度作為減小粒度的依據之一，詞彙越不緊密，我們就有理由将其拆分為更小的粒度。

短語的重要性，其實是短語子成分的重要性，有很多定義。其中一種被普遍接受的定義為其占短語完整含義的比例。一般情況下，偏正結構短語中，“正”的部分比較重要，比如“綠茶”中的“茶”，但也有例外，如“珊瑚蟲”中的“珊瑚”。而主謂、動賓短語一般來說，都比較重要，如“打球”，“你說”。是以，短語的子成分重要性，不能僅靠文法來識别，而應綜合各種因素來确定。

假設有了詞彙的子成分重要性，那麼就可以幫助判斷将詞彙粒度變小後的語義損失風險程度（注意，這裡使用了“語義損失”，而不是“轉義”，想一想為什麼）。這也就回答了第四節末尾的問題：語義損失越小，越有可能召回相關結果。

本文介紹了搜尋引擎中的粒度問題，重點讨論了搜尋引擎與短語切分粒度的關系，并進一步探讨了短語的兩個重要性質——緊密度和重要性。通過本文，讀者應該能夠大緻明白搜尋引擎中關于粒度的種種。當然，本文隻是對搜尋引擎的粒度問題開了一個頭，怎麼合理的處理好粒度、在不同場合使用何種粒度，都是需要我們繼續深入研究的。

by xinzhou

【本文首發于：搜尋研發部官方部落格】http://stblog.baidu-tech.com/?p=1429

【關注百度技術沙龍】