خوارزمية بوير-مور للبحث في السلاسل النصية

البحث عن سلسلة بوير-مور فصل البحث عن السلسلة بنية البيانات خيط الأداء في أسوأ الأحوال معالجة مسبقة Θ(m) + مطابقة O(mn) m is the length of the pattern string, which we are searching for in the text, which is of length n. This runtime is for finding all occurrences of the pattern, without the Galil rule. أفضل أداء معالجة مسبقة Θ(m) + مطابقة Ω(n/m) أسوأ حالة تعقيد الفضاء Θ(k+m) k is the size of the alphabet. This space is for the original delta1 bad-character table in the C and Java implementations and the good-suffix table.
خوارزمية بوير-مور للبحث في السلاسل النصية Boyer–Moore string-search algorithm- في علوم الكمبيوتر، تُعد خوارزمية البحث عن السلاسل بوير-مور خوارزمية فعالة للبحث عن السلاسل، وهي المعيار القياسي لأدبيات البحث العملي عن السلاسل. وقد تم تطويرها بواسطة كل من: روبرت إس. بوير، وجيه ستروثر مور، وذلك في عام 1977م. تحتوي الورقة البحثية الأصلية على جداول ثابتة لحساب تحولات النمط دون توضيح لكيفية إنتاجها. وتم نشر الخوارزمية المستخدمة في إنتاج الجداول في ورقة بحثية لاحقة؛ وقد احتوت هذه الورقة على أخطاء تم تصحيحها لاحقًا بواسطة فويتشيك ريتر في عام 1980م.

وتقوم الخوارزمية بمعالجة السلسلة التي يتم البحث عنها (النمط)، ولكن ليس السلسلة التي يتم البحث فيها (النص). الأمر الذي يجعلها مناسبة تمامًا للتطبيقات التي يكون فيها النمط أقصر بكثير من النص، أو حيث يستمر عبر عمليات بحث متعددة. تستخدم خوارزمية بوير–مور المعلومات التي تم جمعها أثناء خطوة المعالجة المسبقة لتخطي أقسام النص، مما يؤدي إلى عامل ثابت أقل من العديد من خوارزميات البحث عن السلسلة الأخرى. وبشكل عام، تعمل الخوارزمية بشكل أسرع مع زيادة طول النمط. وتكمن الميزات الرئيسية للخوارزمية في الآتي: المطابقة على ذيل النمط بدلاً من الرأس، والتخطي على طول النص في قفزات من عدة أحرف بدلاً من البحث في كل حرف في النص.

 التعاريف 
ANPANMAN -PAN - - - - - - -PAN - - - - - - -PAN - - - - - - -PAN - - - - - - -PAN - - - - - - -PAN -
محاذاة نمط PAN مع نص ANPANMAN، من k=3 إلى k=8. يحدث التطابق عند k=5.
 يشير T إلى النص المدخل الذي سيتم البحث عنه. وطوله هو n.
 يشير P إلى السلسلة التي سيتم البحث عنها، والتي تسمى النمط . وطولها m.
 يشير [ i ] S إلى الحرف الموجود في الفهرس i من السلسلة S، f]hd بداية من 1.
 يشير [ j.. i] S إلى السلسلة الفرعية من السلسلة S التي تبدأ عند الفهرس i وتنتهي عند j ، شاملة.
 البادئة S هي سلسلة فرعية S [1.. i ] لبعض i في النطاق [1, l ]، حيث l هو طول S.
 اللاحقة S هي سلسلة فرعية S [ i .. l ] لبعض i في النطاق [1، l ]، حيث l هو طول S.
 محاذاة P إلى T هي مؤشر k في T بحيث يتم محاذاة الحرف الأخير من P مع المؤشر k في T.
 يحدث تطابق أو حدوث P عند محاذاة k إذا كان P يعادل T [( k - m +1).. k ].

 وصف 
تبحث خوارزمية بوير–مور عن حدوث  في  من خلال إجراء مقارنات صريحة للأحرف في محاذات مختلفة. وذلك بدلاً عن البحث الشامل عن جميع المحاذاة (التي يوجد منها  ) تستخدم بوير–مور المعلومات التي تم الحصول عليها من خلال المعالجة المسبقة  لتخطي أكبر عدد ممكن  من المحاذاة.

