ما هي خوارزمية KMP؟ البحث السريع عن النص باستخدام Knuth–Morris–Pratt

خوارزمية Knuth–Morris–Pratt أو KMP هي خوارزمية كلاسيكية للبحث عن Pattern داخل Text.

الفكرة الأساسية هي عدم إعادة المقارنات التي نملك معلومات عنها بالفعل. عندما يحدث mismatch بعد تطابق جزء من Pattern، تستخدم KMP معلومات هذا التطابق بدلاً من العودة دائماً إلى بداية Pattern.

ويتم تخزين هذه المعلومات في مصفوفة تسمى LPS.

ما هي LPS؟

LPS اختصار لـ:

Longest Proper Prefix which is also a Suffix

أي أطول Prefix صحيح يكون أيضاً Suffix للجزء الحالي من Pattern.

مثال:

Pattern: A B A B A C
LPS:     0 0 1 2 3 0

بالنسبة إلى ABAB، أطول Prefix وهو أيضاً Suffix هو AB، ولذلك تكون القيمة 2.

لماذا نحتاج LPS؟

عند حدوث mismatch بعد مطابقة j أحرف، بدلاً من إعادة:

j = 0

نستخدم:

j = lps[j - 1]

وبذلك نحافظ على الجزء من التطابق السابق الذي ما زال صالحاً.

بناء LPS

function buildLPS(pattern: string): number[] {
  const lps = new Array(pattern.length).fill(0);

  let length = 0;
  let i = 1;

  while (i < pattern.length) {
    if (pattern[i] === pattern[length]) {
      length++;
      lps[i] = length;
      i++;
    } else if (length !== 0) {
      length = lps[length - 1];
    } else {
      lps[i] = 0;
      i++;
    }
  }

  return lps;
}

مثلاً لـ:

ABABCABAB

تكون النتيجة:

[0, 0, 1, 2, 0, 1, 2, 3, 4]

تنفيذ KMP باستخدام TypeScript

function kmpSearch(text: string, pattern: string): number {
  if (pattern.length === 0) return 0;

  const lps = buildLPS(pattern);

  let i = 0;
  let j = 0;

  while (i < text.length) {
    if (text[i] === pattern[j]) {
      i++;
      j++;

      if (j === pattern.length) {
        return i - j;
      }
    } else if (j !== 0) {
      j = lps[j - 1];
    } else {
      i++;
    }
  }

  return -1;
}

في هذه الخوارزمية يمثل i موقعنا في Text، بينما يمثل j موقعنا في Pattern.

المهم أن i لا يعود إلى الخلف عند حدوث mismatch.

التعقيد

إذا كان طول Text هو n وطول Pattern هو m:

LPS:    O(m)
Search: O(n)
Total:  O(n + m)
Space:  O(m)

وهذا أفضل من Naive Search الذي قد يصل في أسوأ حالة إلى:

O(n × m)

مثال يوضح أهمية KMP

Text:
AAAAAAAAAAAAAAAAAB

Pattern:
AAAAAB

في البحث البسيط قد تتم مقارنة عدد كبير من أحرف A عدة مرات.

لكن KMP تستخدم معلومات LPS لتجنب الكثير من هذه المقارنات.

التطبيقات

يمكن استخدام مفاهيم KMP في:

• البحث داخل النصوص
• تحليل الملفات والسجلات
• معالجة DNA Sequence
• البحث عن Pattern داخل Streams
• بعض تطبيقات أمن المعلومات
• مسائل الخوارزميات والمقابلات التقنية

KMP في المقابلات

الأسئلة المرتبطة بها قد تشمل:

• Find substring
• Find all occurrences
• Build LPS
• Longest prefix that is also suffix
• Repeated substring pattern

الأهم هو فهم سبب استخدام LPS وليس حفظ الكود فقط.

خطأ شائع

إذا حدث mismatch وكان:

j > 0

لا يجب زيادة i مباشرة.

بل نستخدم:

j = lps[j - 1]

حتى تتم مقارنة حرف Text نفسه مع موقع جديد من Pattern.

الخلاصة

KMP هي خوارزمية فعالة للبحث عن Pattern داخل Text باستخدام معلومات داخلية عن Pattern نفسه.

بدلاً من إعادة المقارنة من البداية بعد كل mismatch، تستخدم مصفوفة LPS للحفاظ على المعلومات المفيدة من التطابق السابق.

Time Complexity: O(n + m)
Space Complexity: O(m)

الفكرة الأهم في KMP هي أن mismatch لا يعني أن كل ما تم تعلمه من التطابق السابق يجب التخلص منه.