ما هي خوارزمية Rabin–Karp؟ البحث في النصوص باستخدام Rolling Hash

Rabin–Karp هي خوارزمية كلاسيكية للبحث عن Pattern داخل Text باستخدام Hashing.

بدلاً من مقارنة جميع الأحرف في كل موضع، نحسب Hash للـ Pattern ثم نقارنه مع Hash لنوافذ Text التي لها الطول نفسه.

الفكرة الأساسية:

قارن Hash أولاً، وإذا كان متساوياً نفذ مقارنة فعلية للأحرف.

Rolling Hash

إذا كانت النافذة الحالية:

ABC

والتالية:

BCD

لا نحتاج إلى حساب Hash من البداية.

نحذف تأثير A ونضيف D للحصول على Hash النافذة التالية.

وهذا يسمى Rolling Hash.

Hash Collision

قد يكون لسلسلتين مختلفتين نفس Hash.

لذلك:

Hash Match
↓
Character Verification
↓
Real Match or Collision

ولا يجب الاعتماد على Hash وحده لإثبات أن النصين متساويان.

Polynomial Hash

يمكن تمثيل النص بصورة شبيهة بالآتي:

A × base² + B × base + C

ثم استخدام Modulo مع عدد Prime لتقييد حجم القيمة.

TypeScript

function rabinKarp(
  text: string,
  pattern: string
): number {
  const n = text.length;
  const m = pattern.length;

  if (m === 0) return 0;
  if (m > n) return -1;

  const base = 256;
  const prime = 101;

  let patternHash = 0;
  let windowHash = 0;
  let highOrder = 1;

  for (let i = 0; i < m - 1; i++) {
    highOrder = (highOrder * base) % prime;
  }

  for (let i = 0; i < m; i++) {
    patternHash = (
      base * patternHash + pattern.charCodeAt(i)
    ) % prime;

    windowHash = (
      base * windowHash + text.charCodeAt(i)
    ) % prime;
  }

  for (let i = 0; i <= n - m; i++) {
    if (
      patternHash === windowHash &&
      text.slice(i, i + m) === pattern
    ) {
      return i;
    }

    if (i < n - m) {
      windowHash = (
        base * (
          windowHash -
          text.charCodeAt(i) * highOrder
        ) +
        text.charCodeAt(i + m)
      ) % prime;

      if (windowHash < 0) {
        windowHash += prime;
      }
    }
  }

  return -1;
}

التعقيد

في الحالة المتوسطة:

O(n + m)

لكن في أسوأ حالة، إذا حدث عدد كبير من Collisions:

O(n × m)

أما الذاكرة الإضافية:

O(1)

في النسخة الأساسية.

Rabin–Karp مقابل KMP

KMP تعتمد على Prefix وSuffix ومصفوفة LPS وتضمن O(n + m).

أما Rabin–Karp فتعتمد على Hash وRolling Hash، وتملك أداء متوسطاً جيداً لكن Worst Case أسوأ.

التطبيقات

يمكن استخدام أفكار Rolling Hash في:

• String Search
• Plagiarism Detection
• Duplicate Content Detection
• DNA Sequence Search
• Document Fingerprinting
• Substring Queries
• البحث عن عدة Patterns

عدة Patterns

إذا كانت لدينا Patterns كثيرة بالطول نفسه، يمكن حفظ Hash لكل Pattern داخل Set ثم مقارنة Hash كل Window من Text مع تلك المجموعة.

هذه إحدى الحالات التي تكون فيها الفكرة المبنية على Hash جذابة جداً.

Double Hashing

لتقليل احتمال Collision يمكن استخدام Hashين مستقلين بقيم Prime مختلفة.

لا نعتبر Window Candidate إلا إذا تطابقت القيمتان.

أخطاء شائعة

• الاعتماد على Hash فقط دون Verification.
• حساب Hash كل Window من البداية.
• نسيان Modulo.
• اختيار Hash Function ضعيفة.
• حذف قيمة الحرف القديم بوزن خاطئ.

سؤال مقابلات

قد يطلب منك البحث عن Pattern باستخدام Rolling Hash.

يجب شرح:

Pattern Hash
Initial Window Hash
Rolling Update
Hash Comparison
Collision Verification
Complexity

الخلاصة

Rabin–Karp تجمع بين Sliding Window وHashing.

Text
↓
Rolling Hash
↓
Compare with Pattern Hash
↓
Verify

وأهم فكرة قابلة لإعادة الاستخدام في الخوارزمية هي Rolling Hash التي تسمح بتحديث Hash للنافذة الجديدة باستخدام نتيجة النافذة السابقة.