وقبل تقديم مثل هذه الخوارزمية، كانت الطريقة المعتادة للبحث داخل النص هي فحص كل حرف من النص بحثًا عن الحرف الأول من النمط. وبمجرد العثور على ذلك، يتم مقارنة الأحرف اللاحقة للنص بأحرف النمط. وفي حالة-إذا لم يحدث أي تطابق، يتم فحص النص مرة أخرى حرفًا بحرف في محاولة للعثور على تطابق. وهكذا فإن كل حرف في النص يحتاج إلى فحص.

والفكرة الرئيسة في هذه الخوارزمية تكمن في: أنه إذا تمت مقارنة نهاية النمط بالنص، فيمكن إجراء قفزات على طول النص بدلاً من التحقق من كل حرف في النص. ولعل السبب وراء نجاح هذا الأمر، هو أنه عند محاذاة النمط مع النص، تتم مقارنة الحرف الأخير من النمط بالحرف الموجود في النص. وفي حالة-إذا لم تتطابق الأحرف، فلا داعي لمواصلة البحث إلى الوراء على طول النص. فإذا لم يتطابق الحرف الموجود في النص مع أي من الأحرف الموجودة في النمط، فإن الحرف التالي في النص الذي يجب التحقق منه يقع على بعد  حرفًا على طول النص، حيث  هو طول النمط. وإذا كان الحرف الموجود في النص موجودًا في النمط، يتم إجراء تحول جزئي للنمط على طول النص ليتم محاذاته على طول الحرف المطابق، ثم يتم تكرار العملية. والقفز على طول النص لإجراء المقارنات بدلاً من التحقق من كل حرف في النص يعمل لى التقليل من عدد المقارنات التي يجب إجراؤها، وهو مفتاح كفاءة الخوارزمية.

وبشكل أكثر رسمية، تبدأ الخوارزمية عند ، لذا فإن بداية  تتوافق مع بداية ، ثم تتم مقارنة الأحرف في  و  بداية من المؤشر  في  و  في ، مع عملية التحرك للخلف. تتم مطابقة السلاسل من نهاية  إلى . وتستمر المقارنات حتى الوصول إلى بداية  (أي وجود تطابق) أو حدوث عدم تطابق، وعندها يتم تحريك المحاذاة للأمام (إلى اليمين) وفقًا للحد الأقصى للقيمة المسموح بها بناءً على عدد من القواعد. كما يتم إجراء المقارنات مرة أخرى عند المحاذاة الجديدة، وتتكرر مثل هذه العملية حتى يتم تحويل المحاذاة إلى ما بعد نهاية ، مما يعني أنه لن يتم العثور على المزيد من المطابقات.

يتم تنفيذ قواعد التحول بوصفها عمليات بحث في جدول زمني ثابت، باستخدام الجداول التي تم إنشاؤها أثناء المعالجة المسبقة لـ .

 قواعد التحول 
يتم حساب التحول من خلال تطبيق قاعدتين أساسيتين: قاعدة الحرف السيئ، وقاعدة اللاحقة الجيدة. إن الإزاحة التحويلية الفعلية هي الحد الأقصى للتحويلات المحسوبة بواسطة هذه القواعد.

 قاعدة الحرف السيئ 

 وصف 
تأخذ قاعدة الحرف السيئ في الاعتبار الحرف الموجود في ""، والذي فشلت عنده عملية المقارنة (بافتراض حدوث مثل هذا الفشل). تم العثور على الظهور التالي لذلك الحرف على اليسار في ""، وتم اقتراح تحول يجعل هذا الظهور متوافقًا مع الظهور غير المتطابق في "" وإذا لم يظهر الحرف غير المتطابق على اليسار في ""، يتم اقتراح تحول يحرك "" بالكامل بعد نقطة عدم التطابق.
 - - - -X - -K - - -ANPANMANAM - -NNAAMAN - - - - - -NNAAMAN -
