مقدمة: حكاية من قلب المعركة البرمجية
يا جماعة الخير، اسمعوا مني هالحكاية. قبل كم سنة، كنت شغال على مشروع كبير، نظام تحليل سجلات (Logs) لشركة ضخمة. الفكرة كانت بسيطة: النظام يقرأ ملايين الأسطر من ملفات السجلات كل دقيقة، ويبحث عن أنماط معينة بتدل على أخطاء أو هجمات أمنية. في البداية، الأمور كانت “عال العال”. بنيت النموذج الأولي باستخدام أبسط طريقة ممكنة للبحث عن نص داخل نص آخر، اللي هي البحث الخطي أو زي ما بحبوا يسموها بالإنجليزي “Naive Search”.
في مرحلة الاختبار على كمية بيانات قليلة، كل شيء كان تمام والعميل مبسوط. لكن يوم الإطلاق الحقيقي، يوم ما شبكنا النظام على السيرفرات اللي بتضخ بيانات حقيقية… وقع الفأس بالرأس. النظام صار بطيء لدرجة الشلل. استهلاك المعالج (CPU) وصل 100%، والذاكرة (RAM) كانت تصرخ وتستغيث. التنبيهات كانت توصل متأخرة بساعات، والموبايل ما كان يهدا من اتصالات مدير المشروع اللي صوته كان يوصلني من رام الله لآخر الدنيا.
شعرت بإحباط ما بعده إحباط. هل يعقل إنه مشروع شهور من التعب ينهار بسبب وظيفة بحث بسيطة؟ قعدت مع حالي، فنجان القهوة السادة جنبي، وصرت أراجع كل سطر كتبته. وقتها، لمعت في بالي ذكرى من أيام الجامعة، من محاضرة الخوارزميات اللي كان يعطينا إياها دكتور الله يذكره بالخير. ذكرى خوارزمية كان اسمها غريب شوي… KMP. يومها كنت أحكي لحالي “شو هالحكي الفاضي النظري، مين بستخدم هالأشياء؟”. ما كنت أعرف إنه هذي الذكرى راح تكون طوق النجاة.
المشكلة: لماذا كان البحث الخطي (Naive Search) كابوسًا؟
قبل ما نحكي عن المنقذ KMP، خلينا نفهم أصل المشكلة. ليش الطريقة “البديهية” للبحث كانت كارثية؟
كيف يعمل البحث الخطي؟
الفكرة بسيطة جدًا، زي ما اسمها بدل. لو بدك تبحث عن كلمة “فلسطين” في نص طويل، بتعمل الآتي:
- بتاخذ كلمة “فلسطين” (بنسميها النمط أو Pattern).
- بتحطها عند بداية النص الكبير (Text).
- بتقارن حرف بحرف. إذا كل الحروف تطابقت، مبروك، لقيت الكلمة.
- إذا حصل عدم تطابق، “بتسحب” كلمة “فلسطين” خانة واحدة لليمين، وبترجع تعيد المقارنة من أول وجديد.
خلينا نشوف مثال بسيط. بدنا نبحث عن النمط "ABABC" في النص "ABABDABACDABABCABAB".
النص: ABABDABACDABABCABAB
النمط: ABABC
↑
(تطابق)
النص: ABABDABACDABABCABAB
النمط: ABABC
↑
(تطابق)
النص: ABABDABACDABABCABAB
النمط: ABABC
↑
(تطابق)
النص: ABABDABACDABABCABAB
النمط: ABABC
↑
(تطابق)
النص: ABABDABACDABABCABAB
النمط: ABABC
↑
(هنا فشل! D لا تساوي C)
لما فشلت المقارنة، شو بنعمل؟ البحث الخطي بقول لك: “انسى كل اللي فات، وحرك النمط خطوة واحدة بس لليمين وارجع قارن من الصفر”. وهذا هو مكمن الغباء (مع احترامي للاسم Naive).
أين تكمن الكارثة؟ (التعقيد الزمني)
الكارثة تكمن في هذه العودة العمياء للبداية. في المثال السابق، لما فشلت المقارنة عند حرف D، كنا بنعرف إنه أول 4 حروف من النمط (ABAB) تطابقوا مع النص. هاي معلومة ثمينة جدًا! البحث الخطي برميها في الزبالة وبرجع يبدأ من جديد، مقارنًا الحرف الثاني من النص مع أول حرف من النمط. هذا التكرار غير الضروري هو اللي بقتل الأداء.
بلغة الأرقام، لو طول النص هو n وطول النمط هو m، ففي أسوأ الأحوال (تخيل نص كله حرف ‘A’ وبتبحث عن ‘AA…AB’)، راح تحتاج لـ O(n * m) عملية. لما يكون عندك نصوص بحجم الجيجابايت، هذا الرقم بصير فلكي، والسيرفر “بجيم” وبقعد يعيط.
الحل السحري: خوارزمية KMP.. مش مجرد حروف!
هنا يأتي دور الأبطال الثلاثة: Donald Knuth، و James H. Morris، و Vaughan Pratt. هؤلاء العباقرة فكروا بطريقة مختلفة تمامًا. قالوا: “ليش نرجع لوراء بشكل أعمى؟ ليش ما نستخدم المعلومات اللي جمعناها من التطابق الجزئي عشان نقفز قفزة ذكية للأمام؟”
الفكرة العبقرية وراء KMP
الفكرة الأساسية في KMP هي: عند حدوث عدم تطابق، لا تحرك مؤشر النص للخلف أبدًا. بدلًا من ذلك، انظر إلى النمط نفسه، واستخدم هيكله الداخلي لتحديد مقدار “القفزة” التي يجب أن تقفزها للأمام.
كيف؟ عن طريق تحليل النمط مرة واحدة فقط قبل البدء بالبحث، وإنشاء جدول مساعد صغير. هذا الجدول هو العقل المدبر للعملية كلها.
مفتاح اللغز: جدول LPS (أطول بادئة تطابق لاحقة)
اسم الجدول ممكن يخوف شوي، “Longest Proper Prefix which is also a Suffix”، أو اختصارًا LPS. بس فكرته بسيطة. خلينا نفصصه:
- البادئة (Prefix): جزء من بداية الكلمة (ليس الكلمة كلها).
- اللاحقة (Suffix): جزء من نهاية الكلمة (ليس الكلمة كلها).
لكل جزء من النمط، بدنا نعرف ما هي أطول سلسلة حروف تكون في نفس الوقت بادئة ولاحقة لهذا الجزء. خلينا ناخذ مثال عملي، النمط "AABAACAABAA".
لما نوصل للحرف A في الموقع 4 (الكلمة الجزئية هي AABAA):
- البادئات:
A,AA,AAB,AABA - اللاحقات:
A,AA,BAA,ABAA
أطول سلسلة مشتركة هي "AA"، وطولها 2. إذن، قيمة LPS عند هذا الموقع هي 2.
جدول LPS الكامل للنمط "AABAACAABAA" (طوله 11) سيكون هكذا:
النمط: A A B A A C A A B A A
الفهرس: 0 1 2 3 4 5 6 7 8 9 10
LPS: 0 1 0 1 2 0 1 2 3 4 5
طيب شو فائدة هذا الجدول يا أبو عمر؟ فائدته جبارة. قيمة LPS عند أي نقطة بتخبرك، في حال فشلت المقارنة، وين ترجع في النمط (وليس في النص) عشان تكمل مقارنة. الرقم lps[i] هو فعليًا طول البادئة التالية اللي ممكن تتطابق، فبتقدر تقفز مباشرة بدون ما ترجع لوراء في النص الأصلي.
لنبني جدول LPS: الكود خطوة بخطوة
كتابة كود بناء جدول LPS هي قلب الخوارزمية. ممكن تبين معقدة لأول وهلة، بس إذا فهمت الفكرة، بتصير منطقية. هذا مثال بايثون مع شرح وافٍ:
def compute_lps_array(pattern):
m = len(pattern)
lps = [0] * m # إنشاء مصفوفة LPS وملؤها بالأصفار
length = 0 # طول أطول بادئة تطابق لاحقة سابقة
i = 1
# الحلقة تبدأ من ثاني حرف لأن lps[0] دائمًا صفر
while i < m:
if pattern[i] == pattern[length]:
# إذا تطابق الحرف الحالي مع الحرف الموجود عند 'length'
length += 1
lps[i] = length
i += 1
else:
# إذا لم يتطابقا
if length != 0:
# لا نرجع للصفر مباشرة، بل نعود للـ lps السابق
# هذا هو الجزء السحري، القفزة الذكية داخل النمط نفسه
length = lps[length - 1]
else:
# إذا وصلنا للبداية (length=0)، فلا يوجد تطابق
lps[i] = 0
i += 1
return lps
نصيحة من أبو عمر: لا تحفظ هذا الكود حفظًا. حاول أن تتبعه يدويًا على ورقة وقلم باستخدام نمط مثل
"AAABAAA". عندما “تراها” بعينك، لن تنساها أبدًا.
تطبيق KMP على أرض الواقع: من النظرية إلى الكود
بعد ما جهزنا جدول LPS، صار البحث نفسه عملية سهلة ومباشرة جدًا.
خوارزمية البحث الرئيسية
الآن، نمشي على النص والنمط بمؤشرين (i للنص و j للنمط).
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
if m == 0:
return [] # لا يمكن البحث عن نمط فارغ
lps = compute_lps_array(pattern)
found_indices = []
i = 0 # مؤشر للنص
j = 0 # مؤشر للنمط
while i < n:
if pattern[j] == text[i]:
# تطابق! تقدم في كلا المؤشرين
i += 1
j += 1
if j == m:
# مبروك! وجدنا النمط كاملًا
# نضيف فهرس بداية التطابق
found_indices.append(i - j)
# نستمر بالبحث عن تطابقات أخرى باستخدام جدول LPS
j = lps[j - 1]
elif i < n and pattern[j] != text[i]:
# عدم تطابق بعد تطابق جزئي
if j != 0:
# هنا القفزة الذكية! لا نحرك i
# فقط نرجع j إلى الخلف حسب جدول LPS
j = lps[j - 1]
else:
# عدم تطابق عند أول حرف في النمط
# فقط تقدم في النص
i += 1
return found_indices
# مثال الاستخدام
text = "ABABDABACDABABCABAB"
pattern = "ABABC"
result = kmp_search(text, pattern)
print(f"تم العثور على النمط في الفهرس: {result}") # سيطبع: [10]
مقارنة الأداء: الأرقام لا تكذب
الآن، نأتي للحظة الحقيقة. ما هو التعقيد الزمني لخوارزمية KMP؟
- بناء جدول LPS يأخذ وقتًا
O(m)حيثmهو طول النمط. - عملية البحث نفسها تأخذ وقتًا
O(n)حيثnهو طول النص (لأن المؤشرiلا يرجع للخلف أبدًا).
إذًا، التعقيد الإجمالي هو O(n + m). مقارنة بـ O(n * m) للبحث الخطي، هذا فرق السماء عن الأرض! في مشروعي، البحث الذي كان يستغرق دقائق وساعات، أصبح يتم في أجزاء من الثانية. كأني انتقلت من عربة تجرها الخيول إلى سيارة فيراري.
نصائح من أبو عمر (خلاصة التجربة)
- لا تستخف بالأساسيات: الخوارزميات وهياكل البيانات التي تعلمتها في الجامعة ليست مجرد “حكي نظري”. هي الأدوات الحقيقية التي تميز المبرمج المحترف عن الهاوي. استثمر وقتًا في فهمها بعمق.
- اعرف متى تستخدم KMP: هذه الخوارزمية تتألق عندما تبحث عن نمط ثابت بشكل متكرر في نصوص طويلة أو متغيرة. إذا كان النمط يتغير في كل مرة، فإن تكلفة حساب جدول LPS قد لا تكون مجدية.
- قِس قبل أن تحسّن (Profile before you optimize): قبل أن تقفز لتغيير خوارزمية البحث، تأكد أولًا أن البحث هو فعلًا “عنق الزجاجة” في تطبيقك. استخدم أدوات تحليل الأداء (Profilers) لتحديد الأجزاء البطيئة بدقة.
- انظر إلى البدائل: KMP رائعة، لكنها ليست الوحيدة. خوارزمية Boyer-Moore غالبًا ما تكون أسرع في الممارسة العملية لأنها تبدأ المقارنة من نهاية النمط، مما يسمح بقفزات أكبر. خوارزمية Rabin-Karp تستخدم التجزئة (Hashing) وهي ممتازة للبحث عن عدة أنماط مختلفة في نفس الوقت.
الزبدة والخلاصة النهائية 💡
رحلتي مع البحث الخطي و KMP علمتني درسًا لن أنساه: البرمجة ليست مجرد كتابة كود “يعمل”، بل هي فن وعلم حل المشاكل بأكثر الطرق كفاءة وذكاء. في عالم البيانات الضخمة اليوم، الكود البطيء ليس مجرد إزعاج، بل هو فشل في التصميم.
عندما تواجهك مشكلة أداء، لا تستسلم للحلول السطحية. ارجع للأساسيات، فكّر في بنية المشكلة، وابحث عن الأداة (الخوارزمية) الصحيحة للمهمة. استثمار ساعة في فهم خوارزمية مثل KMP يمكن أن يوفر عليك أيامًا من الصداع ومكالمات العملاء الغاضبين. تذكر دائمًا، الكود الأنيق ليس فقط الكود النظيف، بل هو أيضًا الكود السريع والذكي. والله ولي التوفيق.
