خوارزمية KMP
لا يمكن الاستفادة من خوارزمية البحث البسيط في الحالات التي تحتوي فيها السلسلة النصية على العديد من الحروف المطابقة للنمط المعطى متبوعة بحرف غير مطابق. مثال:
txt[] = "AAAAAAAAAAAAAAAAAB"
pat[] = "AAAAB"
txt[] = "ABABABCABABABCABABABC"
pat[] = "ABABAC"
// (صحيح أنّها ليست الحالة الأسوأ ولكنها لا تزال حالة سيئة بالنسبة لخوارزمية البحث البسيط)
تستخدم خوارزمية Knuth–Morris–Pratt (وتعرف اختصارًا بخوارزمية KMP) خاصية التحلل degenerating في الأنماط (أي أن النمط يحتوي على أنماط فرعية تظهر فيه لأكثر من مرة) وتحسّن التعقيد الزمني للحالة الأسوأ إلى المقدار O(n).
بنيت هذه الخوارزمية على فكرة مفادها أنّه في كلّ مرة نكشف فيها عن عدم تطابق (بعد عدد من التطابقات) فإنّنا سنكون على علم ببعض الحروف الموجودة في النص والتي ستكون مطابقة في الخطوة القادمة، وسنستغل هذه المعلومة لتجنب مطابَقة الحروف التي نعلم بأنّها مطابِقة في جميع الأحوال. يوضّح المثال التالي طريقة عمل الخوارزمية:
txt = "AAAAABAAABA"
pat = "AAAA"
نقارن نافذة النص الأولى مع النمط المعطى
txt = "AAAAABAAABA"
pat = "AAAA" [الموقع الابتدائي]
نلاحظ وجود التطابق في هذا الموقع. هذا مشابه لعمل خوارزمية البحث البسيط Naive.
نقارن في الخطوة التالية النافذة التالية للنص مع النمط المعطى:
txt = "AAAAABAAABA"
pat = "AAAA" [تحريك النمط بمقدار موقع واحد]
تتفوق خوارزمية KMP في هذه النقطة على خوارزمية البحث البسيط، ففي النافذة الثانية، سنقارن الحرف الرابع في النمط مع الحرف الرابع في نافذة النص الحالية لنقرر ما إذا كانت النافذة الحالية مطابقة للنص أو لا. وما دمنا نعرف أنّ الأحرف الثلاثة الأولى ستكون مطابقة في جميع الأحوال فلا حاجة حينئذٍ لمطابقتها مع النص الأصلي.
المعالجة القبلية
يجب تحديد عدد الحروف التي يجب تجاوزها عند إجراء عملية المطابقة، وللقيام بذلك يمكن معالجة النمط مسبّقًا وتحضير مصفوفة أعداد صحيحة (لتكن lps[]) والتي ستخبرنا بعدد الحروف اللازم تجاوزها، وتكون المصفوفة lps[] مماثلة في حجمها للنمط المراد مطابقته.
الاسم lps هو اختصار للعبارة Longest Proper Prefix ويعني أطول سابقة ملائمة والتي تكون لاحقة Suffix في نفس الوقت.
والسابقة الملائمة هي السابقة التي لا يسمح فيها بظهور السلسلة النصية كاملة، فعلى سبيل المثال تمتلك السلسلة النصية "ABC" السوابق: "" و "A" و "AB" و "ABC"، ولكن السوابق الملائمة هي "" و "A" و "AB"، أما اللواحق الخاصة بهذه السلسلة النصية فهي: "" و "C" و "BC" و "ABC".
بعد الحصول على المصفوفة lps[] نجري عملية البحث بالاستعانة بهذه المصفوفة في الأنماط الفرعية، أي أننا سنركّز على السلاسل النصية الفرعية للأنماط التي تكون إمّا سوابق أو لواحق.
يخزّن العنصر lps[i] لكل نمط فرعي pat[0..i] عند i = 0 إلى i = m-1، طول أقصى سابقة ملائمة مطابقة والتي تكون لاحقة في نفس الوقت في النمط الفرعي pat[0..i].
أمثلة
تعرض الأمثلة التالية عددًا من الأنماط ومصفوفة lps[] التي تنشأ منها:
For the pattern “AAAA”,
lps[] is [0, 1, 2, 3]
For the pattern “ABCDE”,
lps[] is [0, 0, 0, 0, 0]
For the pattern “AABAACAABAA”,
lps[] is [0, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5]
For the pattern “AAACAAAAAC”,
lps[] is [0, 1, 2, 0, 1, 2, 3, 3, 3, 4]
For the pattern “AAABAAA”,
lps[] is [0, 1, 2, 0, 1, 2, 3]
خوارزمية البحث
تقارن خوارزمية البحث البسيط النمط المعطى مع النص حرفًا حرفًا، وتقارن جميع الحروف في كل مرة، أمّا خوارزمية KMP فتستخدم القيم المخزّنة في المصفوفة lps[] لتقرر عدد الحروف التي يجب مطابقتها في الخطوة القادمة. وتقوم هذه الخوارزمية على فكرة مفادها أن لا حاجة لمقارنة الحروف التي نجزم بكونها مطابقة في جميع الأحوال.
يمكن تقسيم عمل خوارزمية KMP إلى الخطوات التالية:
- نبدأ بمقارنة
pat[i]معj = 0مع الحروف الموجودة في نافذة النص الحالية. - نستمر في مقارنة الحروف
txt[i]وpat[j]ونستمر كذلك في زيادة قيمتيiوj. - عند الوصول إلى حالة عدم تطابق:
- نحن نعلم أنّ الحروف
pat[0..j-1]مطابقة للحروفtxt[i-j...i-1](لاحظ أنّjتبدأ من الصفر وتزداد قيمتها عند حدوث تطابق فقط). - ونعلم كذلك (من التعريف أعلاه) أنّ العدد المخزّن في الموقع
lps[j-1]هو عدد الحروف الموجودة فيpat[0...j-1]والتي تكون سابقة ولاحقة ملائمة في نفس الوقت. - يمكن أن نستنتج من النقطتين السابقتين أنّنا لسنا بحاجة إلى مطابقة العدد
lps[j-1]من الحروف مع النصtxt[i-j...i-1]، وذلك لأنّنا نعلم بأنّ هذه الحروف مطابقة في جميع الأحوال.
- نحن نعلم أنّ الحروف
لتوضيح طريقة عمل الخوارزمية إليك المثال التالي:
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
lps[] = {0, 1, 2, 3}
i = 0, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 1, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 2, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 3, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 4, j = 4
لاحظ أنّ j == M؛ لذا سنطبع النموذج الذي عثرنا عليه ونعيد تعيين قيمة j.
j = lps[j-1] = lps[3] = 3
لن نطابق الحروف الثلاثة الأول في هذه النافذة مع النص، فالقيمة المخزنة في lps[j-1] (في الخطوة السابقة) تعطينا موقع الحرف التالي الذي سنبدأ منه عملية المقارنة.
i = 4, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 5, j = 4
لاحظ أنّ j == M؛ لذا سنطبع النموذج الذي عثرنا عليه ونعيد تعيين قيمة j.
j = lps[j-1] = lps[3] = 3
مرة أخرى، لا حاجة إلى مقارنة الأحرف الثلاثة الأولى في هذه النافذة؛ إذ تعطينا القيمة المخزّنة في lps[j-1] الموقع الذي سنبدأ فيه عملية المقارنة.
i = 5, j = 3
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لا وجود للتطابق بين txt[i] و pat[j] و j > 0 لذا سنغيّر قيمة j فقط.
j = lps[j-1] = lps[2] = 2
i = 5, j = 2
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لا وجود للتطابق بين txt[i] و pat[j] و j > 0 لذا سنغيّر قيمة j فقط.
j = lps[j-1] = lps[1] = 1
i = 5, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لا وجود للتطابق بين txt[i] و pat[j] و j > 0 لذا سنغيّر قيمة j فقط.
j = lps[j-1] = lps[0] = 0
i = 5, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لا وجود للتطابق بين txt[i] و pat[j] و j == 0 لذا سنزيد قيمة i بمقدار واحد.
i = 6, j = 0
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
i = 7, j = 1
txt[] = "AAAAABAAABA"
pat[] = "AAAA"
لاحظ أنّ txt[i] و pat[j] متطابقان؛ لذا سنزيد قيمة i و j بمقدار واحد.
ونستمر بهذه الطريقة ...
تنفيذ الخوارزمية
تعرض الأمثلة التالية طريقة تنفيذ خوارزمية KMP في عدد من لغات البرمجة:
- C++:
#include <bits/stdc++.h>
void computeLPSArray(char* pat, int M, int* lps);
void KMPSearch(char* pat, char* txt)
{
int M = strlen(pat);
int N = strlen(txt);
// إنشاء المصفوفة المسؤولة عن تخزين قيم أطول لاحقة-سابقة ملائمة للنمط المعطى
int lps[M];
// إجراء المعالجة القبلية للنمط المعطى
computeLPSArray(pat, M, lps);
int i = 0; // موقع الحرف في النص
int j = 0; // موقع الحرف في النمط
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d ", i - j);
j = lps[j - 1];
}
// حالة عدم التطابق بعد حالات التطابق السابقة
// mismatch after j matches
else if (i < N && pat[j] != txt[i]) {
// lps[0..lps[j-1]] لا حاجة لمطابقة الحروف
// لأنّها ستكون مطابقة في جميع الأحوال
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
// تملأ هذه الدالة المصفوفة المسؤولة عن تخزين قيم أطول لاحقة-سابقة ملائمة للنمط المعطى
void computeLPSArray(char* pat, int M, int* lps)
{
// طول أطول سابقة-لاحقة
int len = 0;
// العنصر الأول في هذه المصفوفة يكون صفرًا دائمًا
lps[0] = 0;
// تحسب هذه الحلقة التكرارية القيم التي ستخزن في المصفوفة
// M-1 من 1 إلى
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps[len - 1];
// i لاحظ عدم زيادة قيمة المتغير
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}
// اختبار الدوال السابقة
int main()
{
char txt[] = "ABABDABACDABABCABAB";
char pat[] = "ABABCABAB";
KMPSearch(pat, txt);
return 0;
}
- بايثون:
def KMPSearch(pat, txt):
M = len(pat)
N = len(txt)
# إنشاء القائمة المسؤولة عن تخزين قيم أطول لاحقة-سابقة ملائمة للنمط المعطى
lps = [0]*M
j = 0 # موقع الحرف في النمط
# إجراء المعاجلة القبلية للنمط المعطى
computeLPSArray(pat, M, lps)
i = 0 # موقع الحرف في النص
while i < N:
if pat[j] == txt[i]:
i += 1
j += 1
if j == M:
print "Found pattern at index " + str(i-j)
j = lps[j-1]
# حالة عدم التطابق بعد عدد من التطابقات السابقة
elif i < N and pat[j] != txt[i]:
# lps[0..lps[j-1]] لا حاجة لمطابقة الحروف
# لأنّها ستكون مطابقة في جميع الأحوال
if j != 0:
j = lps[j-1]
else:
i += 1
def computeLPSArray(pat, M, lps):
len = 0 # طول أطول سابقة-لاحقة
lps[0] # العنصر الأول في هذه المصفوفة يكون صفرًا دائمًا
i = 1
# تحسب هذه الحلقة التكرارية القيم التي ستخزن في المصفوفة
# M-1 من 1 إلى
while i < M:
if pat[i]== pat[len]:
len += 1
lps[i] = len
i += 1
else:
if len != 0:
len = lps[len-1]
# i لاحظ عدم زيادة قيمة المتغير
else:
lps[i] = 0
i += 1
txt = "ABABDABACDABABCABAB"
pat = "ABABCABAB"
KMPSearch(pat, txt)
- جافا:
class KMP_String_Matching {
void KMPSearch(String pat, String txt)
{
int M = pat.length();
int N = txt.length();
// إنشاء المصفوفة المسؤولة عن تخزين قيم أطول لاحقة-سابقة ملائمة للنمط المعطى
int lps[] = new int[M];
int j = 0; // موقع الحرف في النمط
// إجراء المعالجة القبلية للنمط المعطى
computeLPSArray(pat, M, lps);
int i = 0; // موقع الحرف في النص
while (i < N) {
if (pat.charAt(j) == txt.charAt(i)) {
j++;
i++;
}
if (j == M) {
System.out.println("Found pattern "
+ "at index " + (i - j));
j = lps[j - 1];
}
// حالة عدم التطابق بعد حالات التطابق السابقة
else if (i < N && pat.charAt(j) != txt.charAt(i)) {
// lps[0..lps[j-1]] لا حاجة لمطابقة الحروف
// لأنّها ستكون مطابقة في جميع الأحوال
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}
void computeLPSArray(String pat, int M, int lps[])
{
// lطول أطول سابقة-لاحقة
int len = 0;
int i = 1;
lps[0] = 0; // العنصر الأول في هذه المصفوفة يكون صفرًا دائمًا
// تحسب هذه الحلقة التكرارية القيم التي ستخزن في المصفوفة
// M-1 من 1 إلى
while (i < M) {
if (pat.charAt(i) == pat.charAt(len)) {
len++;
lps[i] = len;
i++;
}
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps[len - 1];
// i لاحظ عدم زيادة قيمة المتغير
}
else // if (len == 0)
{
lps[i] = len;
i++;
}
}
}
}
// اختبار الدوال السابقة
public static void main(String args[])
{
String txt = "ABABDABACDABABCABAB";
String pat = "ABABCABAB";
new KMP_String_Matching().KMPSearch(pat, txt);
}
}
مصادر
- صفحة KMP Algorithm for Pattern Searching في توثيق الخوارزميات في موقع GeeksforGeeks.