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

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

ابتكر جيمس إتش. موريس هذه الخوارزمية ، واكتشفها دونالد كنوث بشكل مستقل بعد بضعة أسابيع، انطلاقًا من نظرية الأوتوماتا . ^[¹^]^[²^] نشر موريس وفون برات تقريرًا فنيًا عام 1970. ^[³^] كما نشر الثلاثة الخوارزمية معًا عام 1977. ^[¹^] وفي عام 1969، اكتشف ماتياسيفيتش ^[⁴^]^[⁵^] بشكل مستقل خوارزمية مشابهة، مُبرمجة بواسطة آلة تورينج ثنائية الأبعاد، أثناء دراسته لمسألة التعرف على أنماط السلاسل النصية باستخدام الأبجدية الثنائية. وكانت هذه أول خوارزمية خطية لمطابقة السلاسل النصية. ^[⁶^]

خلفية

تريد خوارزمية مطابقة السلاسل إيجاد فهرس البداية mفي السلسلة sالتي تطابق كلمة البحث w.

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

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

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

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

يكمن الاختلاف في أن خوارزمية KMP تستفيد من معلومات المطابقة السابقة، وهو ما لا تفعله الخوارزمية المباشرة. في المثال أعلاه، عندما تفشل خوارزمية KMP في مطابقة تجريبية عند الحرف رقم 1000 ( i999) s[m + 999] ≠ w[999]، فإنها ستزيد قيمة المتغير mبمقدار 1، لكنها ستعلم أن أول 998 حرفًا في الموضع الجديد متطابقة بالفعل. طابقت خوارزمية KMP 999 حرفًا من الحرف A قبل اكتشاف عدم التطابق عند الحرف رقم 1000 (الموضع 999). يؤدي تحريك موضع المطابقة التجريبية mبمقدار واحد إلى حذف أول حرف A ، وبالتالي تعلم خوارزمية KMP أن هناك 998 حرفًا من الحرف A متطابقة w، ولا تعيد اختبارها؛ أي أن خوارزمية KMP تُعيّن قيمة المتغير iإلى 998. تحتفظ خوارزمية KMP بمعلوماتها في الجدول المُحسَب مسبقًا ومتغيرين للحالة. عندما تكتشف خوارزمية KMP عدم تطابق، يُحدد الجدول مقدار الزيادة التي ستُجريها خوارزمية KMP (المتغير m) وموضع استئناف الاختبار (المتغير i).

خوارزمية KMP

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

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

m، مما يدل على الموضع الذي تبدأ فيه Sالمطابقة المحتملة لـW
i، مما يشير إلى فهرس الحرف الذي يتم النظر فيه حاليًا في W.

في كل خطوة، تقارن الخوارزمية S[m+i]القيمتين W[i]وتزيدها iإذا كانتا متساويتين. ويتم توضيح ذلك في بداية التشغيل، كما يلي:

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABC D ABD i: 012 3 456

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

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456

تفشل هذه المطابقة عند الحرف الأول، لذا تقوم الخوارزمية بتعيين m = 4وi = 0

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDAB D i: 012345 6

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

 1 2 م: 01234567890123456789012 S: ABC ABCD AB ABCDABCDABDE W: AB C DABD i: 01 2 3456

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

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: A BCDABD i: 0 123456

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

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCDAB C DABDE W: ABCDAB D i: 012345 6

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

 1 2 م: 01234567890123456789012 S: ABC ABCDAB ABCD ABCDABD E W: ABCDABD i: 0123456

هذه المرة اكتملت المباراة، والحرف الأول في المباراة هو S[15].

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

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

