خوارزمية Bitap

الموسوعة الحرة

خوارزمية bitap (المعروفة أيضًا باسم خوارزمية الإزاحة-أو ، ​​أو الإزاحة-و، أو خوارزمية بايزا-ياتس-جونيه ) هي خوارزمية مطابقة تقريبية للسلاسل النصية . تُحدد هذه الخوارزمية ما إذا كان نص مُعطى يحتوي على سلسلة فرعية "مُساوية تقريبًا" لنمط مُعطى، حيث تُعرَّف المُساواة التقريبية بدلالة مسافة ليفنشتاين - إذا كانت السلسلة الفرعية والنمط ضمن مسافة k مُحددة، فإن الخوارزمية تعتبرهما مُتساويين. تبدأ الخوارزمية بحساب مُسبق لمجموعة من أقنعة البتات، تحتوي كل منها على بت واحد لكل عنصر من عناصر النمط. بعد ذلك، تُنجز الخوارزمية مُعظم العمل باستخدام عمليات البتات ، وهي عمليات سريعة للغاية. 

ربما تُعرف خوارزمية bitap على نطاق واسع كإحدى الخوارزميات الأساسية لأداة agrep في نظام يونكس ، والتي كتبها أودي مانبر ، وسون وو ، وبورا جوبال . وتقدم الورقة البحثية الأصلية لمانبر وو امتدادات للخوارزمية للتعامل مع المطابقة التقريبية للتعبيرات النمطية العامة .

نظراً لبنية البيانات التي تتطلبها الخوارزمية، فإنها تعمل بأفضل كفاءة مع الأنماط التي يقل طولها عن طول ثابت (عادةً ما يكون طول الكلمة في الجهاز المعني)، كما أنها تُفضل المدخلات ذات الأبجدية الصغيرة . وبمجرد تطبيقها على أبجدية معينة وطول كلمة m ، يصبح وقت تشغيلها قابلاً للتنبؤ تماماً - إذ تعمل في O ( mn ) عملية، بغض النظر عن بنية النص أو النمط. 

ابتكر بالينت دومولكي خوارزمية bitap للبحث عن السلاسل النصية الدقيقة في عام 1964وتم توسيعه بواسطة آر كي شياماسوندار في عام 1977، قبل أن يعيد ابتكارها ريكاردو بايزا-ياتس وجاستون جونيهفي عام 1989 (فصل واحد من أطروحة الدكتوراه للمؤلف الأول)) والذي وسّع نطاقه أيضًا ليشمل التعامل مع فئات الأحرف، والأحرف البديلة، وحالات عدم التطابق. وفي عام 1991، قام مانبر وو بتوسيعه .لمعالجة عمليات الإضافة والحذف أيضاً (البحث التقريبي الكامل عن السلاسل النصية). وقد تم تحسين هذه الخوارزمية لاحقاً بواسطة بايزا-ياتس ونافارو في عام 1996.

البحث الدقيق

تبدو خوارزمية bitap للبحث عن السلاسل النصية الدقيقة ، بشكل عام، على النحو التالي في الشفرة الزائفة:

خوارزمية bitap_search هي المدخلات: نص كسلسلة نصية. نمط كسلسلة نصية. المخرجات: سلسلة نصية m := طول( النمط ) إذا كانت قيمة m تساوي صفرًا، فأرجع النص . /* تهيئة مصفوفة البتات R. */ R := مصفوفة جديدة [ m +1] من البتات، جميعها في البداية 0 R [0] := 1 for i := 0; i < length( text ); i += 1 do /* تحديث مصفوفة البتات. */ for k := m ; k ≥ 1; k -= 1 do R [k] := R [ k - 1] & ( text [ i ] = pattern [ k - 1]) إذا كان R [ m ] ، فأرجع ( النص + i - m ) + 1 إرجاع قيمة فارغة

تتميز خوارزمية Bitap عن غيرها من خوارزميات البحث عن السلاسل النصية المعروفة بقابليتها الطبيعية للعمليات الثنائية البسيطة، كما في التعديل التالي للبرنامج أعلاه. لاحظ أنه في هذا التطبيق، وعلى عكس المتوقع،  يشير كل بت بقيمة صفر إلى تطابق، بينما يشير كل بت بقيمة  1 إلى عدم تطابق. يمكن كتابة الخوارزمية نفسها بدلالات بديهية للقيمتين 0 و1، ولكن في هذه الحالة يجب إضافة تعليمة أخرى إلى الحلقة الداخلية لضبط قيمة البت R |= 1. في هذا التطبيق، نستفيد من حقيقة أن إزاحة القيمة إلى اليسار تُضيف أصفارًا إلى اليمين، وهو السلوك المطلوب تحديدًا.

لاحظ أيضًا أننا نحتاج إلى CHAR_MAXأقنعة بت إضافية لتحويل (text[i] == pattern[k-1])الشرط في التنفيذ العام إلى عمليات بتية. لذلك، يكون أداء خوارزمية bitap أفضل عند تطبيقها على مدخلات ذات أبجديات أصغر.

#include <string.h> #include <limits.h> const char * bitap_bitwise_search ( const char * text , const char * pattern ) { int m = strlen ( pattern ); unsigned long R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i ; if ( m == 0 ) return text ; if ( m > 31 ) throw "النمط طويل جدًا!" ; /* تهيئة مصفوفة البتات R */ R = ~ 1 ; /* تهيئة أقنعة بتات النمط */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* تحديث مصفوفة البتات */ R |= pattern_mask [ text [ i ]]; R <<= 1 ; if ( 0 == ( R & ( 1UL << m ))) return ( text + i - m ) + 1 ; } return NULL ; }

