ds2i
1.0.0
Структуры данных для инвертированных индексов (ds2i) — это библиотека структур данных для представления целочисленных последовательностей, используемых в инвертированных индексах.
Этот код использовался в экспериментах следующих работ.
Джузеппе Оттавиано, Россано Вентурини, Разделенные индексы Элиаса-Фано , ACM SIGIR 2014.
Джузеппе Оттавиано, Никола Тонеллотто, Россано Вентурини, Оптимальные компромиссы между пространством и временем для инвертированных индексов , ACM WSDM 2015.
Код протестирован в Linux с GCC 4.9 и OSX Yosemite с Clang.
Для сборки необходимы следующие зависимости.
Код зависит от нескольких подмодулей git. Если вы клонировали репозиторий без --recursive , перед сборкой вам необходимо будет выполнить следующие команды:
$ git submodule init
$ git submodule update
Чтобы построить код:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
Также предпочтительнее выполнить make test , который запускает модульные тесты.
Каталог 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 каждую строку стандартного ввода как набор идентификаторов терминов, разделенных табуляцией, где 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 будет содержать выборку троек (лямбда, пространство, расчетное время).
Бинарная последовательность — это последовательность целых чисел с префиксом ее длины, где целые числа последовательности и длина записываются как 32-битные целые числа без знака с прямым порядком байтов.
Коллекция состоит из трех файлов: <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs начинается с одноэлементной двоичной последовательности, единственное целое число которой — это количество документов в коллекции. Затем для каждого списка публикаций следует одна двоичная последовательность в порядке идентификаторов терминов. Каждый список сообщений содержит последовательность идентификаторов документов, содержащих этот термин.
<basename>.freqs состоит из одной двоичной последовательности для каждого списка сообщений, где каждая последовательность содержит количество вхождений сообщений, выровненных с предыдущим файлом (однако обратите внимание, что этот файл не имеет дополнительного одноэлементного списка в начале).
<basename>.sizes состоит из одной двоичной последовательности, длина которой равна количеству документов в коллекции, а i-й элемент последовательности представляет собой размер (количество терминов) i-го документа.
