ds2i
1.0.0
Struktur Data untuk Indeks Terbalik (ds2i) adalah pustaka struktur data untuk mewakili urutan bilangan bulat yang digunakan dalam indeks terbalik.
Kode ini digunakan dalam percobaan makalah berikut.
Giuseppe Ottaviano, Rossano Venturini, Indeks Elias-Fano yang Dipartisi , ACM SIGIR 2014.
Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, Pengorbanan Ruang-Waktu Optimal untuk Indeks Terbalik , ACM WSDM 2015.
Kode ini diuji di Linux dengan GCC 4.9 dan OSX Yosemite dengan Clang.
Dependensi berikut diperlukan untuk build.
Kode ini bergantung pada beberapa submodul git. Jika Anda telah mengkloning repositori tanpa --recursive , Anda perlu melakukan perintah berikut sebelum membuat:
$ git submodule init
$ git submodule update
Untuk membuat kode:
$ mkdir build
$ cd build
$ cmake .. -DCMAKE_BUILD_TYPE=Release
$ make
Sebaiknya juga melakukan make test , yang menjalankan pengujian unit.
Direktori test/test_data berisi kumpulan dokumen kecil yang digunakan dalam pengujian unit. Format biner dari koleksi dijelaskan di bagian berikut.
Untuk membuat indeks gunakan perintah create_freq_index . Tipe indeks yang tersedia tercantum dalam index_types.hpp . Misalnya, untuk membuat indeks menggunakan algoritma partisi optimal menggunakan koleksi pengujian, jalankan perintah:
$ ./create_freq_index opt ../test/test_data/test_collection test_collection.index.opt --check
di mana test/test_data/test_collection adalah nama dasar koleksi, yaitu nama tanpa ekstensi .{docs,freqs,sizes} , dan test_collection.index.opt adalah nama file indeks keluaran. --check melakukan langkah verifikasi untuk memeriksa kebenaran indeks.
Untuk melakukan kueri BM25, perlu dibuat file tambahan yang berisi parameter yang diperlukan untuk menghitung skor, seperti panjang dokumen. File dapat dibuat dengan perintah berikut:
$ ./create_wand_data ../test/test_data/test_collection test_collection.wand
Sekarang dimungkinkan untuk menanyakan indeks. queries perintah mem-parsing setiap baris masukan standar sebagai kumpulan id istilah yang dipisahkan tab, dengan istilah ke-i adalah daftar ke-i dalam kumpulan masukan. Contoh kumpulan kueri ada lagi di test/test_data .
$ ./queries opt and test_collection.index.opt test_collection.wand < ../test/test_data/queries
Ini melakukan kueri konjungtif ( and ). Sebagai pengganti and operator lain dapat digunakan ( or , wand , ..., lihat queries.cpp ), dan juga beberapa operator dipisahkan dengan titik dua ( and:or:wand ).
Untuk membuat indeks waktu yang optimal untuk distribusi kueri dan anggaran ruang tertentu, perlu mengikuti langkah-langkah berikut.
Pertama, indeks berbasis blok harus dibangun di atas koleksi. Ini akan digunakan untuk mengumpulkan statistik akses blok.
$ ./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
Kemudian, dengan urutan kueri yang diambil sampelnya dari distribusi kueri, kita dapat menghasilkan statistiknya.
$ ./profile_queries block_optpfor ranked_and:wand:maxscore
test_collection.index.block_optpfor test_collection.wand
< ../test/test_data/queries
> query_profile
Untuk memprediksi waktu decoding blok kita perlu mengukurnya pada sampel.
$ ./profile_decoding block_optpfor test_collection.index.block_optpfor 0.1 > decoding_times.json
0,1 adalah pecahan blok sampel. Untuk indeks yang besar, angka yang sangat kecil dapat digunakan. Waktu yang diukur dapat digunakan untuk melatih model linier.
$ ./dec_time_regression.py parse_data decoding_times.json decoding_times.pandas
$ ./dec_time_regression.py train decoding_times.pandas > linear_weights.tsv
Script di atas membutuhkan Numpy, Scipy, Pandas, dan Theano.
Kami akhirnya dapat membuat indeks baru, misalnya sesuatu yang sedikit lebih kecil dari indeks block_optpfor yang dihasilkan di atas.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 4000000 test_collection.index.block_mixed
Titik-titik kritis yang dihitung dalam algoritma serakah di-cache dalam file lambdas.bin , yang dapat digunakan kembali untuk menghasilkan indeks lain dengan pengorbanan ruang-waktu yang berbeda. Untuk menghitung ulangnya (misalnya jika profil kueri berubah) cukup hapus file tersebut.
Sekarang kita dapat menanyakan indeks.
$ ./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
...
Perhatikan bahwa indeks baru lebih cepat dan lebih kecil dibandingkan indeks lama. Tentu saja kami melakukan kecurangan di sini karena kami mengujinya dengan pertanyaan yang sama dengan yang kami latih; pada pelatihan aplikasi nyata dan set pengujian akan bersifat independen.
Dimungkinkan juga untuk menampilkan contoh kurva trade-off dengan perintah berikut.
$ ./optimal_hybrid_index block_optpfor linear_weights.tsv
query_profile test_collection.index.block_optpfor
lambdas.bin 0 lambdas.tsv
File lambdas.tsv akan berisi contoh tripel (lambda, spasi, perkiraan waktu).
Barisan biner adalah barisan bilangan bulat yang diawali dengan panjangnya, dimana bilangan bulat barisan dan panjangnya ditulis sebagai bilangan bulat tak bertanda tangan little-endian 32-bit.
Koleksi terdiri dari 3 file, <basename>.docs , <basename>.freqs , <basename>.sizes .
<basename>.docs dimulai dengan urutan biner tunggal di mana satu-satunya bilangan bulat adalah jumlah dokumen dalam koleksi. Hal ini kemudian diikuti oleh satu urutan biner untuk setiap daftar posting, dalam urutan id istilah. Setiap daftar posting berisi urutan id dokumen yang mengandung istilah tersebut.
<basename>.freqs terdiri dari satu urutan biner per daftar posting, di mana setiap urutan berisi jumlah kemunculan posting, selaras dengan file sebelumnya (namun perlu diperhatikan bahwa file ini tidak memiliki daftar tunggal tambahan di awal).
<basename>.sizes terdiri dari barisan biner tunggal yang panjangnya sama dengan jumlah dokumen dalam koleksi, dan elemen ke-i dari barisan tersebut adalah ukuran (jumlah istilah) dari dokumen ke-i.
