หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>ซอร์สโค้ดอื่น ๆ
ดาวน์โหลด

ดีเอส2ไอ

โครงสร้างข้อมูลสำหรับดัชนีกลับหัว (ds2i) คือไลบรารีของโครงสร้างข้อมูลที่แสดงถึงลำดับจำนวนเต็มที่ใช้ในดัชนีกลับหัว

รหัสนี้ใช้ในการทดลองในเอกสารต่อไปนี้

  • Giuseppe Ottaviano, Rossano Venturini, ดัชนี Elias-Fano แบบแบ่งพาร์ติชัน , ACM SIGIR 2014

  • Giuseppe Ottaviano, Nicola Tonellotto, Rossano Venturini, การแลกเปลี่ยนอวกาศ-เวลาที่เหมาะสมที่สุดสำหรับดัชนีกลับหัว , ACM WSDM 2015

การสร้างรหัส

รหัสนี้ได้รับการทดสอบบน Linux ด้วย GCC 4.9 และ OSX Yosemite พร้อม Clang

จำเป็นต้องมีการขึ้นต่อกันต่อไปนี้สำหรับบิลด์

  • 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 สั่งเคียวรีแยกวิเคราะห์แต่ละบรรทัดของอินพุตมาตรฐานเป็นคอลเล็กชัน term-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 จะมีตัวอย่างสามรายการ (แลมบ์ดา พื้นที่ เวลาโดยประมาณ)

รูปแบบอินพุตคอลเลกชัน

ลำดับไบนารี่ คือลำดับของจำนวนเต็มนำหน้าด้วยความยาว โดยที่ทั้งจำนวนเต็มลำดับและความยาวเขียนเป็นจำนวนเต็ม little-endian ที่ไม่ได้ลงนามขนาด 32 บิต

คอลเลกชัน ประกอบด้วย 3 ไฟล์ <basename>.docs , <basename>.freqs , <basename>.sizes

  • <basename>.docs เริ่มต้นด้วยลำดับไบนารีเดี่ยว โดยที่จำนวนเต็มเพียงอย่างเดียวคือจำนวนเอกสารในคอลเลกชัน จากนั้นตามด้วยลำดับไบนารีหนึ่งลำดับสำหรับแต่ละรายการการโพสต์ ตามลำดับรหัสคำ แต่ละรายการการโพสต์ประกอบด้วยลำดับของรหัสเอกสารที่มีคำดังกล่าว

  • <basename>.freqs ประกอบด้วยหนึ่งลำดับไบนารี่ต่อรายการการโพสต์ โดยแต่ละลำดับมีจำนวนการโพสต์ที่เกิดขึ้น ซึ่งสอดคล้องกับไฟล์ก่อนหน้า (อย่างไรก็ตาม โปรดทราบว่าไฟล์นี้ไม่มีรายการซิงเกิลตันเพิ่มเติมที่จุดเริ่มต้น)

  • <basename>.sizes ประกอบด้วยลำดับไบนารีเดี่ยวที่มีความยาวเท่ากับจำนวนเอกสารในคอลเล็กชัน และองค์ประกอบ i-th ของลำดับคือขนาด (จำนวนเทอม) ของเอกสาร i-th

ผู้เขียน

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด