ما هو البحث بالقوة الغاشمة عن النصوص (Brute Force String Search)؟ شرح مبسّط بالأمثلة

البحث بالقوة الغاشمة عن النصوص (Brute Force String Search) هو أبسط خوارزمية للعثور على سلسلة قصيرة (النمط pattern) داخل نص أطول (النص text). فكرتها كلها في جملة واحدة: جرِّب مطابقة النمط عند كل موضع ممكن في النص، حرفاً بحرف، من البداية حتى النهاية، دون أي تحضير مسبق أو ذكاء إضافي. لهذا تُسمى أيضاً «الخوارزمية الساذجة» (Naive String Matching)، وهي غالباً أول ما يُدرّس في مساقات الخوارزميات لأنها تبني الحدس قبل الانتقال إلى الخوارزميات الأسرع.

كيف تعمل خطوة بخطوة؟

تخيّل أنك تمسك بالنمط كشريط شفاف وتضعه فوق النص بدءاً من الموضع صفر، ثم تحرّكه موضعاً واحداً إلى اليمين في كل مرة:

1. ضع بداية النمط عند الموضع الحالي في النص (نسمّيه i).
2. قارن حروف النمط واحداً واحداً مع الحروف المقابلة في النص.
3. إذا تطابقت كل حروف النمط، فقد وجدت تطابقاً عند الموضع i.
4. إذا اختلف أي حرف (مهما كان قريباً من النهاية)، أوقف المقارنة فوراً، وحرّك النمط موضعاً واحداً (i + 1) وابدأ من جديد.
5. كرّر حتى تصل نهاية النص، أو حتى لا يبقى مكان كافٍ للنمط.

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

مثال عملي

لنبحث عن النمط ABAB داخل النص ABACABAB:

• الموضع 0: ABAC مقابل ABAB → تطابق A، B، A ثم اختلاف عند C. نتحرك.
• الموضع 1: B مقابل A → اختلاف فوري. نتحرك.
• الموضع 2: A مقابل A، ثم C مقابل B → اختلاف. نتحرك.
• الموضع 3: C مقابل A → اختلاف. نتحرك.
• الموضع 4: ABAB مقابل ABAB → تطابق كامل. وجدناه عند الموضع 4.

لاحظ كيف بذلنا مقارنات «ضائعة» عند الموضع 0 قبل أن نفشل في الحرف الأخير.

الكود في أبسط صوره

def brute_force_search(text, pattern):
    n, m = len(text), len(pattern)
    for i in range(n - m + 1):          # كل موضع بداية ممكن
        j = 0
        while j < m and text[i + j] == pattern[j]:
            j += 1
        if j == m:                      # وصلنا لنهاية النمط = تطابق
            return i                    # موضع أول تطابق
    return -1                           # لا يوجد تطابق

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

التعقيد الزمني: متى تكون بطيئة فعلاً؟

• أسوأ حالة: ‏O(n × m) حيث n طول النص وm طول النمط. تحدث حين يطابق النمط جزئياً في كل موضع تقريباً قبل أن يفشل، مثل البحث عن AAAAB داخل نص طويل مكوّن من حرف A مكرر.
• الحالة المتوسطة والعملية: أسرع بكثير من ذلك، وغالباً قريبة من O(n)، لأن معظم المقارنات تفشل من الحرف الأول أو الثاني في النصوص الطبيعية.

هذه المفارقة مهمة: القوة الغاشمة «سيئة نظرياً» لكنها «مقبولة عملياً» في كثير من الاستخدامات اليومية.

متى تستخدمها؟ ومتى تتجنبها؟

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

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

مقارنة سريعة مع الخوارزميات الأشهر

الخوارزمية	الفكرة الأساسية	تحضير مسبق	أسوأ حالة	الأنسب لـ
القوة الغاشمة	مطابقة عند كل موضع من اليسار	لا	‏O(n×m)	نصوص قصيرة، بحث لمرة واحدة
كنوث-موريس-برات (KMP)	تتذكّر ما طابقته لتتجنب الرجوع	O(m)	‏O(n+m)	أنماط ذات حروف متكررة
بويير-مور (Boyer-Moore)	تقارن من اليمين وتقفز قفزات كبيرة	O(m+k)	‏O(n×m) نظرياً، سريعة عملياً	نصوص طويلة، أبجدية كبيرة

الفرق الجوهري: القوة الغاشمة لا تستفيد أبداً من المعلومات التي جمعتها أثناء المطابقة الفاشلة، بينما تبني KMP جدول «إخفاقات» يسمح بتخطي مواضع بلا فائدة، وتستغل بويير-مور المقارنة من نهاية النمط لتقفز أحياناً بمقدار طول النمط كاملاً.

نصيحة عملية وخطأ شائع

الخطأ الأكثر شيوعاً عند كتابتها يدوياً هو حدود الحلقة الخارجية: يجب أن تتوقف عند n - m وليس عند n، وإلا خرجت عن حدود النص وحصلت على خطأ فهرسة (index out of range) عند مقارنة الحرف الأخير من النمط. تذكّر دائماً أن آخر موضع بداية ممكن هو n - m.

نصيحة الأداء: قبل أن تلجأ إلى تعقيد KMP أو بويير-مور، قِس فعلاً. في معظم النصوص الواقعية القوة الغاشمة «سريعة بما يكفي»، والتحسين المبكر يضيف تعقيداً بلا مقابل حقيقي. اكتب الحل البسيط أولاً، ثم حسّنه فقط إذا أثبتت القياسات وجود مشكلة.

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

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

ما الفرق بينه وبين خوارزمية KMP؟ كلاهما يبحث عن نمط داخل نص، لكن القوة الغاشمة تعيد المقارنة من الصفر عند كل إخفاق، بينما تتذكّر KMP الأجزاء المطابقة مسبقاً عبر جدول تحضيري، فتتجنب الرجوع وتضمن زمناً خطياً O(n+m).

هل تجد الخوارزمية كل التطابقات أم أول واحد فقط؟ النسخة الأساسية تُرجع أول تطابق، لكن يمكن بسهولة تعديلها لتكمل البحث بعد كل تطابق وتجمع جميع المواضع في قائمة، دون تغيير الفكرة الأساسية.

هل هي مناسبة للنصوص العربية والحروف الموحّدة (Unicode)؟ نعم، طالما قارنت على مستوى الرموز (characters) لا البايتات، وانتبهت إلى مسائل التطبيع (normalization) مثل الهمزات والتشكيل التي قد تجعل حرفين يبدوان متطابقين بصرياً بينما يختلفان في التمثيل الداخلي.