خوارزمية kmp_search : المدخلات : مصفوفة من الأحرف، S (النص المراد البحث عنه) مجموعة من الأحرف، W (الكلمة المطلوبة) الناتج : مصفوفة من الأعداد الصحيحة، P (المواقع في S التي يوجد فيها W) عدد صحيح، nP (عدد المواضع) تعريف المتغيرات : عدد صحيح، j ← 0 (موضع الحرف الحالي في S) عدد صحيح، k ← 0 (موضع الحرف الحالي في W) مصفوفة من الأعداد الصحيحة، T (الجدول، محسوب في مكان آخر) ليكن nP ← 0 طالما أن j < طول(S) نفّذ ما يلي: إذا كان W[k] = S[j] ، فاجعل j ← j + 1، واجعل k ← k + 1. إذا كان k = طول(W)، فافعل ما يلي: (تم العثور على التكرار، إذا كانت هناك حاجة إلى أول تكرار فقط، فيمكن إرجاع 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قيمة دون تغيير، حيث mتُضاف i - T[i]إليها قيمة ، ثم 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تساوي nm + i ، فإن ≥ n بالتأكيد ، وبما أنها تزيد بمقدار وحدة واحدة على الأكثر، فلا بد أننا كنا قد حصلنا على m + iتساوي n في وقت ما في الماضي، وبالتالي سنكون قد انتهينا في كلتا الحالتين.

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

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

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

يهدف الجدول إلى منع الخوارزمية من مطابقة أي حرف 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]المقابل ، ، كان غير متطابق، وبالتالي . لذا، لا جدوى من إعادة بدء البحث من ؛ يجب أن نبدأ من الموضع التالي. هذا يعني أنه يمكننا تحريك النمط بمقدار طول التطابق زائد حرف واحد، أي .SS[m+4]S[m+4] ≠ 'A'S[m+4]WT[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

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

`i`	٠٠	01	02	03	04	05	06	07	08	09	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
`W[i]`	P	أ	R	تي	أنا	ج	أنا	P	أ	تي	هـ		أنا	شمال		P	أ	R	أ	ج	ح	يو	تي	هـ
`T[i]`	-1	0	0	0	0	0	0	-1	0	2	0	0	0	0	0	-1	0	0	3	0	0	0	0	0	0

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

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

خوارزمية kmp_table : المدخلات : مجموعة من الأحرف، W (الكلمة المراد تحليلها) الناتج : مصفوفة من الأعداد الصحيحة، T (الجدول المراد ملؤه) تعريف المتغيرات : عدد صحيح، pos ← 1 (الموقع الحالي الذي نحسبه في T) عدد صحيح، cnd ← 0 (الفهرس الذي يبدأ من الصفر في W للحرف التالي من السلسلة الفرعية المرشحة الحالية) ليكن T[0] ← -1 طالما أن pos < طول(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. let 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)$ التعقيد الزمني باستخدام ترميز Big O.

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

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

هذه التعقيدات مستقلة عن عدد الأنماط المتكررة الموجودة في Wأو S.

من المعروف أن التأخير، أي عدد مرات مقارنة رمز النص برموز النمط، أقل من $\lfloor \log _{\Phi }(k+1)\rfloor$ ، حيث Φ هي النسبة الذهبية $(1+{\sqrt {5}})/2$ في عام 1993، تم تقديم خوارزمية ذات تأخير محدود بـ $\min(1+\lfloor \log _{2}k\rfloor ,|\Sigma |)$ حيث Σ هو حجم الأبجدية (للنمط). ^{[ 7 ]}^{[ 8 ]}

المتغيرات

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

تستخدم خوارزمية بوث نسخة معدلة من دالة المعالجة المسبقة KMP لإيجاد دوران السلسلة الأدنى معجميًا . ويتم حساب دالة الفشل تدريجيًا مع دوران السلسلة.

ملحوظات

↑ $m$ يمثل طول النمط، وهو السلسلة التي نبحث عنها في النص والتي يبلغ طولها $n$

مراجع

1 2 كنوت، دونالد؛ موريس، جيمس هـ.؛ برات، فوغان (1977). "مطابقة الأنماط السريعة في السلاسل النصية". مجلة SIAM للحوسبة . 6 (2): 323-350 . CiteSeerX 10.1.1.93.8147 . doi : 10.1137/0206024 .
↑ كنوت، دونالد إي. (1973). "مخاطر نظرية علوم الحاسوب". دراسات في المنطق وأسس الرياضيات . 74 : 189-195 . doi : 10.1016/S0049-237X(09)70357-X . ISBN 978-0-444-10491-5.
↑ موريس، جيه إتش الابن؛ برات، في. (1970). خوارزمية مطابقة الأنماط الخطية (تقرير فني). جامعة كاليفورنيا، بيركلي، مركز الحوسبة. TR-40.
^ ماتياسيفيتش، يوري (1971). ""التواصل في الوقت الحقيقي للتغذية"" (PDF) . سجلت ندوات تعليم لينينغراد في لينينغراد لمعهد الرياضيات. В.А.Стеклова (بالروسية). 20 : 104 – 114.تُرجمت إلى الإنجليزية بعنوان: ماتياسيفيتش، يوري (1973). "التعرف الفوري على علاقة التضمين" . مجلة الرياضيات السوفيتية . 1 : 64-70 . doi : 10.1007/BF01117471 . S2CID 121919479. مؤرشف من الأصل بتاريخ 30 أبريل 2021. تم الاطلاع عليه بتاريخ 4 يوليو 2017 .
↑ يذكر كنوت هذه الحقيقة في تصويبات كتابه " أوراق مختارة حول تصميم الخوارزميات" :
لقد علمت في عام 2012 أن يوري ماتياسيفيتش قد توقع خوارزميات مطابقة الأنماط ومعالجة الأنماط في الوقت الخطي لهذه الورقة، في الحالة الخاصة للأبجدية الثنائية، في عام 1969. وقد قدمها كبنى لآلة تورينج ذات ذاكرة عمل ثنائية الأبعاد.
↑ أمير، أميهود؛ لاندو، جاد م.؛ ليوينشتاين، موشيه؛ سوكول، دينا (2007). "النص الديناميكي ومطابقة الأنماط الثابتة". معاملات ACM للخوارزميات . 3 (2): 19. doi : 10.1145/1240233.1240242 . S2CID 8409826 .
↑ سيمون، إيمري (1994). "خوارزميات مطابقة السلاسل والآلات". النتائج والاتجاهات في علوم الحاسوب النظرية: ندوة تكريمًا لآرتو سالوما . سبرينغر. ص 386-395 .
↑ هانكارت، كريستوف (1993). "حول خوارزمية سيمون للبحث عن السلاسل النصية" . رسائل معالجة المعلومات . 47 (2): 65-99 . doi : 10.1016/0020-0190(93)90231-W .

كورمن، توماس ؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد إل .؛ شتاين، كليفورد (2001). "القسم 32.4: خوارزمية كنوت-موريس-برات". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات 923-931 . ISBN 0-262-03293-7. Zbl 1047.68161 .
كروشيمور، ماكسيم؛ ريتر، فويتش (2003). جواهر علم السلاسل. خوارزميات النصوص . ريفر إيدج، نيوجيرسي: وورلد ساينتيفيك. ص 20-25 . ISBN 981-02-4897-0. Zbl 1078.68151 .
شبانكوفسكي، فويتش (2001). تحليل الحالة المتوسطة للخوارزميات على المتتاليات . سلسلة وايلي-إنترساينس في الرياضيات المتقطعة والتحسين. مع مقدمة بقلم فيليب فلاجو. تشيتشستر: وايلي. الصفحات 15-17 ، 136-141 . ISBN 0-471-24063-X. Zbl 0968.68205 .

روابط خارجية

رسوم متحركة لتطبيق البحث عن السلاسل
شرح للخوارزمية ونموذج كود C++ من إعداد ديفيد إبستين
وصف خوارزمية كنوت-موريس-برات وشفرة C من إعداد كريستيان شاراس وتيري ليكروك
شرح الخوارزمية من البداية بواسطة إتش دبليو لانغ
شرح خطوات إدارة برنامج KMP بقلم تشو-تشنغ هسيه.
فيديو محاضرة NPTELHRD على يوتيوب
فيديو محاضرة LogicFirst على يوتيوب
إثبات صحة النتائج
التحويل بين أشكال مختلفة من الخوارزميات. مؤرشف في 7 يوليو 2023 على موقع Wayback Machine.
خوارزمية كنوت-موريس-برات مكتوبة بلغة سي شارب
شرح مبسط لتعقيد وقت البحث في خوارزمية KMP

[1] $m$ يمثل طول النمط، وهو السلسلة التي نبحث عنها في النص والتي يبلغ طولها $n$

[knuth1977-2] 1 2 كنوت، دونالد؛ موريس، جيمس هـ.؛ برات، فوغان (1977). "مطابقة الأنماط السريعة في السلاسل النصية". مجلة SIAM للحوسبة . 6 (2): 323-350 . CiteSeerX 10.1.1.93.8147 . doi : 10.1137/0206024 .

[3] كنوت، دونالد إي. (1973). "مخاطر نظرية علوم الحاسوب". دراسات في المنطق وأسس الرياضيات . 74 : 189-195 . doi : 10.1016/S0049-237X(09)70357-X . ISBN 978-0-444-10491-5.

[4] موريس، جيه إتش الابن؛ برات، في. (1970). خوارزمية مطابقة الأنماط الخطية (تقرير فني). جامعة كاليفورنيا، بيركلي، مركز الحوسبة. TR-40.

[5] ماتياسيفيتش، يوري (1971). ""التواصل في الوقت الحقيقي للتغذية"" (PDF) . سجلت ندوات تعليم لينينغراد في لينينغراد لمعهد الرياضيات. В.А.Стеклова (بالروسية). 20 : 104 – 114.تُرجمت إلى الإنجليزية بعنوان: ماتياسيفيتش، يوري (1973). "التعرف الفوري على علاقة التضمين" . مجلة الرياضيات السوفيتية . 1 : 64-70 . doi : 10.1007/BF01117471 . S2CID 121919479. مؤرشف من الأصل بتاريخ 30 أبريل 2021. تم الاطلاع عليه بتاريخ 4 يوليو 2017 .

[6] يذكر كنوت هذه الحقيقة في تصويبات كتابه " أوراق مختارة حول تصميم الخوارزميات" :
لقد علمت في عام 2012 أن يوري ماتياسيفيتش قد توقع خوارزميات مطابقة الأنماط ومعالجة الأنماط في الوقت الخطي لهذه الورقة، في الحالة الخاصة للأبجدية الثنائية، في عام 1969. وقد قدمها كبنى لآلة تورينج ذات ذاكرة عمل ثنائية الأبعاد.

[7] أمير، أميهود؛ لاندو، جاد م.؛ ليوينشتاين، موشيه؛ سوكول، دينا (2007). "النص الديناميكي ومطابقة الأنماط الثابتة". معاملات ACM للخوارزميات . 3 (2): 19. doi : 10.1145/1240233.1240242 . S2CID 8409826 .

[8] سيمون، إيمري (1994). "خوارزميات مطابقة السلاسل والآلات". النتائج والاتجاهات في علوم الحاسوب النظرية: ندوة تكريمًا لآرتو سالوما . سبرينغر. ص 386-395 .

[9] هانكارت، كريستوف (1993). "حول خوارزمية سيمون للبحث عن السلاسل النصية" . رسائل معالجة المعلومات . 47 (2): 65-99 . doi : 10.1016/0020-0190(93)90231-W .

[

[

[

[

[

[

[ 7 ]

[ 8 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