如何建立一個簡單的倒排索引？

Question

我想建立一個沒有任何API的搜索引擎的簡單索引函數，比如Lucene。在倒排索引中，我只需要記錄每個單詞的基本信息，例如， docID，位置和頻率。

現在，我有幾個問題：

1. 通常用於建立倒排索引什麼樣的數據結構？多維列表？

2. 建立索引後，如何將它寫入文件？文件中的格式是什麼？像桌子一樣？像在紙上繪製索引表一樣？

Answer 1

你可以看到一個非常簡單的倒排索引實現和搜索TinySearchEngine。

關於第一個問題，如果你想建立一個簡單的（在內存中）倒排索引的簡單的數據結構是一個散列映射是這樣的：

val invertedIndex = new collection.mutable.HashMap[String, List[Posting]] 

或Java去年秋季：

HashMap<String, List<Posting>> invertedIndex = new HashMap<String, List<Postring>>(); 

該散列將每個詞/詞/標記映射到一個Postings列表。甲Posting只是表示文檔內的單詞的出現的對象：

case class Posting(docId:Int, var termFrequency:Int) 

索引一個新的文檔只是一個標記化它（在令牌/字分離）的物質和對於每個令牌插入一個新的過帳在哈希映射的正確列表中。當然，如果該特定docId中的該術語已經存在，您可以增加termFrequency。還有其他方法可以做到這一點。對於內存倒排索引，這是可以的，但對於磁盤索引，您可能希望將Postings一次插入正確的termFrequency，而不是每次更新一次。

關於你提到的第二個問題，通常有兩種情況：

（1）你有一個（幾乎）不可變的指數。您只需索引所有數據一次，如果您有新數據，您可以重新索引。例如，一小時內不需要實時或索引多次。 （2）新文件一直到達，您需要儘快搜索新抵達的文件。

對於情況（1），你可以有至少2個文件：

1 - 倒排索引文件。它列出了每個術語全部Postings（docId/termFrequency對）。這裏用純文本表示，但通常以二進制數據存儲。

Term1<docId1,termFreq><docId2,termFreq><docId3,termFreq><docId4,termFreq><docId5,termFreq><docId6,termFreq><docId7,termFreq> 
Term2<docId3,termFreq><docId5,termFreq><docId9,termFreq><docId10,termFreq><docId11,termFreq> 
Term3<docId1,termFreq><docId3,termFreq><docId10,termFreq> 
Term4<docId5,termFreq><docId7,termFreq><docId10,termFreq><docId12,termFreq> 
... 
TermN<docId5,termFreq><docId7,termFreq> 

2-抵消文件。爲每個項存儲偏移量，以在倒排索引文件中查找其反轉列表。這裏我用字符表示偏移量，但通常會存儲二進制數據，所以偏移量將以字節爲單位。該文件可以在啓動時加載到內存中。當你需要查找一個詞語倒排列表時，你可以查找它的偏移量並從文件中讀取倒排列表。

Term1 -> 0 
Term2 -> 126 
Term3 -> 222 
.... 

隨着這2個文件你可以（而且通常會）有文件（S）來存儲每個學期IDF和每個文檔的規範。 （2），我將嘗試簡要說明Lucene（因此Solr和ElasticSearch）如何做到這一點。

文件格式可以與上面解釋的相同。主要區別在於，如果在像Lucene這樣的系統中索引新文檔，而不是從頭開始重新構建索引，則只需使用新文檔創建一個新文檔。所以每次你必須索引一些東西時，你需要在一個新的索引中進行索引。

要在此「分割」索引中執行查詢，您可以針對每個不同索引（並行）運行查詢，並在返回給用戶之前將結果合併在一起。

Lucene稱之爲「小」索引segments。

這裏顯而易見的問題是你會很快得到很多小段。爲了避免這種情況，您需要制定合併分段和創建更大分段的政策。例如，如果您有超過N segments，您可以決定合併所有小於10 KBs的分段。