BitFunnel

📅 آخر تحديث: ٢٢ يوليو ٢٠٢٦
✍️ نُشر في: ٢٢ يوليو ٢٠٢٦
📷 يحتوي على 5 صور
الموسوعة الحرة

BitFunnel هي خوارزمية فهرسة محركات البحث ومجموعة من المكونات المستخدمة في محرك بحث Bing ، [ 1 ] والتي أصبحت مفتوحة المصدر في عام 2016. [ 2 ] تستخدم BitFunnel التوقيعات المقطعة بالبتات بدلاً من الفهرس المعكوس في محاولة لتقليل تكلفة العمليات. [ 3 ]

تاريخ

أُعلن عن التقدم المُحرز في تطبيق خوارزمية BitFunnel في أوائل عام 2016، مع توقع توفر تطبيق عملي في وقت لاحق من ذلك العام. [ 4 ] وفي سبتمبر 2016، أُتيح الكود المصدري عبر منصة GitHub . [ 5 ] وفي عام 2017، نُشرت ورقة بحثية تناقش خوارزمية BitFunnel وتطبيقها من خلال مجموعة الاهتمام الخاصة باسترجاع المعلومات التابعة لرابطة آلات الحوسبة، وحازت على جائزة أفضل ورقة بحثية. [ 3 ] [ 6 ]

عناصر

يتكون BitFunnel من ثلاثة مكونات رئيسية: [ 1 ]

الخوارزمية

نظرة عامة أولية على المشكلة والحل

تصف ورقة BitFunnel "مشكلة المطابقة"، التي تحدث عندما يتعين على خوارزمية تحديد المستندات باستخدام الكلمات المفتاحية. يهدف هذا الحل إلى تحديد مجموعة من التطابقات بناءً على مجموعة نصوص للبحث فيها واستعلام يتضمن كلمات مفتاحية للمطابقة. تُحل هذه المشكلة عادةً باستخدام الفهارس المعكوسة ، حيث يُحتفظ بكل عنصر قابل للبحث بخريطة للكلمات المفتاحية. [ 3 ]

في المقابل، يُمثل BitFunnel كل عنصر قابل للبحث من خلال توقيع. التوقيع عبارة عن سلسلة من البتات تصف مُرشِّح بلوم للمصطلحات القابلة للبحث في عنصر مُحدد. يتم إنشاء مُرشِّح بلوم من خلال التجزئة عبر عدة مواضع بت. [ 3 ]

التنفيذ النظري لتوقيعات السلاسل الثنائية

يمكن وصف توقيع المستند (D) بأنه عملية "أو" المنطقية لتوقيعات المصطلحات الخاصة به:

Sد→=⋃ت∈دSت→{\displaystyle {\overrightarrow {S_{D}}}=\bigcup _{t\in D}{\overrightarrow {S_{t}}}}

وبالمثل، يمكن تعريف الاستعلام عن مستند (Q) على أنه اتحاد:

Sسؤال→=⋃ت∈سؤالSت→{\displaystyle {\overrightarrow {S_{Q}}}=\bigcup _{t\in Q}{\overrightarrow {S_{t}}}}

بالإضافة إلى ذلك، يكون المستند D عضوًا في المجموعة M' عندما يتحقق الشرط التالي:

Sسؤال→∩Sد→=Sسؤال→{\displaystyle {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}}

ثم يتم دمج هذه المعرفة لإنتاج صيغة يتم فيها تحديد M' بواسطة المستندات التي تطابق توقيع الاستعلام:

م′={د∈ج|Sسؤال→∩Sد→=Sسؤال→}{\displaystyle M'=\left\{D\in C\mid {\overrightarrow {S_{Q}}}\cap {\overrightarrow {S_{D}}}={\overrightarrow {S_{Q}}}\right\}}

تمت مناقشة هذه الخطوات وبراهينها في ورقة بحثية نُشرت عام 2017. [ 3 ]

الشفرة الزائفة لتوقيعات السلاسل الثنائية

تم وصف هذه الخوارزمية في ورقة بحثية نُشرت عام 2017. [ 3 ]م′=∅لكل د∈ج يفعللو Sد→∩Sسؤال→=Sسؤال→ ثمم′=م′∪{د}endifendfor{\displaystyle {\begin{array}{l}M'=\emptyset \\{\texttt {foreach}}\ D\in C\ {\texttt {do}}\\\qquad {\texttt {if}}\ {\overrightarrow {S_{D}}}\cap {\overrightarrow {S_{Q}}}={\overrightarrow {S_{Q}}}\ {\texttt {then}}\\\qquad \qquad M'=M'\cup \{D\}\\\qquad {\texttt {endif}}\\{\texttt {endfor}}\end{array}}}

مراجع

  1. 1 2 يغولالب، سردار (6 سبتمبر 2016). "مايكروسوفت تفتح مصادر مكونات Bing لتجميع التعليمات البرمجية بسرعة" . إنفوورلد .
  2. ↑ فيرما، أربيت (2016-09-07). "مايكروسوفت تفتح المصادر لمكونات رئيسية من محرك بحث بينغ، إليك سبب أهمية ذلك" . فوسبايتس . تم الاسترجاع في 2020-06-12 .
  3. 1 2 3 4 5 6 غودوين، بوب؛ هوبكروفت، مايكل؛ لو، دان؛ كليمر، أليكس؛ كورمي، ميهايلا؛ إلنيكيتي، سامح؛ هي، يوكسيونغ (2017-08-07). "BitFunnel". وقائع المؤتمر الدولي الأربعين لجمعية ACM SIGIR حول البحث والتطوير في استرجاع المعلومات . نيويورك، نيويورك، الولايات المتحدة الأمريكية: ACM. الصفحات 605-614 . doi : 10.1145/3077136.3080789 . ISBN  978-1-4503-5022-8.
  4. ↑ "متى سيصبح BitFunnel قابلاً للاستخدام؟ · BitFunnel" . bitfunnel.org . تم الاطلاع عليه بتاريخ 12 يونيو 2020 .
  5. ↑ BitFunnel/BitFunnel ، BitFunnel، 12 مايو 2020 ، تم الاطلاع عليه بتاريخ 12 يونيو 2020
  6. ↑ "جوائز SIGIR لأفضل ورقة بحثية" . ACM . تم الاطلاع عليه بتاريخ 8 يوليو 2020 .