توضيح لقاعدة الأحرف غير الصحيحة باستخدام النمط P = NNAAMAN. يوجد عدم تطابق بين الحرف N (في النص المُدخل) والحرف A (في النمط) في العمود المُعلّم بعلامة X. يُزاح النمط إلى اليمين (في هذه الحالة بمقدار ٢) بحيث يظهر الحرف N (في النمط P) التالي على يسار الحرف الحالي (وهو حرف A الأوسط).

 المعالجة المسبقة 
تتعدد الأساليب وتختلف في الشكل الدقيق الذي يجب أن يتخذه الجدول لقاعدة الحرف السيئ، ولكن حل البحث البسيط في الوقت الثابت هو كما يلي: إنشاء جدول ثنائي الأبعاد يتم فهرسته أولاً بواسطة فهرس الحرف  في الأبجدية وثانيًا بواسطة الفهرس  في النمط. وسوف يؤدي هذا البحث إلى إرجاع حدوث "" في "" مع أعلى مؤشر or - 1  ,إذا لم يحدث مثل هذا. سيتم بعد ذلك التحول المقترح  ، مع وقت البحث  ومساحة البحث ، بافتراض وجود أبجدية محدودة بطول "".

تحتوي تنفيذات "C" و"جافا Java" أدناه على تعقيد المساحة  (make_delta1، makeCharTable). وهذا هو نفس جدول delta1 الأصلي و BMH bad-character . يقوم هذا الجدول برسم خريطة للحرف في " " ليتم التحول عن طريق ، مع إعطاء الأولوية للمثال الأخير -أقل قدر من التحول. ثم يتم تعيين جميع الأحرف غير المستخدمة على  بوصفها قيمة حارسة.

 قاعدة اللواحق الجيدة 

 وصف 

تعد قاعدة اللواحق الجيدة أكثر تعقيدًا بشكل ملحوظ من حيث المفهوم والتنفيذ من قاعدة الحرف السيئ. وكما هو الحال مع قاعدة الحرف السيئ، فإنها تستغل أيضًا ميزة الخوارزمية للمقارنات التي تبدأ في نهاية النمط وتستمر نحو بداية النمط. ويمكن وصف هذه القاعدة على النحو التالي:
 - - - -X - -K - - - - -MANPANAMANAP -ANAMPNAM - - - - - - - - -ANAMPNAM -
توضيح قاعدة اللواحق الجيدة باستخدام النمط P = ANAMPNAM. حيث t يساوي T[6..8] وt′ يساوي P[2..4].افترض أنه بالنسبة لمحاذاة معينة بين P و T، فإن السلسلة الفرعية t من T تطابق لاحقة P وافترض أن t هي أكبر سلسلة فرعية من هذا القبيل للمحاذاة المحددة.

 ثم ابحث، إن وُجدت، عن النسخة اليمنى القصوى t من t في P بحيث لا تكون t لاحقة لـ P ويختلف الحرف الموجود على يسار t في P عن الحرف الموجود على يسار t في P. ثم انقل P إلى اليمين بحيث تتماشى السلسلة الفرعية t في P مع السلسلة الفرعية t في T.
 إذا لم يكن الحرف t موجودًا، فقم بإزاحة الطرف الأيسر من P إلى اليمين بأقل قدر (بعد الطرف الأيسر من t في T) بحيث تتطابق بادئة النمط المُزاح مع لاحقة t في T. يتضمن هذا الحالات التي يكون فيها t مطابقًا تمامًا لـ P.
 إذا لم يكن مثل هذا التحول ممكنًا، فقم بتحويل P بمقدار m (طول P) إلى اليمين.

 المعالجة المسبقة 
