ds2i下載 - ds2i原始碼下載

ds2i

其他源碼

1.0.0

下載

DS2i

倒排索引資料結構 (ds2i) 是一個資料結構庫，用於表示倒排索引中使用的整數序列。

這段程式碼在後面論文的實驗中都用到了。

Giuseppe Ottaviano、Rossano Venturini，分區 Elias-Fano 索引，ACM SIGIR 2014。
Giuseppe Ottaviano、Nicola Tonellotto、Rossano Venturini，倒排索引的最優時空權衡，ACM WSDM 2015。

建構程式碼

該程式碼在使用 GCC 4.9 的 Linux 和使用 Clang 的 OSX Yosemite 上進行了測試。

建置需要以下相依性。

CMake >= 2.8，用於建置系統
提升 >= 1.51

該程式碼依賴幾個 git 子模組。如果您在沒有--recursive情況下複製了儲存庫，則需要在建置之前執行以下命令：

 $ git submodule init
$ git submodule update

建構程式碼：

 $ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make

最好也執行make test來執行單元測試。

例：分區 Elias-Fano

目錄test/test_data包含單元測試中使用的小文檔集合。以下部分描述了集合的二進位格式。

若要建立索引，請使用指令create_freq_index 。 index_types.hpp中列出了可用的索引類型。例如，若要使用測試集合使用最佳分區演算法建立索引，請執行下列命令：

 $ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check

其中test/test_data/test_collection是集合的基本名稱，即不含.{docs,freqs,sizes}副檔名的名稱， test_collection.index.opt是輸出索引的檔名。 --check執行驗證步驟以檢查索引的正確性。

要執行 BM25 查詢，需要建立一個附加文件，其中包含計算分數所需的參數，例如文件長度。可以使用以下命令建置該檔案：

 $ ./create_wand_data ../test/test_data/test_collection test_collection.wand

現在可以查詢索引了。命令queries將標準輸入的每一行解析為製表符分隔的術語 ID 集合，其中第 i 個術語是輸入集合中的第 i 個清單。一組範例查詢再次位於test/test_data中。

 $ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries

這將執行連接查詢（ and ）。可以使用and其他運算子來代替（ or 、 wand 、...，請參閱queries.cpp ），也可以使用冒號分隔的多個運算子（ and:or:wand ）。

範例：最佳時空權衡

要為給定的查詢分佈和空間預算建立時間最優的索引，必須遵循以下步驟。

首先，必須在集合上建立基於區塊的索引。這將用於收集區塊存取統計資訊。

 $ ./create_freq_index block_optpfor ../test/test_data/test_collection test_collection.index.block_optpfor
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand

然後，給定從查詢分佈中採樣的一系列查詢，我們可以產生統計資料。

 $ ./profile_queries block_optpfor ranked_and:wand:maxscore 
    test_collection.index.block_optpfor test_collection.wand 
    < ../test/test_data/queries 
    > query_profile

為了預測區塊解碼時間，我們需要在樣本上進行測量。

 $ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json

0.1 是採樣區塊的分數。對於大索引，可以使用非常小的數字。測量的時間可用於訓練線性模型。

 $ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv

上述腳本需要 Numpy、Scipy、Pandas 和 Theano。

我們最終可以建立新的索引，例如比上面產生的block_optpfor索引稍小的索引。

 $ ./optimal_hybrid_index block_optpfor linear_weights.tsv 
    query_profile test_collection.index.block_optpfor 
    lambdas.bin 4000000 test_collection.index.block_mixed

貪心演算法計算出的臨界點快取在lambdas.bin檔案中，該檔案可以重複用於產生具有不同時空權衡的其他索引。若要重新計算它們（例如，如果查詢設定檔發生變更），只需刪除該檔案即可。

現在我們可以查詢索引了。

 $ ./queries block_mixed ranked_and test_collection.index.block_mixed 
    test_collection.wand < ../test/test_data/queries
...
Mean: 9.955
...

$ ./queries block_optpfor ranked_and test_collection.index.block_optpfor 
    test_collection.wand < ../test/test_data/queries
...
Mean: 11.125
...

請注意，新索引比舊索引更快且更小。當然，我們在這裡作弊，因為我們正在使用與訓練它相同的查詢來測試它；真實應用程式的訓練和測試集是獨立的。

也可以使用以下命令輸出權衡曲線的樣本。

 $ ./optimal_hybrid_index block_optpfor linear_weights.tsv 
    query_profile test_collection.index.block_optpfor 
    lambdas.bin 0 lambdas.tsv

文件lambdas.tsv將包含三元組樣本（lambda、空間、估計時間）。

集合輸入格式

二進位序列是以其長度為前綴的整數序列，其中序列整數和長度都寫成 32 位元小端無符號整數。

集合由 3 個檔案組成： <basename>.docs 、 <basename>.freqs 、 <basename>.sizes 。

<basename>.docs以單一二進位序列開頭，其中唯一的整數是集合中文件的數量。然後，每個發布清單後面跟著一個二進位序列，按照術語 ID 的順序排列。每個發布清單包含包含該術語的文檔 ID 序列。
<basename>.freqs由每個發布清單的一個二進位序列組成，其中每個序列包含發布的出現計數，與前一個文件對齊（但請注意，該文件在其開頭沒有附加的單例列表）。
<basename>.sizes由單一二進位序列組成，其長度與集合中文件的數量相同，序列的第 i 個元素是第 i 個文件的大小（術語數）。