الگوریتم‌های تطبیق رشته: جستجوی ساده، Rabin-Karp، و فراتر از آن

مسئله تطبیق رشته

با داشتن یک Text (متن) T به طول n و یک Pattern (الگو) P به طول m (جایی که m ≤ n)، String-Matching Problem (مسئله تطبیق رشته) هر موقعیت در T که P به‌عنوان یک زیررشته رخ می‌دهد را می‌خواهد. این عملیات زیربنای توابع جستجوی ویرایشگر متن، تطبیق توالی DNA در بیوانفورماتیک، و تشخیص سرقت ادبی یا تکرار کد است.

الگوریتم تطبیق رشته ساده

ساده‌ترین رویکرد هر موقعیت شروع ممکن در متن را بررسی می‌کند، و الگو را کاراکتر‌به‌کاراکتر در هر موقعیت مقایسه می‌کند.

NAIVE-STRING-MATCHER(T, P, n, m):
  برای s = 0 تا n - m:
      اگر P[1..m] == T[s+1..s+m]:
          چاپ "الگو با جابه‌جایی رخ می‌دهد" s

در بدترین‌حالت، زمان اجرای این الگوریتم O((n-m+1)m) است، چون برای هرکدام از n-m+1 موقعیت شروع ممکن، تا m کاراکتر ممکن است نیاز به مقایسه داشته باشد پیش از پیداشدن یک عدم‌تطابق (یا تأیید یک تطبیق کامل).

یک بدترین‌حالت آسیب‌شناختی:
متن:    "aaaaaaaaaaaaaaaaaaaaaaaaaab"
الگو:   "aaaaaaaaab"

در تقریباً هر موقعیت شروع، الگوریتم باید
تقریباً همه m کاراکتر الگو را پیش از یافتن
عدم‌تطابق (یا تأیید تطبیق نهایی) مقایسه کند،
که رفتار بدترین‌حالت کامل O(nm) تولید می‌کند

با وجود این بدترین‌حالت ضعیف، الگوریتم ساده در عمل به‌طور معقولی برای متن معمولی خوب عمل می‌کند، جایی که عدم‌تطابق‌ها معمولاً در چند مقایسه کاراکتر اول پیدا می‌شوند، و سادگی‌اش آن را به یک پیش‌فرض معقول برای الگوهای کوتاه یا جستجوهای کم‌تکرار تبدیل می‌کند.

الگوریتم Rabin-Karp: استفاده از هشینگ برای سرعت

Rabin-Karp Algorithm (الگوریتم رابین-کارپ) رویکرد اساساً متفاوتی اتخاذ می‌کند: به‌جای مقایسه مستقیم کاراکترها در هر موقعیت، یک مقدار هش عددی، که پیش‌تر در این مجموعه درباره جداول هش بحث شد، برای الگو و برای هر زیررشته با طول-m متن محاسبه می‌کند، و فقط یک مقایسه کاراکتر کامل را وقتی مقادیر هش تطبیق دارند انجام می‌دهد.

محاسبه کارآمد مقادیر هش با هش غلتان

بینش کلیدی‌ای که این را کارآمد می‌کند یک تکنیک Rolling Hash (هش غلتان) است: به‌جای محاسبه مجدد هش هر زیررشته از صفر، که زمان O(m) به‌ازای هر موقعیت می‌گرفت و هر مزیت سرعتی را حذف می‌کرد، هش زیررشته بعدی می‌تواند در زمان O(1) از هش زیررشته فعلی محاسبه شود.

رفتار با هر زیررشته به‌عنوان یک عدد در مبنای d
(جایی که d اندازه الفبای کاراکتر است):

hash(T[s+1..s+m]) = T[s+1]·d^(m-1) + T[s+2]·d^(m-2)
                     + ... + T[s+m]

برای لغزاندن پنجره یک موقعیت به جلو:
hash(T[s+2..s+m+1]) =
  (hash(T[s+1..s+m]) - T[s+1]·d^(m-1)) · d + T[s+m+1]

این سهم کاراکتر پیشتاز را حذف می‌کند،
رقم‌های باقی‌مانده را شیفت می‌دهد، و
کاراکتر انتهایی جدید را اضافه می‌کند — همه در زمان O(1)

در عمل، این محاسبه به‌پیمانه یک عدد اول بزرگ q انجام می‌شود، تا مقادیر هش را در یک بازه قابل‌مدیریت نگه دارد و از سرریز اجتناب کند، در حالی که همچنان ویژگی اینکه زیررشته‌های برابر همیشه مقادیر هش برابر تولید می‌کنند را حفظ می‌کند.

الگوریتم

RABIN-KARP-MATCHER(T, P, n, m, d, q):
  h = d^(m-1) mod q
  p = 0    // مقدار هش الگو
  t0 = 0   // مقدار هش اولین پنجره متن
  برای i = 1 تا m:
      p = (d·p + P[i]) mod q
      t0 = (d·t0 + T[i]) mod q
  برای s = 0 تا n - m:
      اگر p == ts:
          اگر P[1..m] == T[s+1..s+m]:    // برای رد کردن تطبیق نادرست تأیید کن
              چاپ "الگو با جابه‌جایی رخ می‌دهد" s
      اگر s < n - m:
          ts+1 = (d·(ts - T[s+1]·h) + T[s+m+1]) mod q

چرا گام تأیید ضروری است

از آنجا که زیررشته‌های متفاوت گاهی می‌توانند همان مقدار هش را تولید کنند، رویدادی به نام Spurious Hit (تطبیق نادرست)، الگوریتم همیشه باید یک تطبیق کاراکتر-به-کاراکتر کامل را هروقت مقادیر هش توافق داشته باشند تأیید کند، به‌جای اعتماد صرف به تطبیق هش. رد‌کردن این گام