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

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

في علوم الحاسوب ، تُعدّ خوارزمية بوير-مور للبحث عن السلاسل النصية خوارزمية فعّالة ، وهي المعيار المرجعي في أدبيات البحث العملي عن السلاسل النصية. [ 1 ] طُوّرت هذه الخوارزمية على يد روبرت س. بوير وج . ستروثر مور عام 1977. [ 2 ] احتوت الورقة البحثية الأصلية على جداول ثابتة لحساب تحولات الأنماط دون شرح لكيفية إنتاجها. نُشرت خوارزمية إنتاج هذه الجداول في ورقة بحثية لاحقة، احتوت بدورها على أخطاء صحّحها فويتشيك ريتر عام 1980. [ 3 ] [ 4 ]

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

التعريفات

أشمالPأشمالمأشمال-
Pأشمال------
-Pأشمال-----
--Pأشمال----
---Pأشمال---
----Pأشمال--
-----Pأشمال-
محاذاة النمط PAN مع النص ANPANMAN ، من k=3 إلى k=8 . يحدث تطابق عند k=5 .
  • يرمز T إلى النص المدخل المراد البحث فيه. طوله n .
  • يرمز P إلى السلسلة المراد البحث عنها، والتي تسمى النمط . طولها m .
  • يشير S [ i ] إلى الحرف الموجود في الفهرس i من السلسلة S ، بدءًا من 1.
  • S [ i .. j ] تشير إلى السلسلة الفرعية من السلسلة 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 ] .

وصف

تبحث خوارزمية بوير-مور عن حالات ظهور الحرف P في النص T من خلال إجراء مقارنات صريحة للأحرف في محاذاة مختلفة. بدلاً من البحث الشامل في جميع المحاذاة (والتي يوجد منها ⁠ن-م+1{\displaystyle n-m+1}) ، يستخدم Boyer–Moore المعلومات التي تم الحصول عليها من خلال المعالجة المسبقة لـ P لتخطي أكبر عدد ممكن من عمليات المحاذاة.

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

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

بصورة أكثر رسمية، تبدأ الخوارزمية عند المحاذاةك=م{\displaystyle k=m}لذا ، تتم محاذاة بداية P مع بداية T. ثم تُقارنالأحرف في P و T بدءًا من الفهرس m في P و k في T ، مع التحرك للخلف. تُطابق السلاسل من نهاية P إلى بداية P. تستمر المقارنات حتى الوصول إلى بداية P (مما يعني وجود تطابق) أو حدوث عدم تطابق، وعندها تُزاح المحاذاة للأمام (إلى اليمين) وفقًا للقيمة القصوى المسموح بها وفقًا لعدد من القواعد. تُجرى المقارنات مرة أخرى عند المحاذاة الجديدة، وتتكرر العملية حتى تتجاوز المحاذاة نهاية T ، مما يعني عدم العثور على أي تطابقات أخرى.

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

قواعد المناوبة

يتم حساب الإزاحة بتطبيق قاعدتين: قاعدة الأحرف غير الصالحة وقاعدة اللواحق الصالحة. وتكون قيمة الإزاحة الفعلية هي القيمة القصوى للإزاحات المحسوبة بهاتين القاعدتين.

قاعدة الشخصية السيئة

وصف

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

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

المعالجة المسبقة

تختلف الطرق في الشكل الدقيق الذي يجب أن يتخذه جدول قاعدة الأحرف غير الصالحة، ولكن الحل البسيط للبحث في وقت ثابت هو كما يلي: إنشاء جدول ثنائي الأبعاد مفهرس أولاً بفهرس الحرف c في الأبجدية وثانياً بفهرس i في النمط. سيعيد هذا البحث ظهور الحرف c في P ذي الفهرس الأعلى التالي .ج<أنا{\displaystyle j<i}أو -1 إذا لم يحدث ذلك. وسيكون التحول المقترح حينهاأنا-ج{\displaystyle ij}، مع​يا(1){\displaystyle O(1)}وقت البحث ويا(كم){\displaystyle O(km)}الفضاء ، بافتراض أبجدية محدودة بطول k .

