الگوریتم جستجوی رشته رابین-کارپ

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم جستجوی رشتهٔ رابین-کارپ یکی از الگوریتم‌های تطابق رشته است که در سال 1987 توسط مایکل او. رابین و ریچارد ام. کارپ ارائه شد. از این الگوریتم برای پیدا کردن مجموعه‌ای از رشته‌ها (الگوها[۱]) در یک متن با به‌کارگیری درهم‌سازی استفاده می‌شود. این کار در دو مرحله پیش‌پردازش [۲] و تطابق [۳] انجام می‌گیرد که اگر یک متن به طول n و رشته‌ای به طول m داشته باشیم که  m\le \;n ، مرحلۀ اول در زمان \Theta(m) و مرحلۀ دوم در بدترین حال در زمان  \Theta(m(n-m+1)) انجام می‌شود. هر چند زمان میانگین اجرای مرحله دوم بر اساس فرضیات خاصی می‌تواند به  \Theta(m+n) بهبود یابد.

جستجو با استفاده از شیفت دادن زیررشته[ویرایش]

در صورتی که متنی به طول n به صورت [T[1..n و رشته‌ای به طول m به صورت [P[1..m داشته باشیم که  m\le \;n ، آسان‌ترین و ناکارآمدترین راه برای جستجو، الگوریتم جستجوی رشتهٔ نیو است که همه حالت‌های ممکن را به این صورت بررسی می‌کند:

در هر مرحله رشته [P[1..m با زیررشته‌ای از متن T مقایسه می‌گردد. زیررشته موردنظر در مرحله اول m حرف اول از متن ([T[1..m)، در مرحله دوم m حرف دوم از متن ([T[2..m+1) و به همین ترتیب در مرحله s ام m حرف s ام  (0 \le \; s \le \; n-m) از متن ([T[s+1..s+m) می‌باشد. در این مقایسه‌ها، هر بار که دو رشتۀ مقایسه‌شده یکسان باشند، نشانگر یک‌بار رخ‌دادن رشته P در متن T است.

procedure NaiveStringMatcher (T,P)
begin
  n=lenght(T);
  m=lenght(P);
  for s=0 to n-m do
    if P[1...m]=T[s+1...s+m] then
      print «Pattern occurs with shift» s;
end

هر مقایسه در زمان \Theta(m) انجام می‌شود. از آنجا که 1+n-m مقایسه داریم این الگوریتم از مرتبه زمانی  \Theta(m(n-m+1)) خواهد بود.

الگوریتم رابین-کارپ سعی دارد با به‌کارگیری تابع درهم‌سازی، سرعت مقایسۀ رشتۀ الگو و زیررشته‌های متن را افزایش داده و از این طریق زمان اجرا را بهبود ببخشد.

استفاده از درهم‌سازی[ویرایش]

یک تابع درهم‌سازی، تابعی است که مجموعۀ بزرگی از داده‌ها را به مجموعۀ کوچکتری از داده‌ها نگاشت می‌کند. در اینجا تابع درهم‌سازی هر رشته را به یک مقدار عددی که به آن مقدار درهم‌سازی می‌گویند، تبدیل می‌کند. برای مثال اگر تابع را برابر طول رشته تعریف کنیم hash("hello") = 5 و hash("cat") = 3 خواهد بود.

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

نکته‌ای که باید به آن توجه کرد این است که رشته‌های مختلف می‌توانند مقادیر درهم‌سازی یکسان داشته باشند. به این رویداد تصادم [۴] گفته می‌شود. مثلاً در مثال بالا مقدار درهم‌سازی هر رشتۀ پنج حرفی برابر 5 خواهد بود. پس با اینکه یکسان بودن دو رشته به معنای یکسان بودن مقدار درهم‌سازی آنان است اما عکس این موضوع لزوماً برقرار نیست. در نتیجه در صورت برابر نبودن مقدار درهم‌سازی رشتۀ الگو و زیررشته قطعاً می‌توان نتیجه گرفت که خود رشته‌ها نیز با هم برابر نیستند ولی در صورت برابر بودن این دو مقدار ، ممکن است دو رشته با مقدار درهم‌سازی برابر یافت کرده باشیم در حالی که اصل رشته‌ها برابر نیستند پس یکسان بودن زیررشته با رشتۀ الگو را باید با مقایسه حرف به حرف تحقیق کنیم که درصورتی که واقعاً تصادم رخ داده باشد این کار زمان اجرا را بیهوده افزایش داده است. خوشبختانه اگر تابع درهم‌سازی را خوب تعریف کنیم می‌توانیم امیدوار باشیم این رویداد زیاد رخ ندهد و زمان اجرای میانگین، مطلوب باشد.

تابع درهم‌سازی استفاده شده در رابین-کارپ به این صورت تعریف می‌شود:

 hash(T[1 .. m]) = (T[1]×dm-1 + T[2]×dm-2 + ... + T[m]×d0) mod q

که در آن d و q دو مقدار ثابت هستند. اگر \Sigma مجموعۀ الفبا باشد، d به طور معمول اینگونه تعریف می‌شود: d=\left| \Sigma \right| و q نیز عموماً یک عدد اول بزرگ در نظر گرفته می‌شود به طوری که qd در یک کلمه از کامپیوتر[۵] جا بگیرد.

برای مثال اگر فرض کنیم \Sigma=\{0,1,2,...,9\}، متن موردنظر ما T=''43141567'' و برای راحتی کار q=1 باشد، خواهیم داشت: d=10 و مقدار درهم‌سازی زیررشته "31415" به طول 5 از متن برابر است با:

( 3×104 + 1×103 + 4×102 + 1×101 + 5×100 ) mod 1 = 31415 mod 1 = 31415

مقدار تابع درهم‌سازی تعریف شده را برای هر رشته به طول m می‌توان با استفاده از روش هورنر در زمان \Theta(m) به این صورت محاسبه کرد:

 hash(T[1 .. m]) = (T[m] + d(T[m-1] + d(T[m-2] + ... + d(T[2] + dT[1])...)))  mod q

حال اگر بخواهیم برای هر زیررشته یک‌بار مقدار این تابع را حساب کنیم از آنجا که n-m+1 زیررشته داریم، این کار  \Theta(m(n-m+1)) طول می‌کشد که همان زمان اجرای الگوریتم نیو می‌باشد و در حقیقت زمان اجرا بهبود نیافته است. برای حل این مشکل از درهم‌سازی چرخشی[۶] استفاده می‌کنیم. درهم‌سازی چرخشی به ما امکان می‌دهد تا مقدار درهم‌سازی زیررشتۀ هر مرحله را از روی مقدار درهم‌سازی زیررشتۀ مرحله قبلی در زمان ثابت به دست بیاوریم. این روند در حال کلی به صورت زیر است:

 s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]

در الگوریتم رابین-کارپ اگر مقدار درهم‌سازی زیررشته در مرحله s ام را t_s بنامیم، رابطۀ درهم‌سازی چرخشی به این صورت خواهد بود:

 ts+1 = ( d( ts - dm-1 T[s+1] ) + T[s+m+1] ) mod q    

در مثال گفته شده در بالا اگر بخواهیم مقدار درهم‌سازی زیررشته مرحله بعد یعنی "14156" را از روی مقدار درهم‌سازی زیررشته قبل یعنی "31415" حساب کنیم روند کار به این صورت خواهد بود:

ts+1 = ( 10×(31415 - 104 × 3) + 6 ) mod 1 = 14156

در نهایت می‌توان گفت در الگوریتم رابین-کارپ کافی است تنها مقدار درهم‌سازی رشتۀ الگو [P[1..m و مقدار درهم‌سازی زیررشته [T[1..m از متن را در بخش پیش پردازش با زمان \Theta(m) محاسبه کرد و سپس محاسبه مقادیر درهم‌سازی زیررشته‌های مراحل بعد در هر مرحله با زمان \Theta(1) قابل انجام است.

الگوریتم و زمان اجرا[ویرایش]

شبه‌کد الگوریتم رابین-کارپ را می‌توان به این صورت نشان داد:

procedure Rabin-Karp-Matcher (T,P,d,q)
begin
1 n = lenght(T);
2 m = lenght(P);
3 h = d^(m-1) mod q;
4 p = 0;
5 t = 0;
6 
7 for i = 1 to m do // Preprocessing
8 p = (d*p + P[i]) mod q;
9 t = (d*t + T[i]) mod q;
10
11 for s = 0 to n-m do // Matching
12 if p = t then
13 if P[1...m] = T[s+1...s+m] then
14 print «Pattern occurs with shift» s;
15 if s <n-m then
16 t = ( d * (t - T[s+1]*h ) + T[s+m+1] ) mod q; 
end

خطوط 8 و 9 در زمان ثابت اجرا می‌شوند و کل حلقه در خط 7، m بار تکرار می‌گردد پس مرحلۀ پیش‌پردازش از مرتبۀ زمانی \Theta(m) خواهد بود.

خط 13 نیز در زمان \Theta(m) اجرا می‌شود و از آنجا که احتمال اجرای آن در هر بار تکرار حلقه وجود دارد، مرتبۀ زمانی اجرای حلقه در بدترین حالت برابر  \Theta(m(n-m+1)) است.

اما در بسیاری از حالت‌ها انتظار می‌رود تطابق رشتۀ الگو و زیررشته، دفعات کمی رخ دهد (مثلاً به تعداد ثابتی مانند c از کل دفعات تکرار حلقه). در این صورت زمان اجرای موردانتظار مرحله تطابق برابر با  \operatorname{O}((n-m+1)+cm) = \operatorname{O}(n+m)  خواهد بود.

الگوریتم رابین-کارپ و جستجوی رشتۀ چندالگویی [۷][ویرایش]

الگوریتم رابین-کارپ در جستجوی رشتۀ تک‌الگویی [۸] نسبت به الگوریتم کنوث-موریس-پرت، الگوریتم جستجوی رشته بویر-مور و دیگر الگوریتم‌های سریع جستجوی رشتۀ تک‌الگویی، به علت زمان اجرای کند خود در بدترین حالت، عملکرد ضعیف‌تری دارد اما برای جستجوی رشتۀ چندالگویی الگوریتم مناسبی به شمار می‌رود.

اگر بخواهیم هر یک از الگوهای با طول ثابت k را در متن جستجو کنیم، کافی است گونه‌ای از الگوریتم رابین-کارپ را بسازیم که با استفاده از داده ساختار مجموعه [۹] تعیین می‌کند که آیا مقدار درهم‌سازی زیررشتۀ موردنظر از متن در مجموعۀ مقادیر درهم‌سازی الگوها وجود دارد یا خیر. فرض می‌کنیم همه زیررشته‌ها به طول ثابت m هستند:

 function RabinKarpSet(string s[1..n], set of string subs, m):
     set hsubs := emptySet
     for each sub in subs
         insert hash(sub[1..m]) into hsubs
     hs := hash(s[1..m])
     for i from 1 to n-m+1
         if hs ∈ hsubs and s[i..i+m-1] ∈ subs
             return i
         hs := hash(s[i+1..i+m])
     return not found

برای جستجوی k الگو در متن با روش نیو باید k بار جستجوی رشتۀ تک‌الگویی نیو اجرا گردد که با توجه به فرض ثابت بودن m می‌توان گفت این کار از مرتبۀ زمانی  \operatorname{O}(nk) است. اما الگوریتم بالا می‌تواند همه k الگو را در زمان  \operatorname{O}(n+k) بیابد زیرا با به‌کارگیری یک جدول درهم‌سازی در زمان  \operatorname{O}(1) می‌توان مشخص کرد که آیا مقدار درهم‌سازی یک زیررشته با مقادیر درهم‌سازی هر یک از الگوها برابر است یا خیر.

پانویس[ویرایش]

  1. patterns
  2. preprocessing
  3. matching
  4. collision
  5. computer word
  6. rolling hash
  7. multiple pattern search
  8. single pattern search
  9. set data structure

جستارهای وابسته[ویرایش]

منابع[ویرایش]

  • Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Clifford Stein (2001-09-01). "The Rabin–Karp algorithm". Introduction to Algorithms (2nd edition ed.). Cambridge, Massachusetts: MIT Press. pp. 911–916. ISBN 978-0262032933.  Unknown parameter |origdate= ignored (|origyear= suggested) (help);

پیوند به بیرون[ویرایش]