البحث الضبابي

لإجراء بحث تقريبي عن السلاسل النصية باستخدام خوارزمية bitap، من الضروري توسيع مصفوفة البتات R إلى بُعد ثانٍ. فبدلاً من وجود مصفوفة واحدة R تتغير على طول النص، لدينا الآن k مصفوفة مميزة R <sub>1</sub>... k . تحتوي المصفوفة R <sub> i</sub> على تمثيل لبادئات النمط التي تُطابق أي لاحقة من السلسلة النصية الحالية مع i خطأ أو أقل. في هذا السياق، قد يكون "الخطأ" عبارة عن إضافة أو حذف أو استبدال؛ راجع مسافة ليفنشتاين لمزيد من المعلومات حول هذه العمليات.

تُجري الخوارزمية الموضحة أدناه مطابقة تقريبية (بإرجاع أول تطابق مع ما يصل إلى k خطأ) باستخدام خوارزمية المطابقة التقريبية الثنائية. مع ذلك، فهي تُركز فقط على الاستبدالات، وليس على الإضافات أو الحذوفات - أي مسافة هامينغ k . وكما في السابق، فإن دلالات 0 و1 معكوسة عن معانيها التقليدية. 

#include <stdlib.h> #include <string.h> #include <limits.h> const char * bitap_fuzzy_bitwise_search ( const char * text , const char * pattern , int k ) { const char * result = NULL ; int m = strlen ( pattern ); unsigned long * R ; unsigned long pattern_mask [ CHAR_MAX + 1 ]; int i , d ; if ( pattern [ 0 ] == '\0' ) return text ; if ( m > 31 ) return "النمط طويل جدًا!" ; /* تهيئة مصفوفة البتات R */ R = malloc (( k + 1 ) * sizeof * R ); for ( i = 0 ; i <= k ; ++ i ) R [ i ] = ~ 1 ; /* تهيئة أقنعة بت النمط */ for ( i = 0 ; i <= CHAR_MAX ; ++ i ) pattern_mask [ i ] = ~ 0 ; for ( i = 0 ; i < m ; ++ i ) pattern_mask [ pattern [ i ]] &= ~ ( 1UL << i ); for ( i = 0 ; text [ i ] != '\0' ; ++ i ) { /* تحديث مصفوفات البت */ unsigned long old_Rd1 = R [0 ]; R [ 0 ] |= pattern_mask [ text [ i ]]; R [ 0 ] <<= 1 ; for ( d = 1 ; d <= k ; ++ d ) { unsigned long tmp = R [ d ]; /* الاستبدال هو كل ما يهمنا */ R [ d ] = ( old_Rd1 & ( R [ d ] | pattern_mask [ text [ i ]])) << 1 ; old_Rd1 = tmp ; } if ( 0 == ( R [ k ] & ( 1UL << m ))) { result = ( text + i - m ) + 1 ; break ; } } free ( R ); return result ; }

انظر أيضاً

  1. ^ بالينت دومولكي، خوارزمية للتحليل النحوي، اللغويات الحاسوبية 3، الأكاديمية الهنغارية للعلوم، ص 29-46، 1964.
  2. ^ بالينت دومولكي، نظام مُترجم عالمي قائم على قواعد الإنتاج،الرياضيات العددية في BIT، 8(4)، ص 262-275،1968.doi:10.1007/BF01933436
  3. ^ RK Shyamasundar، تحليل الأسبقية باستخدام خوارزمية Dömölki،المجلة الدولية للرياضيات الحاسوبية، 6(2) ص 105-114، 1977.
  4. ^ ريكاردو بايزا-ياتس. "البحث النصي الفعال". أطروحة دكتوراه، جامعة واترلو، كندا، مايو 1989.
  5. ^ أودي مانبر، صن وو. "بحث سريع عن النصوص مع وجود أخطاء". تقرير فني TR-91-11. قسم علوم الحاسوب،جامعة أريزونا، توسون، يونيو 1991. (ملف بوست سكريبت مضغوط بصيغة gzip)
  6. ^ ريكاردو بايزا-ياتس، جاستون هـ. جونيت. "نهج جديد للبحث في النصوص." اتصالات ACM ، 35(10): ص 74-82،أكتوبر 1992.
  7. ^ أودي مانبر، صن وو. "بحث نصي سريع يسمح بالأخطاء." اتصالات ACM ، 35(10): ص 83-91،أكتوبر 1992،doi:10.1145/135239.135244.
  8. ^ ر. بايزا-ياتس وج. نافارو. خوارزمية أسرع لمطابقة السلاسل التقريبية. في دان هيرشسبيرغ وجين مايرز، محررين،مطابقة الأنماط التوافقية(CPM'96)، LNCS 1075، الصفحات 1-23،إرفاين، كاليفورنيا، يونيو 1996.
  9. ^ جي. مايرز. "خوارزمية سريعة لمتجهات البتات لمطابقة السلاسل التقريبية بناءً على البرمجة الديناميكية." مجلة ACM 46 (3)، مايو 1999، 395–415.
  10. مكتبة libbitap هي تطبيق مجاني يوضح كيفية توسيع الخوارزمية بسهولة لتشمل معظم التعابير النمطية. على عكس الكود المذكور أعلاه، لا تفرض هذه المكتبة أي قيود على طول النمط.
  11. ريكاردو بايزا ييتس، بيرتييه ريبيرو نيتو. استرجاع المعلومات الحديثة . 1999. ردمك 0-201-39829-X.
  12. bitap.py - تطبيق بايثون لخوارزمية Bitap مع تعديلات Wu-Manber.