خوارزمية كنوت-موريس-برات

في علوم الحاسوب **خوارزمية كنوث-موريس-برات** (أو **خوارزمية KMP** )، تُعد خوارزمية كنوث-موريس-برات (KMP) خوارزمية فعالة للبحث عن نمط W داخل نص S. تعتمد الخوارزمية على استغلال المعلومات المتضمنة في النمط نفسه لتحديد نقطة البداية المحتملة للتطابق التالي عند حدوث عدم تطابق، مما يجنب إعادة فحص الأحرف المتطابقة سابقًا.

.

تُنسب خوارزمية كنوث-موريس-برات إلى جيمس هـ. موريس الذي ابتكرها، بينما اكتشفها دونالد كنوث بشكل مستقل بعد أسابيع قليلة بناءً على نظرية الأتمتة. وقد وثق موريس وفوغان برات هذه الخوارزمية في تقرير تقني عام 1970،  ثم نشر الثلاثة عملهم المشترك حولها في عام 1977. وتجدر الإشارة إلى أن يوري ماتيياسيفيتش كان قد توصل بشكل مستقل في عام 1969 إلى خوارزمية مشابهة، تم ترميزها باستخدام آلة تورينج ثنائية الأبعاد، وذلك أثناء بحثه في مشكلة تحديد مطابقة أنماط السلاسل باستخدام أبجدية ثنائية.  وتُعد خوارزميته أول خوارزمية خطية الزمن لحل مشكلة مطابقة السلاسل.

## خلفية
الهدف من خوارزمية مطابقة السلاسل هو تحديد الفهرس الابتدائي (m) في السلسلة النصية S[] حيث يبدأ ظهور كلمة البحث W[] بشكل مطابق.

تُعد خوارزمية "القوة الغاشمة" أو "الخوارزمية الساذجة" أبسط طرق البحث عن تطابق سلسلة فرعية. تعتمد هذه الخوارزمية على فحص احتمالية تطابق كلمة البحث W[] عند كل فهرس m في السلسلة النصية S[]. ولتحقيق ذلك، تبدأ الخوارزمية عند كل موضع m بالتحقق من تطابق الحرف الأول في كلمة البحث مع الحرف المقابل في النص (S[m] == W[0]). وفي حال وجود تطابق أولي، تستمر الخوارزمية في مقارنة الأحرف المتتالية في كلمة البحث (W[i]) مع الأحرف المقابلة في النص بدءًا من الموضع m (S[m+i] == W[i]). إذا تطابقت جميع أحرف W[] بشكل متسلسل عند الموضع m، يتم اعتبار هذا الموضع نقطة تطابق ناجحة. أما إذا وصل الفهرس m إلى نهاية السلسلة S[] دون العثور على تطابق كامل، فإن عملية البحث تُعتبر فاشلة.

عادةً، يرفض الفحص التجريبي المطابقة التجريبية بسرعة. إذا كانت السلاسل أحرفًا عشوائية موزعة بالتساوي، فإن احتمال تطابق الأحرف هو 1 من 26. في معظم الحالات، يرفض الفحص التجريبي المطابقة عند الحرف الأول. احتمال تطابق الحرفين الأولين هو 1 من 26 (احتمال تطابق واحد من 26^2 من أصل 26 حرفًا محتملًا). لذا، إذا كانت الأحرف عشوائية، فإن التعقيد المتوقع للبحث عن السلسلة S[] بطول n يكون من رتبة n مقارنة أو Θ(n). الأداء المتوقع ممتاز. إذا كان طول السلسلة S[] مليون حرف وطول السلسلة W[] 1000 حرف، فيجب أن يكتمل البحث عن السلسلة بعد حوالي 1.04 مليون مقارنة.

هذا الأداء المتوقع ليس مضمونًا دائمًا. ففي حال لم تكن السلاسل عشوائية، قد يتطلب التحقق من كل موضع تجريبي m إجراء مقارنات عديدة للأحرف. وتتجلى أسوأ الحالات عندما تتطابق السلسلتان في جميع الأحرف باستثناء الحرف الأخير. على سبيل المثال، تخيل سلسلة S[] مؤلفة من مليون حرف 'A'، وكلمة بحث W[] تتكون من 999 حرف 'A' متبوعة بحرف 'B' في النهاية. في هذه الحالة، ستقوم خوارزمية مطابقة السلاسل البسيطة بفحص 1000 حرف عند كل موضع تجريبي قبل استبعاد التطابق والانتقال إلى الموضع التالي. ونتيجة لذلك، سيستغرق هذا المثال من البحث البسيط عن السلاسل حوالي 1000 مقارنة حرف مضروبة في مليون موضع، أي ما يقارب مليار مقارنة حرف. وبشكل عام، إذا كان طول W[] هو k وطول S[] هو n، فإن أسوأ أداء للخوارزمية هو O(k⋅n).