تتضمن تطبيقات C و Java أدناه ⁠يا(ك){\displaystyle O(k)}تعقيد المساحة (make_delta1، makeCharTable). هذا هو نفسه delta1 الأصلي وجدول الأحرف السيئة BMH . يقوم هذا الجدول بتعيين حرف في الموضع ⁠أنا{\displaystyle i}للتغيير بمقدار​لين⁡(ص)-1-أنا{\displaystyle \operatorname {len} (ع)-1-i}، مع إعطاء الأولوية لآخر حالة - وهي أقل قيمة إزاحة. يتم تعيين جميع الأحرف غير المستخدمة على أنها ⁠لين⁡(ص){\displaystyle \operatorname {len} (p)}كقيمة حارس .

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

وصف

----X--ك-----
مأشمالPأشمالأمأشمالأP-
أشمالأمPشمالأم-----
----أشمالأمPشمالأم-
توضيح قاعدة اللواحق الجيدة مع النمط P = ANAMPNAM . هنا، t هو T [6..8] و t ′ هو P [2..4].

تُعدّ قاعدة اللواحق الجيدة أكثر تعقيدًا بشكل ملحوظ، سواءً من حيث المفهوم أو التطبيق، من قاعدة الأحرف السيئة. ومثل قاعدة الأحرف السيئة، تستغلّ هذه القاعدة أيضًا خاصية الخوارزمية المتمثلة في بدء المقارنات من نهاية النمط والتقدم نحو بدايته. ويمكن وصفها على النحو التالي: [ 5 ]

لنفترض أنه بالنسبة لمحاذاة معينة لـ P و T ، فإن السلسلة الفرعية t من T تطابق لاحقة من P ولنفترض أن t هي أكبر سلسلة فرعية من هذا النوع للمحاذاة المعطاة.

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

المعالجة المسبقة

تتطلب قاعدة اللاحقة الجيدة جدولين: أحدهما للاستخدام في الحالة العامة (حيث يتم العثور على نسخة t ′ )، والآخر للاستخدام عندما لا تُرجع الحالة العامة أي نتيجة ذات معنى. سيتم تسمية هذين الجدولين L و H على التوالي. تعريفاتهما كما يلي: [ 5 ]

لكل i ،​ل[أنا]{\displaystyle L[i]}⁠ هو أكبر موضع أقل من m بحيث يكون السلسلة ⁠P[أنا..م]{\displaystyle P[i..m]}يطابق لاحقة منP[1..ل[أنا]]{\displaystyle P[1..L[i]]}بحيث لا يكون الحرف الذي يسبق تلك اللاحقة مساوياً لـP[أنا-1]{\displaystyle P[i-1]}.​​ل[أنا]{\displaystyle L[i]}يُعرَّف بأنه يساوي صفرًا إذا لم يكن هناك موضع يحقق الشرط.

دع​ح[أنا]{\displaystyle H[i]}⁠ تشير إلى طول أطول لاحقة من ⁠P[أنا..م]{\displaystyle P[i..m]}وهذا أيضًا بادئة لـ P ، إن وُجدت. إذا لم توجد، فليكنح[أنا]{\displaystyle H[i]}أن يكون صفرًا.

يمكن إنشاء كلا الجدولين فييا(م){\displaystyle O(m)}الوقت والاستخدام​يا(م){\displaystyle O(m)}الفضاء . يُعطىإزاحة المحاذاة للفهرس i في P بواسطةم-ل[أنا]{\displaystyle m-L[i]}أو​​م-ح[أنا]{\displaystyle m-H[i]}لاينبغي استخدام H إلا إذال[أنا]{\displaystyle L[i]}إما أن تكون القيمة صفرًا أو تم العثور على تطابق.

مثال على استخدام نمط التحويل ANPANMAN

فهرسة | عدم تطابق | إزاحة 0 | N| 1 1 | AN | 8 2 | رجل | 3 3 | NMAN | 6 4 | أنمان | 6 5 | بانمان | 6 6 | NPANMAN | 6 7 | أنبانمان| 6

توضيح:

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

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

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

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

قاعدة الجليل

قدّم تسفي غاليل في عام 1979 تحسينًا بسيطًا ولكنه هام لخوارزمية بوير-مور. [ 7 ] على عكس الإزاحة، تُعنى قاعدة غاليل بتسريع المقارنات الفعلية التي تُجرى عند كل محاذاة عن طريق تخطي الأجزاء المعروفة بتطابقها. لنفترض أنه عند المحاذاة k1 ، تتم مقارنة P مع T حتى الحرف c من T. إذا تم إزاحة P إلى k2 بحيث يكون طرفها الأيسر بين c و k1 ، ففي مرحلة المقارنة التالية ، يجب أن يتطابق بادئة P مع السلسلة الفرعية T [( k2 - n ).. k1 ] . وبالتالي ، إذا وصلت المقارنات إلى الموضع k1 من T ، يمكن تسجيل ظهور P دون الحاجة إلى مقارنة صريحة لما بعد k1 . بالإضافة إلى زيادة كفاءة خوارزمية بوير-مور، تُعد قاعدة غاليل ضرورية لإثبات التنفيذ الخطي في أسوأ الحالات.

قاعدة غاليل، في صيغتها الأصلية، فعّالة فقط مع السلاسل التي تُخرج عدة تطابقات. وهي تُحدّث نطاق السلسلة الفرعية فقط عند c = 0 ، أي عند التطابق الكامل. وقد نُشرت نسخة مُعمّمة منها للتعامل مع التطابقات الفرعية في عام 1985 تحت اسم خوارزمية أبوستوليكو-جيانكارلو . [ 8 ]

أداء

يبلغ وقت تشغيل خوارزمية بوير-مور، كما وردت في الورقة الأصلية، في أسوأ الحالات ⁠يا(ن+م){\displaystyle O(n+m)}فقط إذا لم يظهر النمطفي النص. وقد أثبت ذلك لأول مرة كل منكنوت وموريس وبرات عام1977، [ 3 ] ثم غيباس وأودليزكوعام 1980 [ 9 ] بحد أقصى 5 مقارنات في أسوأ الحالات. وقدّم ريتشارد كول برهانًا بحد أقصى 3 مقارنات في أسوأ الحالات عام 1991. [ 10 ] وهناك تعديل بسيط لخوارزمية BM يُحسّن الحد إلى 2 م . [ 11 ]

عندما يظهر النمط في النص، يكون وقت تشغيل الخوارزمية الأصلية هو ⁠يا(نم){\displaystyle O(nm)}في أسوأ الأحوال. يسهل ملاحظة ذلك عندما يتكون كل من النمط والنص من نفس الحرف المتكرر فقط. مع ذلك، يؤدي تضمين قاعدة جاليل إلى زمن تشغيل خطي في جميع الحالات. [ 7 ] [ 10 ]

أظهر كل من كنوت وموريس وبرات أيضًا أن متوسط ​​عدد مقارنات الأحرف في نص عشوائي يكون محدودًا بـيا(نسجلك⁡مم){\displaystyle O\left({\frac {n\log _{k}m}{m}}\right)}، أينك{\displaystyle k}حجم الحروف الأبجدية.

التطبيقات

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

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

المتغيرات

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

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

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

ملحوظات

  1. يمثل m طول سلسلة النمط التي نبحث عنها في النص، والتي يبلغ طولها n . يُستخدم هذا الوقت لإيجاد جميع حالات ظهور النمط، دون استخدام قاعدة جاليل.
  2. ↑ k هو حجم الأبجدية. هذه المساحة مخصصة لجدول الأحرف غير الصالحة الأصلي delta1 في تطبيقات C و Java وجدول اللواحق الصالحة.