قاعدة اللاحقة الجيدة تتطلب جدولين أساسيين: أحدهما للاستخدام في الحالة العامة (حيث يتم العثور على نسخة t، والآخر للاستخدام عندما لا تعيد الحالة العامة أي نتيجة ذات معنى. سيتم تسمية هذه الجداول  و  على التوالي. تعريفاتهم هي كما يلي:لكل ،  أكبر موضع أقل من  بحيث  يتطابق مع لاحقة P[1..L[i]] بحيث لا يكون الحرف الذي يسبق تلك اللاحقة مساويًا . و يتم تعريفه على أنه صفر إذا لم يكن هناك موضع يلبي الشرط.ليكن  يمثل طول أكبر لاحقة في والتي تعد أيضًا بادئة لـ ، إذا كانت موجودة. وإذا لم تكن موجودة، فليكن  صفر.كلا الجدولين قابلان للإنشاء في زمن  واستخدام فضاء  . يتم إعطاء تحول المحاذاة للمؤشر  في  بواسطة  أو، ويجب استخدام  فقط إذا كانت  تساوي صفرًا، أو تم العثور على تطابق.

 مثال على التحول باستخدام النمط ANPANMAN 
 الفهرس| التحول     | عدم التطابق   
  0    |         N|   1    
  1    |        AN|   8    
  2    |       MAN|   3    
  3    |      NMAN|   6   
  4    |     ANMAN|   6   
  5    |    PANMAN|   6  
  6    |   NPANMAN|   6  
  7    |  ANPANMAN|   6  
توضيح:

الفهرس "0"، لا توجد أحرف مطابقة، والحرف المقروء لم يكن "N". طول اللاحقة الجيدة هو صفر. ,نظرًا لوجود الكثير من الحروف في النمط التي ليست "N" أيضًا، فلدينا معلومات ضئيلة هنا - ,التحول بمقدار "1" هو النتيجة الأقل إثارة للاهتمام.

الفهرس "1"، لقد طابقنا "N"، وكان مسبوقًا بشيء آخر غير "A". ,الآن انظر إلى النمط بداية من النهاية، أين نجد "N" مسبوقًا بشيء آخر غير "A"؟ هناك حرفان آخران من "N"، إلا أن كلاهما مسبوق بالحرف "A". وهذا يعني أنه لا يمكن لأي جزء من اللاحقة الجيدة أن يكون مفيدًا لنا - التحول بطول النمط الكامل 8.

المؤشر 2: لقد قمنا بمطابقة AN، ولم يسبقه "M". في منتصف النمط يوجد AN مسبوقًا بـ "P"، وبذلك فهو يصبح مرشح التحول. وعملية تحريك AN إلى اليمين لتتوافق مع تطابقنا هو تحول بمقدار 3.

الفهرس 3 وما فوق: لا تتطابق اللواحق المطابقة مع أي شيء آخر في النمط، ولكن اللاحقة اللاحقة "AN" تتطابق مع بداية النمط، وبالتالي فإن التحولات هنا هي 6.

 قاعدة جليل 
تم طرح تحسين بسيط، ولكنه مهم لمعادلة بوير مور بواسطة زفي جليل Zvi Galil في عام 1979م. وعلى عكس التحويل، تتعامل قاعدة جليل مع تسريع المقارنات الفعلية التي يتم إجراؤها في كل محاذاة عن طريق تخطي الأقسام المعروفة بالتطابق. ولنفترض أنه عند محاذاة  ، تتم مقارنة "" مع "" وصولاً إلى الحرف "" من "" ثم إذا تم نقل "" إلى  بحيث يكون طرفه الأيسر بين "" و  ، فيجب في مرحلة المقارنة التالية أن تتطابق بادئة "" مع السلسلة الفرعية  .. . وبالتالي، إذا وصلت المقارنات إلى الموضع  من "" ، فيمكن تسجيل حدوث "" دون مقارنة صريحة بين الماضي  . بالإضافة إلى زيادة كفاءة بوير مور، فإن قاعدة جليل مطلوبة لإثبات التنفيذ في الوقت الخطي في أسوأ الحالات.

قاعدة جليل، في نسختها الأصلية، فعالة فقط للإصدارات التي ُتنتج مطابقات متعددة. يقوم بتحديث نطاق السلسلة الفرعية فقط عند  ، أي تطابق كامل. وقد تم الإبلاغ عن إصدار معمم للتعامل مع المطابقات الفرعية في عام 1985م باسم خوارزمية أبوستوليكو-جيانكارلوApostolico–Giancarlo .

 الأداء 
خوارزمية بوير- مور كما تم تقديمها في الورقة الأصلية لها لها زمن تشغيل في أسوء الحالات قدره  فقط إذا لم يظهر النمط في النص. وقد تم إثبات ذلك لأول مرة بواسطة دونالد كينوث Knuth وجيمس موريس Morris وهيو برات Pratt في عام 1977م، Knuth, Donald E.؛ Morris, James H. Jr.؛ Pratt, Vaughan R. (1977). "Fast pattern matching in strings". SIAM Journal on Computing. 6 (2): 323–350. CiteSeerX 10.1.1.93.8147. doi:10.1137/0206024. ISSN 0097-5397. ثم تبعهم كل من: غيباس Guibas و أودلي زكوOdlyzko في عام 1980م  مع حد أعلى يبلغ  مقارنة في أسوأ الحالات. وأعطى ريتشارد كول دليلاً بحد أقصى  مقارنة في أسوأ الحالات في عام 1991م.

عندما يحدث النمط في النص، يكون وقت تشغيل الخوارزمية الأصلية  في أسوأ الحالات. ومن السهل رؤية ذلك عندما يتكون كل من النمط والنص فقط من نفس الحرف المتكرر. ومع ذلك، فإن إدراج قاعدة جليل يؤدي إلى وقت تشغيل خطي في جميع الحالات.Galil, Z. (September 1979). "On improving the worst case running time of the Boyer–Moore string matching algorithm". Comm. ACM. 22 (9). New York: Association for Computing Machinery: 505–508. doi:10.1145/359146.359148. ISSN 0001-0782. S2CID 1333465.Cole, Richard (September 1991). "Tight bounds on the complexity of the Boyer–Moore string matching algorithm". Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms. Soda '91. Philadelphia, Pennsylvania: Society for Industrial and Applied Mathematics: 224–233. ISBN 0-89791-376-0.

 التنفيذات 
توجد تنفيذات مختلفة في لغات البرمجة المختلفة. في C++، يعد جزءًا من المكتبة القياسية منذ C++17، ويوفر بوستBoost تنفيذ البحث العام بوير–مور ضمن مكتبة الخوارزمية Algorithm . وفي لغة البرمجة غو Go يوجد تنفيذ في search.go. كما تستخدم لغة البرمجة دي D أداة بوير-مور فايندر BoyerMooreFinder للمطابقة القائمة على التنبؤ ضمن النطاقات كجزء من مكتبة تشغيل فوبوس.

كما تُستخدم خوارزمية بوير- مور أيضًا في جريب grep الخاص بـ جنو GNU.

 المتغيرات 
خوارزمية بوير-مور-هورسبول هي تبسيط لخوارزمية بوير-مور عن طريق استخدام قاعدة الأحرف السيئة فقط.

تعمل خوارزمية أبوستوليكو-جيانكارلوa>Apostolico–Giancarlo على تسريع عملية التحقق مما إذا كان قد حدث تطابق في المحاذاة المحددة عن طريق تخطي مقارنات الأحرف الصريحة. وتستخدم هذه المعلومات التي تم جمعها أثناء المعالجة المسبقة للنمط بالتزامن مع أطوال مطابقة اللواحق المسجلة في كل محاولة مطابقة. وعملية تخزين أطوال مطابقة اللواحق تتطلب جدولاً إضافيًا يساوي حجم النص الذي يتم البحث عنه.

تعمل خوارزمية رايتا Raita على تحسين أداء خوارزمية بوير- مور- هورسبول. ويختلف نمط البحث عن سلسلة فرعية معينة في سلسلة معينة عن خوارزمية بوير- مور - هورسبولl.

 مراجع 

 روابط خارجية 

 الورقة الأصلية حول خوارزمية بوير مور
 مثال على خوارزمية بوير مور من الصفحة الرئيسية لجيه ستروثر مور ، المخترع المشارك للخوارزمية
 ورقة ريتشارد كول لعام 1991 التي تثبت خطية وقت التشغيل

تصنيف:استحداثات متعلقة بالحواسيب في 1977