الگوریتم جستجوی رشته رابین-کارپ
الگوریتم جستجوی رشتهٔ رابین-کارپ یکی از الگوریتمهای تطابق رشته است که در سال 1987 توسط مایکل او. رابین و ریچارد ام. کارپ ارائه شد. از این الگوریتم برای پیدا کردن مجموعهای از رشتهها (الگوها) در یک متن با بهکارگیری درهمسازی استفاده میشود. این کار در دو مرحله پیشپردازش و تطابق انجام میگیرد که اگر یک متن به طول n و رشتهای به طول m داشته باشیم که
جستجو با استفاده از شیفت دادن زیررشته
در صورتی که متنی به طول n به صورت [T[1..n و رشتهای به طول m به صورت [P[1..m داشته باشیم که
در هر مرحله رشته [P[1..m با زیررشتهای از متن T مقایسه میگردد. زیررشته موردنظر در مرحله اول m حرف اول از متن ([T[1..m)، در مرحله دوم m حرف دوم از متن ([T[2..m+1) و به همین ترتیب در مرحله s ام m حرف s ام
procedure NaiveStringMatcher (T,P)
begin
n=length(T);
m=length(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
هر مقایسه در زمان
الگوریتم رابین-کارپ سعی دارد با بهکارگیری تابع درهمسازی، سرعت مقایسۀ رشتۀ الگو و زیررشتههای متن را افزایش داده و از این طریق زمان اجرا را بهبود ببخشد.
استفاده از درهمسازی
یک تابع درهمسازی، تابعی است که مجموعۀ بزرگی از دادهها را به مجموعۀ کوچکتری از دادهها نگاشت میکند. در اینجا تابع درهمسازی هر رشته را به یک مقدار عددی که به آن مقدار درهمسازی میگویند، تبدیل میکند. برای مثال اگر تابع را برابر طول رشته تعریف کنیم hash("hello") = 5 و hash("cat") = 3 خواهد بود.
الگوریتم رابین-کارپ با بهرهگیری از این حقیقت که اگر دو رشته یکسان باشند، مقدار درهمسازی آنها نیز با هم برابر خواهد بود، سعی دارد به جای مقایسه حرف یه حرف دو رشته، مقادیر درهمسازی آنان را مقایسه کند. برای این کار کافی است مقدار درهمسازی رشته الگو را حساب نماید و سپس در متن به دنبال زیررشتهای با مقدار درهمسازی برابر با آن بگردد.
نکتهای که باید به آن توجه کرد این است که رشتههای مختلف میتوانند مقادیر درهمسازی یکسان داشته باشند. به این رویداد تصادم گفته میشود. مثلاً در مثال بالا مقدار درهمسازی هر رشتۀ پنج حرفی برابر 5 خواهد بود. پس با اینکه یکسان بودن دو رشته به معنای یکسان بودن مقدار درهمسازی آنان است اما عکس این موضوع لزوماً برقرار نیست. در نتیجه در صورت برابر نبودن مقدار درهمسازی رشتۀ الگو و زیررشته قطعاً میتوان نتیجه گرفت که خود رشتهها نیز با هم برابر نیستند ولی در صورت برابر بودن این دو مقدار لزوماً نمیتوان برابری رشتهها را نتیجه گرفت (برابری مقدار درهمسازی شرط لازم است ولی کافی نیست و ممکن است دو رشته با مقدار درهمسازی برابر یافت کرده باشیم در حالی که اصل رشتهها برابر نیستند). پس در این حالت یکسان بودن زیررشته با رشتۀ الگو را باید با مقایسه حرف به حرف تحقیق کنیم. حال درصورتی که واقعاً تصادم رخ داده باشد (به رشتههای متفاوت با مقدار درهمسازی یکسان برخورد کرده باشیم) این کار زمان اجرا را بیهوده افزایش داده است. خوشبختانه اگر تابع درهمسازی را خوب تعریف کنیم میتوانیم امیدوار باشیم این رویداد زیاد رخ ندهد و زمان اجرای میانگین، مطلوب باشد.
تابع درهمسازی استفاده شده در رابین-کارپ به این صورت تعریف میشود:
hash(T[1 .. m]) = (T[1]×d + T[2]×d + ... + T[m]×d) mod q
که در آن
برای مثال اگر فرض کنیم
( 3×10 + 1×10 + 4×10 + 1×10 + 5×10 ) mod 1 = 31415 mod 1 = 31415
مقدار تابع درهمسازی تعریف شده را برای هر رشته به طول 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 زیررشته داریم، این کار
s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
در الگوریتم رابین-کارپ اگر مقدار درهمسازی زیررشته در مرحله s ام را
ts+1 = ( d( ts - d T[s+1] ) + T[s+m+1] ) mod q
در مثال گفته شده در بالا اگر بخواهیم مقدار درهمسازی زیررشته مرحله بعد یعنی "14156" را از روی مقدار درهمسازی زیررشته قبل یعنی "31415" حساب کنیم روند کار به این صورت خواهد بود:
ts+1 = ( 10×(31415 - 10 × 3) + 6 ) mod 1 = 14156
در نهایت میتوان گفت در الگوریتم رابین-کارپ کافی است تنها مقدار درهمسازی رشتۀ الگو [P[1..m و مقدار درهمسازی زیررشته [T[1..m از متن را در بخش پیش پردازش با زمان
الگوریتم و زمان اجرا
شبهکد الگوریتم رابین-کارپ را میتوان به این صورت نشان داد:
procedure Rabin-Karp-Matcher (T,P,d,q)
begin
1 n = length(T);
2 m = length(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 بار تکرار میگردد پس مرحلۀ پیشپردازش از مرتبۀ زمانی
خط 13 نیز در زمان
اما در بسیاری از حالتها انتظار میرود تطابق رشتۀ الگو و زیررشته، دفعات کمی رخ دهد (مثلاً به تعداد ثابتی مانند c از کل دفعات تکرار حلقه). در این صورت زمان اجرای موردانتظار مرحله تطابق برابر با
الگوریتم رابین-کارپ و جستجوی رشتۀ چندالگویی
الگوریتم رابین-کارپ در جستجوی رشتۀ تکالگویی نسبت به الگوریتم کنوث-موریس-پرت، الگوریتم جستجوی رشته بویر-مور و دیگر الگوریتمهای سریع جستجوی رشتۀ تکالگویی، به علت زمان اجرای کند خود در بدترین حالت، عملکرد ضعیفتری دارد اما برای جستجوی رشتۀ چندالگویی الگوریتم مناسبی به شمار میرود.
اگر بخواهیم هر یک از الگوهای با طول ثابت
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
برای جستجوی
پانویس
جستارهای وابسته
منابع
- Thomas H. Cormen (2001-09-01). "The Rabin–Karp algorithm". Introduction to Algorithms (2nd edition ed.). Cambridge, Massachusetts: MIT Press. pp. 911–916. ISBN 978-0262032933. ; ;