الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

ds2i

هياكل البيانات للفهارس المقلوبة (ds2i) هي مكتبة لهياكل البيانات لتمثيل تسلسلات الأعداد الصحيحة المستخدمة في الفهارس المقلوبة.

تم استخدام هذا الرمز في تجارب الأوراق التالية.

  • جوزيبي أوتافيانو، روسانو فينتوريني، فهارس إلياس فانو المقسمة ، ACM SIGIR 2014.

  • جوزيبي أوتافيانو، نيكولا تونيلوتو، روسانو فينتوريني، المفاضلة المثلى للزمكان للمؤشرات المقلوبة ، ACM WSDM 2015.

بناء الكود

تم اختبار الكود على نظام التشغيل Linux مع الإصدار 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 الذي يقوم بإجراء اختبارات الوحدة.

مثال: مقسم إلياس فانو

يحتوي دليل 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 على عينة ثلاثية (lambda، المساحة، الوقت المقدر).

تنسيق إدخال المجموعة

التسلسل الثنائي هو تسلسل من الأعداد الصحيحة مسبوقة بطولها، حيث يتم كتابة كل من الأعداد الصحيحة التسلسلية والطول كأعداد صحيحة غير موقعة ذات نهاية صغيرة 32 بت.

تتكون المجموعة من 3 ملفات، <basename>.docs ، <basename>.freqs ، <basename>.sizes .

  • يبدأ <basename>.docs بتسلسل ثنائي مفرد حيث يكون عدده الصحيح الوحيد هو عدد المستندات الموجودة في المجموعة. ثم يتبعه تسلسل ثنائي واحد لكل قائمة ترحيل، بترتيب معرفات المصطلحات. تحتوي كل قائمة ترحيل على تسلسل معرفات المستندات التي تحتوي على المصطلح.

  • يتكون <basename>.freqs من تسلسل ثنائي واحد لكل قائمة نشر، حيث يحتوي كل تسلسل على عدد مرات ظهور الترحيلات، محاذاة مع الملف السابق (لاحظ أن هذا الملف لا يحتوي على قائمة مفردة إضافية في بدايته).

  • يتكون <basename>.sizes من تسلسل ثنائي واحد طوله هو نفس عدد المستندات الموجودة في المجموعة، والعنصر i في التسلسل هو حجم (عدد المصطلحات) للمستند i.

المؤلفون

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل