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

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

بيانات عامّة

الصنف	البحث عن السلسلة
بنية البيانات	سلسلة
المكتشف	دونالد كينوث — جيمس إتش موريس — هيو برات
تاريخ الاكتشاف	1970
نسبة التسمية	دونالد كينوث

الأداء

أسوء حالة	$\Theta (m)$ المعالجة المسبقة + $\Theta (n)$ المطابقة
أسوأ حالة تعقيد مكاني	$\Theta (m)$

في علوم الحاسوب خوارزمية كنوث-موريس-برات (أو خوارزمية 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
اس:ABCABCDAB ABCDABCDABDE
دبيلو:ABCDABD
اي  :0123456

تبدأ الخوارزمية بمقارنة الأحرف المتتالية في كلمة البحث W مع الأحرف المقابلة في السلسلة النصية S، وتنتقل إلى الحرف التالي بزيادة قيمة المؤشر i إذا تم العثور على تطابق. ومع ذلك، عند الخطوة الرابعة، يحدث عدم تطابق حيث أن S[3] (فراغ) لا يساوي W[3] ('D'). فبدلًا من إعادة بدء البحث من S[1]، تلاحظ الخوارزمية أنه لا يوجد حرف 'A' بين الموضعين 1 و2 في S. وبما أننا قد تحققنا بالفعل من تطابق هذه الأحرف مع الأحرف المقابلة في W، فإن أي محاولة لبدء تطابق جديد في هذه المنطقة ستكون غير مجدية. لذلك، تقوم الخوارزمية بتحديث قيمة m إلى 3 وإعادة تعيين قيمة i إلى 0، للانتقال إلى بداية محاولة تطابق جديدة من الموضع الثالث في S.

1 2 
م: 01234567890123456789012
س: أ ب جABCDAB ABCDABCDABDE
دبيلو :ABCDABD
اي :0123456

نظرًا لعدم تطابق الحرف الأول في عملية البحث، فإن الخوارزمية تُنشئ قيمة m تساوي 4 وقيمة i تساوي 0.

1          2 
 م: 01234567890123456789012
س: أ ب جABCDABABCDABCDABDE
دبيلو:ABCDABD
اي :0123456

هنا، تزداد قيمة i من خلال تطابق شبه كامل "ABCDAB" حتى تصبح i = 6 مما يؤدي إلى عدم تطابق عند W[6] و S[10] . ومع ذلك، قبل نهاية المباراة الجزئية الحالية مباشرة، كان هناك السلسلة الفرعية "AB" التي يمكن أن تكون بداية لمباراة جديدة، لذا يجب على الخوارزمية أخذ ذلك في الاعتبار.وبما أن هذه الأحرف تتطابق مع الحرفين السابقين للموضع الحالي في W، فليس هناك حاجة لإعادة التحقق منها. لذلك، تقوم الخوارزمية بتحديث قيمة m إلى 8 (وهو بداية ظهور البادئة الأولية المتطابقة) وتعيين قيمة i إلى 2 (مما يشير إلى أن أول حرفين قد تطابقا بالفعل)، ثم تستأنف عملية المطابقة من هذا الموضع. وبالتالي، فإن الخوارزمية لا تتجاوز فقط الأحرف المتطابقة سابقًا في S ("AB")، بل تتجاوز أيضًا البادئة المتطابقة في W ("AB").

• 1 2
• م: 01234567890123456789012
• س:ABC ABCDABABCDABCDABDE
• دبليو : ABCDABD
• اي : 0123456

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

1 2

م: 01234567890123456789012

اس : ABC ABCDABABCDABCDABDE

دبيلو : ABCDABD

اي : 0123456

 

A BCDABD i:  0 123456

تفشل المطابقة عند m=10 على الفور، لذا تحاول الخوارزمية بعد ذلك ام = 11 و i = 0.

1          2 
 ام: 01234567890123456789012
اس: أ ب ج أ ب د أ بABCDABCDABDE
دبلي :ABCDABD
أي:0123456

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

1        2 
ام: 01234567890123456789012
اس: أ ب ج أ ب ج د أ ب ج د أ ب ج دABCDABDE
دبليو :ABCDABD
اي:0123456

في هذه المرة، انتهت عملية البحث بنجاح، وقد تم العثور على التطابق الأول عند الحرف 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 < length( S )
  إذا كان W[k] = S[j] فإن
  دع j ← j + 1
   دع k ← k + 1
 إذا كان كي = الطول (دبيلو) إذن
(تم العثور على الحدوث، إذا كانت هناك حاجة إلى الحدوث الأول فقط، فيمكن إرجاع m ← j - k هنا)
 دع P[nP] ← j - k، nP ← nP + 1
دع k ← T[k] (T[length(W)] لا يمكن أن يكون -1)
آخر
 دع k ← T[k]
 إذا كان k < 0 فإن
 دع j ← j + 1
 دع k ← k + 1

كفاءة خوارزمية البحث

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

تشير هذه الحقيقة إلى أن الحلقة يمكن أن تنفذ على الأكثر 2n مرة، حيث أنها في كل تكرار تنفذ أحد الفرعين في الحلقة. الفرع الأول يزيد i دائمًا ولا يغير m، بحيث يزداد مؤشر m + i للحرف الذي يتم فحصه حاليًا لـ S. الفرع الثاني يضيف i - T[i] إلى m، وكما رأينا، يكون هذا دائمًا رقمًا موجبًا. وبالتالي يزداد موقع m لبداية التطابق المحتمل الحالي. في الوقت نفسه، يترك الفرع الثاني m + i دون تغيير، حيث يضاف i - T[i] إلى m، وبعد ذلك مباشرة يتم تعيين T[i] كقيمة جديدة لـ i، وبالتالي new_m + new_i = old_m + old_i - T[old_i] + T[old_i] = old_m + old_i. الآن، تنتهي الحلقة إذا m + i = n؛ لذلك، يمكن الوصول إلى كل فرع من فروع الحلقة على الأكثر n مرة، لأنها تزيد إما m + i أو m، وm ≤ m + i على التوالي: إذا كان m = n، فمن المؤكد أن m + i ≥ n، بحيث بما أنها تزيد بزيادات وحدوية على الأكثر، فلا بد أن يكون لدينا m + i = n في مرحلة ما في الماضي، وبالتالي سنكون قد انتهينا بأي طريقة.

وبالتالي يتم تنفيذ الحلقة على الأكثر 2n مرة، مما يدل على أن التعقيد الزمني لخوارزمية البحث هو O(n).

إليك منظور آخر لتحليل وقت التشغيل: لنفترض أننا بدأنا بمقارنة W وS عند الفهرسين i وp على التوالي. إذا كانت W تظهر كسلسلة فرعية من S تبدأ عند الموضع p، فهذا يعني أن W[0..m] = S[p..p+m]. عند حدوث تطابق (أي W[i] = S[p+i])، نقوم بزيادة قيمة i بمقدار 1 للمقارنة بين الحرفين التاليين. أما عند حدوث عدم تطابق (أي W[i] ≠ S[p+i])، فإن مؤشر النص p يظل ثابتًا، بينما يتم إرجاع مؤشر كلمة البحث i إلى الخلف بمقدار محدد (i = T[i]، حيث T هو جدول القفز)، ثم نحاول مطابقة W[T[i]] مع S[p+i]. والجدير بالذكر أن الحد الأقصى لعدد مرات إرجاع i محدود بقيمته الحالية، بمعنى أنه عند أي فشل في التطابق، لا يمكننا التراجع إلا بقدر ما تقدمنا به حتى نقطة الفشل. بناءً على هذا التحليل، يمكن استنتاج أن وقت التشغيل هو 2n.

جدول "المطابقة الجزئية" (المعروف أيضًا باسم "دالة الفشل")

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

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

مثال عملي لخوارزمية بناء الجدول

سنبدأ بتحليل المثال W = "ABCDABD". سنلاحظ أنه يتبع نفس مبادئ البحث الأساسية، وهو فعال لأسباب مماثلة. نقوم بتعيين قيمة T[0] لتكون -1. ولإيجاد قيمة T[1]، يجب أن نحدد لاحقة مناسبة للسلسلة "A" تكون أيضًا بادئة للنمط W. ولكن نظرًا لعدم وجود لاحقات مناسبة لـ "A"، فإننا نعين T[1] = 0. وبالمثل، لإيجاد قيمة T[2]، نرى أن السلسلة الفرعية W[0] - W[1] ("AB") لها لاحقة مناسبة هي "B". ومع ذلك، فإن "B" ليست بادئة للنمط W. لذلك، نقوم بتعيين T[2] = 0.

عند معالجة T[3]، نبدأ بفحص اللاحقة الصحيحة التي يبلغ طولها 1، وكما في الحالة السابقة، لا تحقق التطابق المطلوب. هل يلزمنا أيضًا فحص اللواحق الأطول؟ الإجابة هي لا. نلاحظ هنا اختصارًا يسمح بتجنب فحص جميع اللواحق: لنفترض أننا وجدنا لاحقة صحيحة تمثل أيضًا بادئة صحيحة (البادئة الصحيحة للسلسلة لا تساوي السلسلة نفسها) وتنتهي عند W[2] بطول 2 (وهو أقصى طول ممكن)؛ في هذه الحالة، سيكون الحرف الأول في هذه اللاحقة أيضًا بادئة صحيحة لـ W، وبالتالي ستكون اللاحقة نفسها بادئة صحيحة تنتهي عند W[1]، وقد حددنا بالفعل أن هذا لم يحدث لأن T[2] = 0 وليس T[2] = 1. بناءً على ذلك، تكون قاعدة الاختصار في كل خطوة هي أنه يجب فحص اللواحق ذات الحجم m+1 فقط إذا تم العثور على لاحقة صحيحة بحجم m في الخطوة السابقة (أي T[x] = m)، ولا داعي لفحص اللواحق ذات الحجم m+2 أو m+3 وما إلى ذلك.

بناءً على ذلك، لسنا بحاجة حتى إلى أخذ السلاسل الفرعية التي يبلغ طولها 2 في الاعتبار. وكما في الحالة السابقة، فإن السلسلة الفرعية الوحيدة التي يبلغ طولها 1 تفشل في أن تكون بادئة مناسبة، ولهذا السبب تكون قيمة T[3] مساوية لـ 0.

بالانتقال إلى اللاحقة W[4]، وهي الحرف 'A'، يوضح المنطق نفسه أن أطول سلسلة فرعية يجب أخذها في الاعتبار يبلغ طولها 1. وكما في الحالة السابقة، يفشل التطابق لأن 'D' ليست بادئة لـ W. ولكن بدلًا من تعيين T[4] = 0، يمكننا تحسين ذلك بملاحظة أن W[4] يساوي W[0]، وأن البحث عن قيمة T[4] يعني أن الحرف المقابل في S، وهو S[m+4]، كان غير متطابق، وبالتالي S[m+4] لا يساوي 'A'. لذا، لا فائدة من إعادة البحث عند S[m+4]؛ يجب أن نبدأ البحث من موضع واحد للأمام. هذا يعني أنه يمكننا تحريك النمط W بمقدار طول التطابق بالإضافة إلى حرف واحد، وبالتالي تكون قيمة T[4] هي -1.

بالنظر الآن إلى الحرف التالي، W[5]، وهو 'B': مع أن أطول سلسلة فرعية تبدو عند الفحص هي 'A'، إلا أننا ما زلنا نضبط T[5] = 0. السبب مشابه لسبب أن T[4] = -1. W[5] نفسها تُوسّع تطابق البادئة الذي بدأ بـ W[4]، ويمكننا افتراض أن الحرف المقابل في S، S[m+5] ≠ 'B'. لذا، فإن الرجوع قبل W[5] لا طائل منه، ولكن S[m+5] قد يكون 'A'، وبالتالي T[5] = 0.

في الختام، نلاحظ أن الحرف التالي في السلسلة المتصلة التي تبدأ من W[4] ('A') هو 'B'، وهو بالفعل الحرف W[5]. بالإضافة إلى ذلك، يوضح المنطق السابق نفسه أنه لا توجد حاجة للبحث قبل W[4] للعثور على بادئة مناسبة لـ W[6]، لذا فإن هذا هو الحل الأمثل، وعليه نحدد قيمة T[6] لتكون 2.

لذلك قمنا بتجميع الجدول التالي:

i	0	1	2	3	4	5	6	7
W[i]	أ	ب	ج	د	أ	ب	د
T[i]	-1	0	0	0	-1	0	2	0

مثال آخر:

i	0	1	2	3	4	5	6	7	8	9
W[i]	أ	ب	أ	ج	أ	ب	أ	ب	ج
T[i]	-1	0	-1	1	-1	0	-1	3	2	0

مثال آخر (تم تغييره قليلاً عن المثال السابق):

i	0	1	2	3	4	5	6	7	8	9
W[i]	أ	ب	أ	ج	أ	ب	أ	ب	أ
T[i]	-1	0	-1	1	-1	0	-1	3	-1	3

مثال آخر أكثر تعقيدا:

وصف الكود الزائف لخوارزمية بناء الجدول

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

.

خوارزمية kmp_table :
  مدخل :
 هي مجموعة من الأحرف، W (الكلمة المراد تحليلها)
  الإخراج :
عي مجموعة من الأعداد الصحيحة، T (الجدول المراد ملؤه)
  تعريف المتغيرات :
هي عباره عن عدد صحيح، pos ← 1 (الموضع الحالي الذي نحسبه في T)
هي عباره عن عدد صحيح، cnd ← 0 (المؤشر القائم على الصفر في W للحرف التالي من السلسلة الفرعية المرشحة الحالية)
  دع T[0] ← -1
  بينما pos < length(W) افعل
 إذا كان W[pos] = W[cnd] إذن
  دع T[pos] ← T[cnd]
  آخر
  دع T[pos] ← cnd
  بينما cnd ≥ 0 و W[pos] ≠ W[cnd]
     دع cnd ← T[cnd]
 دع pos ← pos + 1، cnd ← cnd + 1
  دع T[pos] ← cnd (مطلوب فقط عند البحث عن جميع الكلمات المتواجدة)

كفاءة خوارزمية بناء الجدول

يبلغ التعقيد الزمني لخوارزمية إنشاء الجدول $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) للعثور على الحد الأدنى من دوران السلسلة المعجمي . ويتم حساب دالة الفشل بشكل تكراري أثناء عملية تدوير السلسلة.

.

مراجع

• Cormen، Thomas؛ Leiserson، Charles E.؛ Rivest، Ronald L.؛ Stein، Clifford (2001). "Section 32.4: The Knuth-Morris-Pratt algorithm". Introduction to Algorithms (ط. Second). MIT Press and McGraw-Hill. ص. 923–931. ISBN:0-262-03293-7. Zbl:1047.68161.
• Crochemore، Maxime؛ Rytter، Wojciech (2003). Jewels of stringology. Text algorithms. River Edge, NJ: World Scientific. ص. 20–25. ISBN:981-02-4897-0. Zbl:1078.68151.
• Szpankowski، Wojciech (2001). Average case analysis of algorithms on sequences. Wiley-Interscience Series in Discrete Mathematics and Optimization. With a foreword by Philippe Flajolet. Chichester: Wiley. ص. 15–17, 136–141. ISBN:0-471-24063-X. Zbl:0968.68205.

روابط خارجية

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