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 个文档的大小（术语数）。