الگوریتم رابین کارپ (Rabin–Karp Algorithm) – به زبان ساده

۱۴۰۲/۰۲/۱۹

۱۰ دقیقه

۱۳۸۱

آموزش متنی جامع

در این مطلب، «الگوریتم رابین کارپ» (Rabin-Karp Algorithm) که برای جستجوی رشته و الگو استفاده می‌شود، مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل ++C، «سی» (C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌ شارپ» (#C) و «پی‌اچ‌پی» (PHP) انجام شده است.

فهرست مطالب این نوشته

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

عبارت بالا چگونه کار می‌کند؟

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

فرض می‌شود که متن [text txt[0..n-1 و الگوی [pat[0..m-1 داده شده است. هدف نوشتن تابع جستجویی (char pat[], char txt[]‎) است که همه وقوع‌های []pat در []txt را چاپ کند.

فیلم آموزش طراحی الگوریتم – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

همچنین، فرض می‌شود که n > m است. مثال زیر در این راستا قابل توجه است.

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

الگوریتم رابین کارپ -- به زبان ساده

الگوریتم تطبیق الگوی ساده، الگو را به صورت اسلایدی (کشویی) در متن جستجو می‌کند. پس از هر اسلاید، کاراکترها یکی یکی در قسمت کنونی بررسی می‌شوند و اگر مطابق با الگو بودند، پرینت می‌شوند. همچون الگوریتم جستجوی رشته ساده، الگوریتم رابین کارپ نیز الگو را یکی یکی اسلاید می‌کند. اما بر خلاف الگوریتم ساده، به جای خود الگو و خود متن، الگوریتم رابین کارپ مقدار هش الگو را با مقدار هش زیر رشته کنونی از متن مطابقت می‌دهد و اگر مقادیر هش با یکدیگر تطبیق داشته باشند، تطبیق کاراکتر به کاراکتر انجام می‌شود. بنابراین، الگوریتم رابین کارپ نیاز به محاسبه مقادیر هش برای رشته‌های زیر دارد.

خود الگو
همه زیر رشته‌های موجود در متن به طول m

از آنجا که نیاز به محاسبه موثر مقادیر هش برای همه زیررشته‌ها با اندازه m از متن است، باید یک تابع هش داشت که دارای مشخصاتی باشد که در ادامه بیان شده است. هش در هر جا به جایی (شیفت)، باید به طور موثری بر اساس مقادیر هش کنونی و کاراکتر بعدی در متن قابل محاسبه باشد. در واقع می‌توان گفت ([hash(txt[s+1 .. s+m باید به طور کارایی از ([hash(txt[s .. s+m-1 و [txt[s+m قابل محاسبه باشد؛ یعنی [(hash(txt[s+1 .. s+m])= rehash(txt[s+m], hash(txt[s .. s+m-1 و rehash باید عملیات از درجه (O(1 باشد.

تابع هش توصیه شده توسط رابین و کارپ، یک مقدار صحیح را محاسبه می‌کند. مقدار صحیح برای یک رشته، یک مقدار عددی از رشته است. برای مثال، اگر همه کاراکترهای ممکن از ۱ تا ۱۰ هستند، مقدار عددی "122" برابر با ۱۲۲ خواهد بود. تعداد کاراکترهای ممکن بالاتر از ۱۰ است (عموما ۲۵۶) و طول الگو می‌تواند بزرگ باشد. بنابراین، مقادیر عددی را نمی‌توان به صورت کاربردی به عنوان عدد صحیح ذخیره کرد. بنابراین، مقدار عددی با استفاده از «حساب ماژولار» (Modular Arithmetic) محاسبه می‌شود تا اطمینان حاصل شود که مقادیر هش را می‌توان در یک متغیر صحیح ذخیره کرد (می‌تواند در کلمات حافظه جا شود). برای هش کردن دوباره (بازهش)، نیاز به خارج کردن قابل توجه‌ترین رقم و افزودن کم اهمیت‌ترین رقم جدید در مقدار هش است. بازهش کردن با استفاده از فرمول زیر انجام می‌شود.

hash( txt[s+1 .. s+m] ) = ( d ( hash( txt[s .. s+m-1]) – txt[s]*h ) + txt[s + m] ) mod q

hash( txt[s .. s+m-1] ): s مقدار هش در شیفت

hash( txt[s+1 .. s+m] ): (s+1 مقدار هش در شیفت بعدی (یا شیفت

d: تعداد کاراکترها در الفبا

q: یک عدد اول

h: d^(m-1)

عبارت بالا چگونه کار می‌کند؟

این یک راهکار ریاضیاتی ساده است که در آن، مقدار اعشاری پنجره کنونی بر اساس پنجره پیشین محاسبه می‌شود. برای مثال، طول الگو ۳ و رشته «۲۳۴۵۶» است. مقدار اولین پنجره (که ۲۳۴ است) برابر با «۲۳۴» محاسبه شده است. برای محاسبه پنجره بعدی یعنی «۳۴۵»، محاسبه ۵+۱۰*(۱۰۰*۲– ۲۳۴) انجام و نتیجه ۳۴۵ حاصل می‌شود.

فیلم آموزش طراحی الگوریتم و حل مثال در فرادرس

کلیک کنید

الگوریتم رابین کارپ در ++C

خروجی قطعه کدهای بالا به صورت زیر است.

Pattern found at index 0
Pattern found at index 10

زمان اجرای میانگین و بهترین حالت برای الگوریتم رابین کارپ از درجه (O(n+m و بدترین حالت از درجه (O(nm است. بدترین حالت از الگوریتم رابین کارپ هنگامی به وقوع می‌پیوندد که همه کاراکترهای الگو و متن مشابه باشند، به طوری که مقادیر هش همه زیر مجموعه‌های []txt با مقدار هش []pat تطبیق پیدا کنند. برای مثال، ”pat[] = “AAA و ”txt[] = “AAAAAAA.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

محصول، خدمات یا برند خود را در مجله فرادرس معرفی کنید.

کلیک کنید

مطالب مجله فرادرس را در جستجوی گوگل سریع‌تر ببینید

بر اساس رای ۸ نفر

آیا این مطلب برای شما مفید بود؟

اگر پرسشی درباره این مطلب دارید، آن را با ما مطرح کنید.

منابع:

«الهام حصارکی»، فارغ‌التحصیل مقطع کارشناسی ارشد مهندسی فناوری اطلاعات، گرایش سیستم‌های اطلاعات مدیریت است. او در زمینه هوش مصنوعی و داده‌کاوی، به ویژه تحلیل شبکه‌های اجتماعی، فعالیت می‌کند.

مطالب مرتبط