مراجع

  1. ↑ هيوم، أندرو؛ صنداي، دانيال (نوفمبر 1991). "البحث السريع عن السلاسل النصية". البرمجيات: الممارسة والخبرة . 21 (11): 1221-1248 . doi : 10.1002/spe.4380211105 . S2CID 5902579 . 
  2. ↑ بوير، روبرت س .؛ مور، ج. ستروثر (أكتوبر 1977). "خوارزمية بحث سريعة عن السلاسل النصية" . مجلة الاتصالات ACM . 20 (10). نيويورك: رابطة آلات الحوسبة: 762-772 . doi : 10.1145/359842.359859 . ISSN 0001-0782 . S2CID 15892987 .  
  3. 1 2 كنوت، دونالد إي .؛ موريس، جيمس إتش. الابن ؛ برات، فوغان آر. (1977). "مطابقة الأنماط السريعة في السلاسل النصية" . مجلة SIAM للحوسبة . 6 (2): 323-350 . CiteSeerX 10.1.1.93.8147 . doi : 10.1137/0206024 . ISSN 0097-5397 .  
  4. ↑ ريتر، فويتش (1980). "خوارزمية معالجة مسبقة صحيحة للبحث عن السلاسل باستخدام خوارزمية بوير-مور". مجلة SIAM للحوسبة . 9 (3): 509-512 . doi : 10.1137/0209037 . ISSN 0097-5397 . 
  5. 1 2 غوسفيلد، دان (1999) [1997]، "الفصل 2 - المطابقة التامة: الطرق الكلاسيكية القائمة على المقارنة"، خوارزميات على السلاسل والأشجار والمتتاليات ( الطبعة الأولى)، مطبعة جامعة كامبريدج، الصفحات 19-21 ، ISBN   0-521-58519-8
  6. ↑ "إنشاء جدول لواحق جيد - فهم مثال" . ستاك أوفرفلو . 11 ديسمبر 2014. تم الاطلاع عليه في 30 يوليو 2024 . تتضمن هذه المقالة نصًا من هذا المصدر، وهو متاح بموجب ترخيص CC BY-SA 3.0 .
  7. 1 2 جاليل، ز. (سبتمبر 1979). "حول تحسين أسوأ وقت تشغيل لخوارزمية مطابقة السلاسل بوير-مور" . مجلة الاتصالات ACM . 22 (9). نيويورك: رابطة آلات الحوسبة: 505-508 . doi : 10.1145/359146.359148 . ISSN 0001-0782 . S2CID 1333465 .  
  8. ↑ أبوستوليكو، ألبرتو؛ جيانكارلو، رافاييل (فبراير 1986). "إعادة النظر في استراتيجيات البحث عن السلاسل النصية لبوير-مور-غاليل" . مجلة SIAM للحوسبة . 15 : 98-105 . doi : 10.1137/0215007 .
  9. ↑ غيباس، ليونيداس ؛ أودليزكو، أندرو (1977). "برهان جديد على خطية خوارزمية بوير-مور للبحث عن السلاسل النصية" . المؤتمر السنوي الثامن عشر حول أسس علوم الحاسوب (SFCS 1977) . جمعية مهندسي الكهرباء والإلكترونيات (IEEE). الصفحات 189-195 . doi : 10.1109/SFCS.1977.3 . S2CID 6470193 .  
  10. 1 2 كول، ريتشارد (سبتمبر 1991). حدود دقيقة لتعقيد خوارزمية مطابقة السلاسل لبوير-مور . جمعية الرياضيات الصناعية والتطبيقية. ص 224-233 . ISBN  0-89791-376-0.
  11. ↑ كروشيمور، ماكسيم؛ وآخرون (1994). "تسريع خوارزميتين لمطابقة السلاسل النصية" . Algorithmica . 12 (24): 247–267 . doi : 10.1007/BF01185427 . 
  12. ↑ هارتل، مايك (21 أغسطس 2010). "لماذا برنامج GNU grep سريع" . أرشيف القائمة البريدية FreeBSD-current .