الگوریتم رابین-کارپ

یکی از مسائلی که در زمینه‌های مختلف مرتبط با کامپوتر مطرح است،‌ مسائل مربوط به پیدا کردن یک رشته (عموما نه چندان بلند) در میان یک رشته‌ی بسیار بلند است. به صورت دقیق‌تر، فرض کنید می‌خواهیم یک رشته‌ی $m$ حرفی را در یک رشته‌ی $n$ حرفی به صورت یک زیررشته‌ی متوالی پیدا کنیم. پیاده‌سازی بدیهی چنین جستجویی،‌ دارای پیچیدگی زمانی $O(nm)$ خواهد بود. الگوریتم رابین - کارپ با استفاده از تکنیک درهم‌سازی این مسئله را در پیچیدگی زمانی $O(n + m)$ حل می‌کند.

فرض کنید یک زیررشته‌ی متوالی شامل حروف $i$ تا $j$ یک رشته رابا $s[i..j]$ نشان دهیم. فرض کنید بخواهیم رشته‌ی $s$ را در $t$ پیدا کنیم. الگوریتم جستجو به شکل زیر عمل می‌کند:

به ازای هر $i$، زیررشته‌ی $s[i..i + m - 1]$ را با $t$ مقایسه کنید و در صورت برابر بودن این زیررشته را به عنوان یک نسخه از $t$ در $s$ گزارش کنید.

اگر زمان مقایسه‌ی دو رشته به طول $x$ را با $f(x)$ نشان دهیم الگوریتم در $O(f(x) * n)$ انجام می‌شود. در حالت عادی $f(x) = O(m)$. الگوریتم رابین‌کارپ روشی برای مقایسه‌ی دو رشته ارائه می‌دهد که به صورت متوسط $f(x) = O(1)$. هر چند در واقع در بدترین حالت یک جستجو می‌تواند زمان $O(m)$ طول بکشد اما چنین اتفاقی با احتمال کمی رخ می‌دهد.

الگوریتم رابین‌کارپ جستجو را به این گونه تغییر می‌دهد که پیش از مقایسه‌ی دو رشته در $O(m)$ ابتدا مقدار یک تابع درهم‌ساز را برای آن‌ها محاسبه کرده و تنها در صورت برابری این مقایسه را انجام می‌دهد. نکته‌ی الگوریتم رابین‌کارپ محاسبه‌ی این تابع به گونه‌ای است که در مجموع در زمان $O(n + m)$ قابل انجام است. بعلاوه با وجود اینکه احتمال برابری تابع درهم‌ساز برای دو رشته‌ی نابرابر وجود دارد، این احتمال برای تابع درهم‌ساز مورد استفاده کم است.

A.c

function NaiveSearch(string s[1..n], string pattern[1..m])
 
   for i from 1 to n-m+1
 
      for j from 1 to m
 
         if s[i+j-1] ≠ pattern[j]
 
            jump to next iteration of outer loop
 
      return i
 
   return not found

‌‌B.c

function RabinKarp(string s[1..n], string pattern[1..m])
 
  hpattern := hash(pattern[1..m]);
 
  for i from 1 to n-m+1
 
    hs := hash(s[i..i+m-1])
 
    if hs = hpattern
 
      if s[i..i+m-1] = pattern[1..m]
 
        return i
 
  return not found

تابع درهم‌ساز «اثر انگشت رابین» تابعی است که در این الگوریتم برای درهم‌سازی رشته‌ها استفاده می‌شود. این الگوریتم هر زیررشته را معادل یک عدد در یک مبنای ثابت در نظر می‌گیرد. مبنای مورد استفاده معمولا یک عدد اول بزرگ است. در این الگوریتم هر حرف معادل یک رقم است و مقدار آن برابر کد ASCII آن حرف در نظر گرفته می‌شود. برای مثال :

// ASCII a = 97, b = 98, r = 114. 
hash("abr") = (97 × 1012) + (98 × 1011) + (114 × 1010) = 999,509 

نکته‌ی این الگوریتم آن است که اگر مقدار آن برای زیررشته‌ی $s[i..j]$ محاسبه شده باشد، مقدار آن برای زیررشته‌ی $s[i + 1..j + 1]$ در $O(1)$ قابل محاسبه است. برای مثال اگر $s = abracadabra$ می‌توان از روی مقدار hash(«abr») مقدار hash(«bra») را به شکل زیر محاسبه کرد:

//             base   old hash    old 'a'         new 'a'
hash("bra") = [1011 × (999,509 - (97 × 1012))] + (97 × 1010) = 1,011,309

پس بنابراین در الگوریتم مقایسه‌ی بالا، کافی است در ابتدا در $O(m)$ مقدار تابع برای $s[1..m]$ را محاسبه کرد و پس از آن در هرمرحله مقدار تابع برای $s[i..i + m - 1]$ را از روی مقدار تابع برای $s[i - 1..i + m - 2]$ محاسبه کرد. در این صورت پیچیدگی زمانی از $O(n + m)$ خواهد بود.

• Wikipedia