تتفوق خوارزمية KMP على الخوارزمية البسيطة من حيث الأداء في أسوأ السيناريوهات. فبخلاف الخوارزمية البسيطة، تستغرق KMP وقتًا وجيزًا لحساب جدول مسبق بحجم يتناسب مع طول كلمة البحث W[] وتعقيده الزمني O(k). بعد ذلك، تستخدم هذه الخوارزمية الجدول لإجراء بحث فعال عن السلسلة في السلسلة النصية الرئيسية S[] بتعقيد زمني قدره O(n).

يكمن الاختلاف الأساسي في أن خوارزمية KMP تستفيد من معلومات التطابقات السابقة التي تتجاهلها الخوارزمية البسيطة. ففي المثال السابق، عندما تواجه KMP فشلًا في التطابق عند الحرف رقم 1000 (i = 999) بسبب اختلاف S[m+999] عن W[999]، فإنها لا تكتفي بزيادة قيمة m بمقدار 1، بل إنها تدرك أيضًا أن أول 998 حرفًا في الموضع الجديد هي بالضرورة متطابقة. والسبب في ذلك هو أن KMP كانت قد طابقت بالفعل 999 حرفًا من 'A' قبل اكتشاف الحرف المختلف في الموضع 999. وعند تقديم موضع التطابق التجريبي m بمقدار واحد، يتم حذف أول حرف 'A'، ونتيجة لذلك، تعلم KMP أن هناك 998 حرفًا من 'A' تتطابق مع بداية W[] دون الحاجة إلى إعادة فحصها؛ أي أن KMP تقوم بتعيين قيمة i إلى 998 مباشرةً. تحتفظ KMP بهذه المعرفة في الجدول الذي تم حسابه مسبقًا وفي متغيري الحالة الخاصين بها. فعندما تكتشف KMP عدم تطابق، يحدد الجدول مقدار الزيادة في m التي يجب تطبيقها وموضع الحرف التالي الذي سيتم فحصه (قيمة i الجديدة).

## خوارزمية KMP

### مثال على خوارزمية البحث
بغرض توضيح تفاصيل عمل الخوارزمية، سنفترض الآن مثالًا تطبيقيًا (وهو مثال اصطناعي إلى حد ما) حيث تكون كلمة البحث W هي "ABCDABD" والسلسلة النصية S هي "ABC ABCDAB ABCDABCDABDE". في أي مرحلة من مراحل تنفيذ الخوارزمية، يمكن وصف حالتها بشكل كامل باستخدام قيمتين صحيحتين:

* **اي ، يشير إلى مؤشر الحرف المعتبر حاليًا في ام .**
* م، تشير إلى الموضع داخل S حيث تبدأ المباراة المحتملة لـ ام،

في كل خطوة من خطوات الخوارزمية، تتم مقارنة الحرف S[m+i] بالحرف W[i]. وفي حال تطابقهما، يتم زيادة قيمة المؤشر i للانتقال إلى الحرف التالي في كل من السلسلة والنص. ويتضح هذا الإجراء في المراحل الأولية لتشغيل الخوارزمية كما يلي:
 1 2 
 ام: 01234567890123456789012
 اس:
 دبيلو:
 اي  :
`تبدأ الخوارزمية بمقارنة الأحرف المتتالية في كلمة البحث W مع الأحرف المقابلة في السلسلة النصية S، وتنتقل إلى الحرف التالي بزيادة قيمة المؤشر i إذا تم العثور على تطابق. ومع ذلك، عند الخطوة الرابعة، يحدث عدم تطابق حيث أن S[3] (فراغ) لا يساوي W[3] ('D'). فبدلًا من إعادة بدء البحث من S[1]، تلاحظ الخوارزمية أنه لا يوجد حرف 'A' بين الموضعين 1 و2 في S. وبما أننا قد تحققنا بالفعل من تطابق هذه الأحرف مع الأحرف المقابلة في W، فإن أي محاولة لبدء تطابق جديد في هذه المنطقة ستكون غير مجدية. لذلك، تقوم الخوارزمية بتحديث قيمة m إلى 3 وإعادة تعيين قيمة i إلى 0، للانتقال إلى بداية محاولة تطابق جديدة من الموضع الثالث في S.`
 1 2 
 م: 01234567890123456789012
 س: أ ب ج
 دبيلو :
 اي :
 نظرًا لعدم تطابق الحرف الأول في عملية البحث، فإن الخوارزمية تُنشئ قيمة m تساوي 4 وقيمة i تساوي 0.
 1          2 
  م: 01234567890123456789012
 س: أ ب ج
 دبيلو:
 اي :
