مرجع
آخر الزيارات

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

2٬042 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: خوارزمية بوير-مور للبحث في السلاسل النصية Boyer–Moore string-search algorithm- في علوم الكمبيوتر، تُعد خوارزمية البحث عن السلاسل بوير-مور خوارزمية فعالة للبحث عن السلاسل، وهي المعيار القياسي لأدبيات البحث العملي عن السلاسل. تتناول المقالة 13 قسماً، منها «7 – ANPANMAN – 6»، «وصف» و«التنفيذات».
المحتويات
  1. 7 – ANPANMAN – 6
  2. وصف
  3. التنفيذات
  4. قاعدة جليل
  5. وصف
  6. التعاريف
  7. الأداء
  8. المعالجة المسبقة
  9. المتغيرات
  10. قواعد التحول
  11. الورقة الأصلية حول خوارزمية بوير مور
  12. المعالجة المسبقة
  13. وصف

في البداية، خوارزمية بوير-مور للبحث في السلاسل النصية Boyer–Moore string-search algorithm- في علوم الكمبيوتر، تُعد خوارزمية البحث عن السلاسل بوير-مور خوارزمية فعالة للبحث عن السلاسل، وهي المعيار القياسي لأدبيات البحث العملي عن السلاسل. وقد تم تطويرها بواسطة كل من: روبرت إس. بوير، وجيه ستروثر مور، وذلك في سنة 1977م. تحتوي الورقة البحثية الأصلية على جداول ثابتة لحساب تحولات النمط دون توضيح لكيفية إنتاجها. وتم نشر الخوارزمية المستعملة في إنتاج الجداول في ورقة بحثية لاحقة؛ وقد احتوت هذه الورقة على أخطاء تم تصحيحها لاحقًا بواسطة فويتشيك ريتر في عام 1980م. وتعرض الأقسام التالية جوانب أخرى من الموضوع.

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

7 – ANPANMAN – 6

توضيح:

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

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

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

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

وصف

من جانب آخر، إذا لم يكن مثل هذا التحول ممكنًا، فقم بتحويل P بمقدار m (طول P) إلى اليمين.

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

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

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

وعلى صعيد آخر، توضيح قاعدة اللواحق الجيدة باستخدام النمط P = ANAMPNAM. حيث t يساوي T[6..8] وt′ يساوي P[2..4].افترض أنه بالنسبة لمحاذاة معينة بين P و T، فإن السلسلة الفرعية t من T تطابق لاحقة P وافترض أن t هي أكبر سلسلة فرعية من هذا القبيل للمحاذاة المحددة.

التنفيذات

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

علاوةً على ذلك، كما تُستعمل خوارزمية بوير- مور كذلك في جريب grep الخاص بـ جنو GNU.

قاعدة جليل

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

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

وصف

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

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

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

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

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

التعاريف

وفي هذا السياق، محاذاة P إلى T هي مؤشر k في T بحيث يتم محاذاة الحرف الأخير من P مع المؤشر k في T.

إضافةً إلى ذلك، البادئة S هي سلسلة فرعية S [1.. i ] لبعض i في النطاق [1, l ]، حيث l هو طول S.

  • محاذاة نمط 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 [ i .. l ] لبعض i في النطاق [1، l ]، حيث l هو طول S.

وفي هذا الصدد، يحدث تطابق أو حدوث P عند محاذاة k إذا كان P يعادل T [( k - m +1).. k ].

الأداء

وفي هذا الصدد، خوارزمية بوير- مور كما تم تقديمها في الورقة الأصلية لها لها زمن تشغيل في أسوء الحالات قدره فقط إذا لم يظهر النمط في النص. وقد تم إثبات ذلك لأول مرة بواسطة دونالد كينوث Knuth وجيمس موريس Morris وهيو برات Pratt في سنة 1977م، ثم تبعهم كل من: غيباس Guibas و أودلي زكوOdlyzko في سنة 1980م مع حد أعلى يبلغ مقارنة في أسوأ الحالات. وأعطى ريتشارد كول دليلاً بحد أقصى مقارنة في أسوأ الحالات في سنة 1991م.

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

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

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

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

المتغيرات

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

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

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

روابط خارجية

مراجع

قواعد التحول

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

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

الورقة الأصلية حول خوارزمية بوير مور

في هذا الإطار، مثال على خوارزمية بوير مور من الصفحة الرئيسية لجيه ستروثر مور ، المخترع المشارك للخوارزمية

ورقة ريتشارد كول لعام 1991 التي تثبت خطية وقت التشغيل

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

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

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

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

وصف

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.