ds2i
1.0.0
역 인덱스용 데이터 구조(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에서 테스트되었습니다.
빌드에는 다음 종속성이 필요합니다.
코드는 여러 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 표준 입력의 각 행을 탭으로 구분된 용어 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 파일에는 트리플 샘플(람다, 공간, 예상 시간)이 포함됩니다.
이진 시퀀스 는 길이가 앞에 붙는 정수 시퀀스로, 시퀀스 정수와 길이는 모두 32비트 리틀 엔디안 부호 없는 정수로 기록됩니다.
컬렉션은 <basename>.docs , <basename>.freqs , <basename>.sizes 3개의 파일로 구성됩니다.
<basename>.docs 유일한 정수가 컬렉션의 문서 수인 싱글톤 바이너리 시퀀스로 시작합니다. 그런 다음 각 게시 목록에 대해 용어 ID 순서로 하나의 바이너리 시퀀스가 옵니다. 각 게시 목록에는 해당 용어를 포함하는 일련의 문서 ID가 포함되어 있습니다.
<basename>.freqs 게시 목록당 하나의 바이너리 시퀀스로 구성됩니다. 여기서 각 시퀀스에는 이전 파일과 정렬된 게시의 발생 횟수가 포함됩니다(그러나 이 파일의 시작 부분에는 추가 싱글톤 목록이 없다는 점에 유의하세요).
<basename>.sizes 길이가 컬렉션의 문서 수와 동일한 단일 이진 시퀀스로 구성되며 시퀀스의 i 번째 요소는 i 번째 문서의 크기(용어 수)입니다.
