1.2.3 對索引進行搜索

上面我們已經可以查找到包含關鍵詞的相關文檔了，但它還不能滿足實際搜索的要求。如果結果只有幾個，當然沒有問題，全部顯示就是了。但在實際應用中，搜索引擎需要返回幾十萬，甚至百萬、千萬級的結果。我們怎樣才能將最相關的文檔顯示在最前面呢？這也是下面需要探討的問題。

1．用戶輸入查詢語句

目前，搜索引擎均提供自然語言搜索以及布爾表達式高級搜索，所以查詢語句也是遵循一定的語法結構。比如我們可以輸入查詢語句“search AND using NOT image”，它搜索包含search和using但不包含image的文檔。

2．對查詢語句進行詞法分析、語法分析、語言處理

詞法分析用來提取查詢詞以及布爾關鍵字，上面的查詢語句提取出的查詢詞為search using image，布爾關鍵字是AND和NOT。語法分析會將詞法分析的提取結果生成一棵語法樹。上例形成的語法樹如圖1-5所示。

語言處理與創建索引時的語言處理過程幾乎相同。如圖1-6所示，上例中的using將轉換為use。

3．搜索索引，返回符合上述語法樹的結果

首先，在反向索引中分別找出包含search、use和image的文檔鏈表。然后，將包含search和use的文檔鏈表合并，得到既包含search，又包含use的文檔鏈表。接著，在上一步的結果中去除包含image的文檔鏈表，最終的文檔鏈表就是符合上述語法樹的結果。

4．對結果進行相關性排序

雖然在上一步中我們得到了想要查找的文檔，但這些文檔并未按照與查詢語句的相關性進行排序，并不是我們最終想要的結果。那怎樣才能將查找結果按相關性進行排序呢？首先，把查詢語句也視為一個由若干詞組成的短小文檔，那么查詢語句與相應文檔的相關性問題就轉變成了文檔之間的相關性問題。毫無疑問，文檔主題近似程度高的，其相關性必然強；文檔主題近似程度低的，其相關性必然弱。那進一步思考一下，什么又是決定文檔間相關性的主要因素？想必讀者都讀過或寫過論文，是否留意到每篇論文都有“關鍵詞”這一項？“關鍵詞”是能夠反映論文主題的詞或詞組。也就是說，論文中每個詞對論文主題思想的表達程度是不相同的。換個說法，文檔中的每個詞對其主題思想表達的權重是不同的，正是這些不同權重的詞構成了文檔的主題。

有兩個主要因素會影響一個詞在文檔中的重要性。一是詞頻率（Term Frequency，tf），表示一個詞在此文檔中出現的次數，它的值越大，說明這個詞越重要。二是文檔頻率（Document Frequency，df），表示多少文檔中包含這個詞，它的值越大，說明這個詞越不重要。一個詞的權重可以使用式（1-1）進行計算：

（1-1）

在上述公式中，W_t,d表示詞t在文檔d中的權重，tf_t,d表示詞t在文檔d中出現的頻率，n表示文檔的總數，df_t表示包含詞t的文檔數量。

怎樣才能度量文檔的相似度呢？第一步，把文檔中每個詞的權重組成一個向量，DocumentVector={weight1, weight2, …, weightN}。把查詢語句也看作一個簡單的文檔，將其中的每個詞的權重也組成一個向量，QueryVector={weight1, weight2, …, weightN}。第二步，將所有查詢出的文檔向量和查詢語句向量取并集，用并集元素的個數N統一各向量長度，如果一個文檔中不包含某個詞，那么該詞的權重為0。第三步，把所有統一后的向量放到一個N維空間中，每個詞是一維，如圖1-7所示。

如圖1-8所示，文件向量間存在一定的夾角。我們可以通過計算夾角余弦值的方法來表示它們之間的相似程度。因為夾角越小，余弦值越大，也就是說文檔向量夾角的余弦值越接近，文檔也越相近。

相關性的計算公式如下：

（1-2）

下面梳理一下上述的索引、搜索過程，如圖1-9所示。

詞法分析和語言處理過程將一系列文本轉化為若干個詞，然后索引創建過程將這些詞生成詞典和倒排索引，索引寫程序將其寫入索引庫。當用戶輸入查詢語句進行搜索時，首先進行詞法分析和語言處理，將查詢語句分解成一系列詞，而后將其輸入語法分析過程生成查詢語法樹。索引讀程序將反向索引表由索引庫讀入內存，搜索過程在反向索引表中查找與查詢語法樹中每個詞一致的文檔鏈表，并對其進行相應的布爾運算，得到結果文檔集。將結果文檔集與查詢語句的相關性進行排序，并將生成結果返回給用戶。