هنا، تزداد قيمة `i` من خلال تطابق شبه كامل `"ABCDAB"` حتى تصبح `i = 6` مما يؤدي إلى عدم تطابق عند `W[6]` و `S[10]` . ومع ذلك، قبل نهاية المباراة الجزئية الحالية مباشرة، كان هناك السلسلة الفرعية `"AB"` التي يمكن أن تكون بداية لمباراة جديدة، لذا يجب على الخوارزمية أخذ ذلك في الاعتبار.وبما أن هذه الأحرف تتطابق مع الحرفين السابقين للموضع الحالي في W، فليس هناك حاجة لإعادة التحقق منها. لذلك، تقوم الخوارزمية بتحديث قيمة m إلى 8 (وهو بداية ظهور البادئة الأولية المتطابقة) وتعيين قيمة i إلى 2 (مما يشير إلى أن أول حرفين قد تطابقا بالفعل)، ثم تستأنف عملية المطابقة من هذا الموضع. وبالتالي، فإن الخوارزمية لا تتجاوز فقط الأحرف المتطابقة سابقًا في S ("AB")، بل تتجاوز أيضًا البادئة المتطابقة في W ("AB").

* 1 2
* م: 01234567890123456789012
* س:ABC ABCD
* دبليو : 
* اي : 

نن يفشل هذا البحث في الموضع الجديد على الفور لأن الحرف W[2] ('C') لا يتطابق مع الحرف S[10] (فراغ). وكما حدث في المحاولة الأولى، يؤدي عدم التطابق إلى إعادة الخوارزمية إلى بداية كلمة البحث W، وتبدأ البحث من موضع الحرف غير المتطابق في S: أي يتم تعيين m = 10 وإعادة تعيين i = 0.

1 2

م: 01234567890123456789012

اس : ABC ABCDAB

دبيلو : 

اي : 

 

A BCDABD i:  0 123456

تفشل المطابقة عند m=10 على الفور، لذا تحاول الخوارزمية بعد ذلك ام = 11 و i = 0.
 1          2 
  ام: 01234567890123456789012
 اس: أ ب ج أ ب د أ ب
 دبلي :
 أي:
مرة أخرى، تجد الخوارزمية تطابقًا للسلسلة "ABCDAB"، ولكن الحرف التالي في النص ('C') لا يتطابق مع الحرف الأخير في النمط W ('D'). بناءً على المنطق السابق، تقوم الخوارزمية بتحديث قيمة m إلى 15، وذلك للانتقال إلى بداية السلسلة الفرعية المكونة من الحرفين "AB" التي تسبق الموضع الحالي. كما تُعيّن قيمة i إلى 2، وتستأنف عملية المطابقة من هذا الموضع الجديد في النص.
 1        2 
 ام: 01234567890123456789012
 اس: أ ب ج أ ب ج د أ ب ج د أ ب ج د
 دبليو :
 اي:
في هذه المرة، انتهت عملية البحث بنجاح، وقد تم العثور على التطابق الأول عند الحرف S[15].

.

