خوارزمية Boyer-Moore: كيف تبحث عن النصوص بسرعة عبر تخطي الحروف

Boyer-Moore هي خوارزمية للبحث عن سلسلة نصية (نمط) داخل نص أكبر، وسرّ سرعتها أنها لا تفحص كل حرف. بدلاً من المقارنة حرفاً بحرف من البداية، تقارن النمط من اليمين إلى اليسار، وعند أول عدم تطابق تقفز عدة مواضع دفعةً واحدة بدلاً من التحرك خطوة واحدة. هذا التخطي الذكي يجعلها من أسرع خوارزميات البحث عملياً على النصوص الطويلة، لدرجة أنها الأساس التاريخي لأمر grep في أنظمة يونكس ولوظيفة البحث (Ctrl+F) في كثير من المحررات.

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

الفكرة الأساسية: لماذا القراءة من اليمين؟

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

Boyer-Moore تقلب الترتيب: تحاذي النمط ثم تقارن آخِر حرف فيه أولاً. الفائدة أنّ الفشل المبكر يكشف معلومة قوية. فإذا كان الحرف المقابل في النص لا يظهر أصلاً في النمط، فلا فائدة من أي محاذاة تضع هذا الحرف داخل النمط، ويمكن قفز طول النمط كاملاً. كلما طال النمط، زادت القفزات وقلّت المقارنات، وهذا عكس ما نتوقعه حدسياً.

القاعدتان اللتان تحكمان القفز

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

1. قاعدة الحرف السيّئ (Bad Character): عند عدم التطابق، ننظر إلى الحرف الفعلي في النص. إن كان موجوداً داخل النمط، نُزحزح النمط حتى يتحاذى أقرب ظهور لهذا الحرف مع موضعه في النص. وإن كان غير موجود إطلاقاً، نقفز النمط بأكمله بعده. (هذا ما سمّاه النصّ القديم "جدول النقل السريع".)

2. قاعدة اللاحقة الجيّدة (Good Suffix): إذا كنّا قد طابقنا جزءاً من نهاية النمط قبل أن يفشل حرف، نستفيد من هذا الجزء المطابق ونُزحزح النمط ليتحاذى مع ظهور آخر لنفس المقطع (أو مع بادئة تطابق نهايته). (هذا ما أسماه النصّ القديم "جدول المطابقة الجانبية".)

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

تعقيدها الزمني بدقّة

هنا نقطة يُخطئ فيها كثير من الشروحات المبسّطة، فلنوضّحها:

• التهيئة (بناء الجداول): بمقدار طول النمط زائد حجم الأبجدية تقريباً، أي O(m + σ).
• أفضل حالة: O(n/m)، أي أسرع من قراءة كل حرف؛ لأن كل قفزة قد تتخطى النمط كاملاً.
• أسوأ حالة في النسخة الأصلية: O(n·m) عند البحث عن نمط داخل نص متكرّر (مثل البحث عن aaa في سلسلة طويلة من a).
• مع تحسين Galil: يمكن ضبط الخوارزمية لتضمن O(n + m) حتى في أسوأ الحالات.

ملاحظة عملية غالباً ما تُغفَل: كفاءة Boyer-Moore ترتفع كلما كبُرت الأبجدية وطال النمط. لذلك تتألق في نصوص اللغات الطبيعية، بينما قد يتقلّص تفوّقها في الأبجديات الصغيرة جداً (مثل تسلسلات DNA بأربعة رموز فقط)، حيث تتقارب المسافات بين ظهور الحروف فتقلّ القفزات.

نسخة مبسّطة تُستخدم كثيراً: Boyer-Moore-Horspool

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

Boyer-Moore أم غيرها؟ مقارنة سريعة

المعيار	Boyer-Moore	KMP	Rabin-Karp
اتجاه المقارنة	من اليمين لليسار	من اليسار لليمين	تجزئة (hash)
أسوأ حالة	O(n·m) أصلاً، O(n) مع Galil	O(n + m)	O(n·m) نظرياً
الأداء العملي	ممتاز على النصوص الطويلة	ثابت وموثوق	جيد للبحث عن أنماط متعددة
الأنسب لـ	نص طويل وأبجدية كبيرة	ضمان أداء مستقر	البحث عن عدة أنماط دفعةً واحدة

باختصار: اختر Boyer-Moore حين يكون النص طويلاً والأبجدية غنية، وKMP حين تريد ضمان أداء ثابت لا يتدهور، وRabin-Karp حين تبحث عن مجموعة أنماط في آن واحد.

أين تُستخدم فعلياً؟

• محرّكات البحث داخل المستندات ومحرّرات النصوص (وظيفة "بحث واستبدال").
• أدوات سطر الأوامر مثل grep والبحث عن الأنماط في السجلّات.
• أنظمة كشف التسلل (IDS) للبحث عن توقيعات هجمات معروفة داخل حركة الشبكة.
• البحث عن أنماط في مجموعات بيانات نصية كبيرة قبل مرحلة التحليل.

الأسئلة الشائعة

هل Boyer-Moore دائماً أسرع من غيرها؟ لا. هي سريعة جداً في المتوسط على النصوص الطويلة، لكنها في أسوأ حالاتها (بلا تحسين Galil) قد تصبح أبطأ من KMP الذي يضمن أداءً خطياً ثابتاً.

ما الفرق بينها وبين KMP؟ KMP تقارن من اليسار لليمين وتضمن O(n + m) دائماً. Boyer-Moore تقارن من اليمين لليسار وتتفوّق عملياً بفضل القفزات، لكن ضمانها النظري أضعف ما لم تُحسَّن.

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

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