引言：

在信息大爆炸的今天，有了搜索引擎的幫助，使得我們能夠快速，便捷的找到所求。提到搜索引擎，就不得不說VSM模型，說到VSM，就不得不聊倒排索引。可以毫不夸張的講，倒排索引是搜索引擎的基石。

VSM檢索模型

VSM全稱是Vector Space Model(向量空間模型)，是IR(Information Retrieval信息檢索)模型中的一種，由于其簡單，直觀，高效，所以被廣泛的應用到搜索引擎的架構中。98年的Google就是憑借這樣的一個模型，開始了它的瘋狂擴張之路。廢話不多說，讓我們來看看到底VSM是一個什么東東。

在開始之前，我默認大家對線性代數里面的向量(Vector)有一定了解的。向量是既有大小又有方向的量，通常用有向線段表示，向量有：加、減、倍數、內積、距離、模、夾角的運算。

文檔(Document)：一個完整的信息單元，對應的搜索引擎系統里，就是指一個個的網頁。

標引項(Term)：文檔的基本構成單位，例如在英文中可以看做是一個單詞，在中文中可以看作一個詞語。

查詢(Query)：一個用戶的輸入，一般由多個Term構成。

那么用一句話概況搜索引擎所做的事情就是：對于用戶輸入的Query，找到最相似的Document返回給用戶。而這正是IR模型所解決的問題：

信息檢索模型是指如何對查詢和文檔進行表示，然后對它們進行相似度計算的框架和方法。

舉個簡單的例子：

現在有兩篇文章(Document)分別是 “春風來了，春天的腳步近了” 和 “春風不度玉門關”。然后輸入的Query是“春風”，從直觀上感覺，前者和輸入的查詢更相關一些，因為它包含有2個春，但這只是我們的直觀感覺，如何量化呢，要知道計算機是門嚴謹的學科^_^。這個時候，我們前面講的Term和VSM模型就派上用場了。

首先我們要確定向量的維數，這時候就需要一個字典庫，字典庫的大小，即是向量的維數。在該例中，字典為{春風,來了,春天, 的,腳步,近了,不度,玉門關} ，文檔向量，查詢向量如下圖：

VSM模型示例

PS:為了簡單起見，這里分詞的粒度很大。

將Query和Document都量化為向量以后，那么就可以計算用戶的查詢和哪個文檔相似性更大了。簡單的計算結果是D1和D2同Query的內積都是1，囧。當然了，如果分詞粒度再細一些，查詢的結果就是另外一個樣子了，因此分詞的粒度也是會對查詢結果（主要是召回率和準確率）造成影響的。

上述的例子是用一個很簡單的例子來說明VSM模型的，計算文檔相似度的時候也是采用最原始的內積的方法，并且只考慮了詞頻(TF)影響因子，而沒有考慮反詞頻(IDF)，而現在比較常用的是cos夾角法，影響因子也非常多，據傳Google的影響因子有100+之多。
大名鼎鼎的Lucene項目就是采用VSM模型構建的，VSM的核心公式如下（由cos夾角法演變，此處省去推導過程）

VSM模型公式

從上面的例子不難看出，如果向量的維度(對漢語來將，這個值一般在30w-45w)變大，而且文檔數量(通常都是海量的)變多，那么計算一次相關性，開銷是非常大的，如何解決這個問題呢？不要忘記了，我們這節的主題就是 倒排索引，主角終于粉墨登場了！！！

倒排索引

倒排索引非常類似我們前面提到的Hash結構。以下內容來自維基百科：

倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統中最常用的數據結構。

有兩種不同的反向索引形式：

• 一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表。
• 一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。

后者的形式提供了更多的兼容性（比如短語搜索），但是需要更多的時間和空間來創建。

由上面的定義可以知道，一個倒排索引包含一個字典的索引和所有詞的列表。其中字典索引中包含了所有的Term(通俗理解為文檔中的詞)，索引后面跟的列表則保存該詞的信息(出現的文檔號，甚至包含在每個文檔中的位置信息)。下面我們還采用上面的方法舉一個簡單的例子來說明倒排索引。

例如現在我們要對三篇文檔建立索引(實際應用中，文檔的數量是海量的)：

文檔1(D1)：中國移動互聯網發展迅速

文檔2(D2)：移動互聯網未來的潛力巨大

文檔3(D3)：中華民族是個勤勞的民族

那么文檔中的詞典集合為：{中國，移動，互聯網，發展，迅速，未來，的，潛力，巨大，中華，民族，是，個，勤勞}

建好的索引如下圖：

倒排索引

在上面的索引中，存儲了兩個信息，文檔號和出現的次數。建立好索引以后，我們就可以開始查詢了。例如現在有一個Query是”中國移動”。首先分詞得到Term集合{中國，移動}，查倒排索引，分別計算query和d1,d2,d3的距離。有沒有發現，倒排表建立好以后，就不需要在檢索整個文檔庫，而是直接從字典集合中找到“中國”和“移動”，然后遍歷后面的列表直接計算。

對倒排索引結構我們已經有了初步的了解，但在實際應用中還有些需要解決的問題(主要是由海量數據引起的)。筆者列舉一些問題，并給出相應的解決方案，拋磚以引玉，希望大家可以展開討論：

1.左側的索引表如何建立?怎么做才能最高效？

可能有人不假思索回答：左側的索引當然要采取hash結構啊，這樣可以快速的定位到字典項。但是這樣問題又來了，hash函數如何選取呢？而且hash是有碰撞的，但是倒排表似乎又是不允許碰撞的存在的。事實上，雖然倒排表和hash異常的相思，但是兩者還是有很大區別的，其實在這里我們可以采用前面提到的Bitmap的思想，每個Term(單詞)對應一個位置(當然了，這里不是一個比特位)，而且是一一對應的。如何能夠做到呢，一般在文字處理中，有很多的編碼，漢字中的GBK編碼基本上就可以包含所有用到的漢字，每個漢字的GBK編碼是確定的，因此一個Term的”ID”也就確定了，從而可以做到快速定位。注：得到一個漢字的GBK號是非常快的過程，可以理解為O(1)的時間復雜度。

2.如何快速的添加刪除更新索引？

有經驗的碼農都知道，一般在系統的“做加法”的代價比“做減法”的代價要低很多，在搜索引擎中中也不例外。因此，在倒排表中，遇到要刪除一個文檔，其實不是真正的刪除，而是將其標記刪除。這樣一個減法操作的代價就比較小了。

3.那么多的海量文檔，如果存儲呢？有么有什么備份策略呢？

當然了，一臺機器是存儲不下的，分布式存儲是采取的。一般的備份保存3份就足夠了。

好了，倒排索引終于完工了，不足的地方請指正。謝謝

做人要厚道，轉載請注明出處：http://diducoder.com/mass-data-topic-8-inverted-index.html