مرجع
آخر الزيارات

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

3٬465 كلمة•0 مشاهدة•🗒️ منذ 3 أيام
باختصار: في علوم الحاسوب خوارزمية كنوث-موريس-برات (أو خوارزمية KMP )، تُعد خوارزمية كنوث-موريس-برات (KMP) خوارزمية فعالة للبحث عن نمط W داخل نص S. تتناول المقالة 24 قسماً، منها «س:ABC ABCD»، «دع T[pos] ← cnd» و«ام: 01234567890123456789012».
المحتويات
  1. س:ABC ABCD
  2. دع T[pos] ← cnd
  3. ام: 01234567890123456789012
  4. مثال عملي لخوارزمية بناء الجدول
  5. ام: 01234567890123456789012
  6. رسوم متحركة لبرنامج البحث عن السلسلة
  7. وصف الكود الزائف لخوارزمية البحث
  8. خلفية
  9. خوارزمية Knuth-Morris-Pratt المكتوبة بلغة C#
  10. مثال على خوارزمية البحث
  11. كفاءة خوارزمية KMP
  12. وصف الكود الزائف لخوارزمية بناء الجدول
  13. A BCDABD i:  0 123456
  14. إذا كان كي = الطول (دبيلو) إذن
  15. المتغيرات
  16. كفاءة خوارزمية البحث
  17. ام: 01234567890123456789012
  18. شرح الخوارزمية من الصفر بواسطة HW Lang
  19. اس : ABC ABCDAB
  20. دع nP ← 0
  21. كفاءة خوارزمية بناء الجدول
  22. س: أ ب ج
  23. دع cnd ← T[cnd]
  24. س: أ ب ج

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

.

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

س:ABC ABCD

1 2

اي :

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

دبليو :

م: 01234567890123456789012

دع T[pos] ← cnd

بينما cnd ≥ 0 و W[pos] ≠ W[cnd]

ام: 01234567890123456789012

اس: أ ب ج أ ب د أ ب

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

دبلي :

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

علاوةً على ذلك، عند معالجة 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.

في هذا الإطار، سنبدأ بتحليل المثال 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.

ام: 01234567890123456789012

إضافةً إلى ذلك، اي:في هذه المرة، انتهت عملية البحث بنجاح، وقد تم العثور على التطابق الأول عند الحرف S[15].

دبليو :

.

اس: أ ب ج أ ب ج د أ ب ج د أ ب ج د

رسوم متحركة لبرنامج البحث عن السلسلة

في هذا الإطار، وصف خوارزمية كنوث-موريس-برات وشيفرة C بقلم كريستيان شاراس وتييري ليكراك

شرح الخوارزمية ونموذج كود C++ بقلم ديفيد إيبشتاين

وصف الكود الزائف لخوارزمية البحث

كذلك، يتضمن المثال السابق جميع المكونات الأساسية للخوارزمية. ونفترض في الوقت الحالي وجود جدول "التطابق الجزئي" 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 (موضع الحرف الحالي في دبيلو)
  • وهي مجموعة من الأعداد الصحيحة، تي (الجدول، تم حسابه في مكان آخر)

خلفية

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

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

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

خوارزمية KMP

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

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

خوارزمية Knuth-Morris-Pratt المكتوبة بلغة C#

من جانب آخر، شرح تعقيد وقت البحث في خوارزمية KMP باللغة الإنجليزية البسيطة

مثال على خوارزمية البحث

من جهة ثانية، في كل خطوة من خطوات الخوارزمية، تتم مقارنة الحرف S[m+i] بالحرف W[i]. وفي حال تطابقهما، يتم زيادة قيمة المؤشر i للانتقال إلى الحرف التالي في كل من السلسلة والنص. ويتضح هذا الإجراء في المراحل الأولية لتشغيل الخوارزمية كما يلي: 1 2

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

اي ، يشير إلى مؤشر الحرف المعتبر في الوقت الحالي في ام .

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

كفاءة خوارزمية KMP

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

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

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

  • .
  • خوارزمية kmp_table :
  • مدخل :
  • هي مجموعة من الأحرف، W (الكلمة المراد تحليلها)
  • الإخراج :
  • عي مجموعة من الأعداد الصحيحة، T (الجدول المراد ملؤه)
  • تعريف المتغيرات :
  • هي عباره عن عدد صحيح، pos ← 1 (الموضع الحالي الذي نحسبه في T)

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

وفي السياق ذاته، هي عباره عن عدد صحيح، cnd ← 0 (المؤشر القائم على الصفر في W للحرف التالي من السلسلة الفرعية المرشحة الحالية)

  • دع T[0] ← -1
  • بينما pos < length(W) افعل
  • إذا كان W[pos] = W[cnd] إذن
  • دع T[pos] ← T[cnd]
  • آخر

A BCDABD i:  0 123456

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

إذا كان كي = الطول (دبيلو) إذن

  • دع 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

وعلى صعيد آخر، (تم العثور على الحدوث، إذا كانت هناك حاجة إلى الحدوث الأول فقط، فيمكن إرجاع m ← j - k هنا)

المتغيرات

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

  • .
  • مراجع
  • روابط خارجية

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

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

ومن ناحية أخرى، تشير هذه الحقيقة إلى أن الحلقة يمكن أن تنفذ على الأكثر 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 في مرحلة ما في الماضي، وبالتالي سنكون قد انتهينا بأي طريقة.

ومن ناحية أخرى، بافتراض أن الجدول 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.

وفي السياق ذاته، إليك منظور آخر لتحليل وقت التشغيل: لنفترض أننا بدأنا بمقارنة 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.

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

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

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

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

ام: 01234567890123456789012

دبيلو:

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

اس:

م: 01234567890123456789012

شرح الخوارزمية من الصفر بواسطة HW Lang

  • تحليل خطوات إدارة KMP بقلم تشو تشنغ هسيه.
  • فيديو محاضرة NPTELHRD على يوتيوب
  • فيديو محاضرة LogicFirst على يوتيوب
  • إثبات الصحة
  • التحويل بين أشكال مختلفة من الخوارزمية

اس : ABC ABCDAB

اي :

دبيلو :

دع nP ← 0

  • بينما j < length( S )
  • إذا كان W[k] = S[j] فإن
  • دع j ← j + 1
  • دع k ← k + 1

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

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

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

وعلى صعيد آخر، يبلغ التعقيد الزمني لخوارزمية إنشاء الجدول ، حيث يمثل k طول كلمة البحث W.

.

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

س: أ ب ج

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

دبيلو :

م: 01234567890123456789012

دع cnd ← T[cnd]

دع pos ← pos + 1، cnd ← cnd + 1

وفي السياق ذاته، دع T[pos] ← cnd (مطلوب فقط عند البحث عن جميع الكلمات المتواجدة)

س: أ ب ج

م: 01234567890123456789012

دبيلو:

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

1 2

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.