### وصف الكود الزائف لخوارزمية البحث
يتضمن المثال السابق جميع المكونات الأساسية للخوارزمية. ونفترض حاليًا وجود جدول "التطابق الجزئي" T، الموضح أدناه، والذي يحدد الموضع الذي يجب البحث فيه عن بداية تطابق جديد عند حدوث عدم تطابق. تم تصميم قيم هذا الجدول بحيث إذا وجد تطابق يبدأ عند S[m] وحدث فشل عند مقارنة S[m + i] بالحرف W[i]، فإن بداية التطابق المحتمل التالي ستكون عند الفهرس m + i - T[i] في السلسلة S (بمعنى أن T[i] يمثل مقدار "الرجوع" الذي يجب القيام به بعد عدم التطابق). يترتب على هذا التصميم نتيجتان مهمتان: أولًا، قيمة T[0] تساوي -1، مما يدل على أنه إذا كان الحرف W[0] غير مطابق، فلا يمكننا التراجع، ويتوجب علينا ببساطة الانتقال إلى فحص الحرف التالي في S؛ ثانيًا، على الرغم من أن بداية التطابق المحتمل التالي ستكون عند الفهرس m + i - T[i]، كما رأينا في المثال السابق، فإننا لسنا بحاجة فعليًا إلى إعادة فحص أي من T[i] الأحرف التالية، بل سنستأنف البحث مباشرة من الحرف W[T[i]]. فيما يلي نموذج لتنفيذ خوارزمية البحث KMP باستخدام لغة الترميز الزائف.
 **خوارزمية** *kmp_search* :
 **مدخل** :
  مجموعة من الأحرف، اس (النص المراد البحث عنه)
  مجموعة من الأحرف، ام (الكلمة المطلوبة)
 **الإخراج** :
   مجموعة من الأعداد الصحيحة، بي (المواضع في اس التي يوجد فيها دبيلو)
  عدد صحيح، ان بي (عدد المواضع)
 
  **تعريف المتغيرات** :
  هي عدد صحيح، j ← 0 (موضع الحرف الحالي في اس)
 هي عدد صحيح، k ← 0 (موضع الحرف الحالي في دبيلو)
  وهي مجموعة من الأعداد الصحيحة، تي (الجدول، تم حسابه في مكان آخر)
  **دع** nP ← 0
   **بينما** j O(k)، حيث يمثل k طول كلمة البحث W.

.

* الحلقة الخارجية: يتم تهيئة `pos` إلى 1، وشرط الحلقة هو `pos < k` ، ويتم زيادة `pos` بمقدار 1 في كل تكرار للحلقة. وبالتالي فإن الحلقة سوف تأخذ k - 1 التكرارات.

* الحلقة الداخلية: يتم تهيئة `cnd` إلى `0` ويتم زيادتها بما لا يزيد عن 1 في كل تكرار للحلقة الخارجية. يكون `T[cnd]` دائمًا أقل من `cnd` ، لذا يتم تقليل `cnd` بمقدار 1 على الأقل في كل تكرار للحلقة الداخلية؛ شرط الحلقة الداخلية هو `cnd ≥ 0` . يعني هذا أن الحلقة الداخلية يمكنها التنفيذ بحد أقصى عدد مرات إجمالي مماثل لما نفذته الحلقة الخارجية - كل انخفاض في `cnd` بمقدار 1 في الحلقة الداخلية يحتاج إلى زيادة مقابلة بمقدار 1 في الحلقة الخارجية. نظرًا لأن الحلقة الخارجية تأخذ k - 1 التكرارات، لا يمكن للحلقة الداخلية أن تستغرق أكثر من k - 1 التكرارات الإجمالية.

حيث ان مجتمعة، تستغرق الحلقات الخارجية والداخلية ما لا يزيد عن 2k-2 التكرارات وهذا يتوافق مع O(k) تعقيد الوقت باستخدام تدوين تمثيلO الكبري.

## كفاءة خوارزمية KMP
لأن الجزأين من الخوارزمية لهما، على التوالي، تعقيدات `O(k)` و `O(n)` ، تعقيد الخوارزمية الإجمالية هو `O(n + k)`.

يظل هذا المستوى من التعقيد الحسابي ثابتًا، بغض النظر عن عدد مرات تكرار الأنماط الفرعية داخل كل من النمط W والنص S.

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

تعتمد خوارزمية Booth على نسخة مُعدلة من دالة المعالجة المسبقة لخوارزمية كنوث-موريس-برات (KMP) للعثور على الحد الأدنى من دوران السلسلة المعجمي . ويتم حساب دالة الفشل بشكل تكراري أثناء عملية تدوير السلسلة.

.

## مراجع

* 
* 
* 

## روابط خارجية

* رسوم متحركة لبرنامج البحث عن السلسلة
* شرح الخوارزمية ونموذج كود C++ بقلم ديفيد إيبشتاين
* وصف خوارزمية كنوث-موريس-برات وشيفرة C بقلم كريستيان شاراس وتييري ليكراك
* شرح الخوارزمية من الصفر بواسطة HW Lang
* تحليل خطوات إدارة KMP بقلم تشو تشنغ هسيه.
* فيديو محاضرة NPTELHRD على يوتيوب
* فيديو محاضرة LogicFirst على يوتيوب
* إثبات الصحة
* التحويل بين أشكال مختلفة من الخوارزمية 
* خوارزمية Knuth-Morris-Pratt المكتوبة بلغة C#
* شرح تعقيد وقت البحث في خوارزمية KMP باللغة الإنجليزية البسيطة

تصنيف:علم الحاسوب في 1970
تصنيف:مقالات تحوي أمثلة مكتوبة بشبه رماز
تصنيف:دونالد كانوث