برداشت کلی شما از مقاله‌ی داده‌شده چیست؟

مقاله: در صورتی که متنی به طول n به صورت [t [۱.. n و رشته‌ای به طول m به صورت [p [۱.. m داشته باشیم که، آسان‌ترین و ناکارآمدترین راه برای جستجو، الگوریتم جستجوی رشته ساده‌لوحانه است که همه حالت‌های ممکن را به این صورت بررسی می‌کند: در هر مرحله رشته [p [۱.. m با زیررشته‌ای از متن t مقایسه می‌گردد. زیررشته موردنظر در مرحله اول m حرف اول از متن ([t [۱.. m)، در مرحله دوم m حرف دوم از متن ([t [۲.. m+ ۱) و به همین ترتیب در مرحله s ام m حرف s ام از متن ([t [s+ ۱.. s+m) می‌باشد. در این مقایسه‌ها، هر بار که دو رشتۀ مقایسه‌شده یکسان باشند، نشانگر یک‌بار رخ‌دادن رشته p در متن t است. هر مقایسه در زمان انجام می‌شود. از آنجا که ۱ +n-m مقایسه داریم این الگوریتم از مرتبه زمانی خواهد بود. الگوریتم رابین-کارپ سعی دارد با به‌کارگیری تابع درهم‌سازی، سرعت مقایسۀ رشتۀ الگو و زیررشته‌های متن را افزایش داده و از این طریق زمان اجرا را بهبود ببخشد. یک تابع درهم‌سازی، تابعی است که مجموعۀ بزرگی از داده‌ها را به مجموعۀ کوچکتری از داده‌ها نگاشت می‌کند. در اینجا تابع درهم‌سازی هر رشته را به یک مقدار عددی که به آن مقدار درهم‌سازی می‌گویند، تبدیل می‌کند. برای مثال اگر تابع را برابر طول رشته تعریف کنیم hash («hello») = ۵ و hash («cat») = ۳ خواهد بود. الگوریتم رابین-کارپ با بهره‌گیری از این حقیقت که اگر دو رشته یکسان باشند، مقدار درهم‌سازی آن‌ها نیز با هم برابر خواهد بود، سعی دارد به جای مقایسه حرف یه حرف دو رشته، مقادیر درهم‌سازی آنان را مقایسه کند. برای این کار کافی است مقدار درهم‌سازی رشته الگو را حساب نماید و سپس در متن به دنبال زیررشته‌ای با مقدار درهم‌سازی برابر با آن بگردد. نکته‌ای که باید به آن توجه کرد این است که رشته‌های مختلف می‌توانند مقادیر درهم‌سازی یکسان داشته باشند. به این رویداد تصادم گفته می‌شود. مثلا در مثال بالا مقدار درهم‌سازی هر رشتۀ پنج حرفی برابر ۵ خواهد بود. پس با اینکه یکسان بودن دو رشته به معنای یکسان بودن مقدار درهم‌سازی آنان است اما عکس این موضوع لزوما برقرار نیست. در نتیجه در صورت برابر نبودن مقدار درهم‌سازی رشتۀ الگو و زیررشته قطعا می‌توان نتیجه گرفت که خود رشته‌ها نیز با هم برابر نیستند ولی در صورت برابر بودن این دو مقدار لزوما نمی‌توان برابری رشته‌ها را نتیجه گرفت (برابری …
برداشت:
الگوریتم جستجوی رشتهٔ رابین-کارپ یکی از الگوریتم‌های تطابق رشته است که در سال ۱۹۸۷ توسط مایکل او.رابین و ریچارد ام.کارپ ارائه شد . از این الگوریتم برای پیدا کردن مجموعه‌ای از رشته‌ها (الگوها) در یک متن با به‌کارگیری درهم‌سازی استفاده می‌شود . این کار در دو مرحله پیش‌پردازش و تطابق انجام می‌گیرد که اگر یک متن به طول n و رشته‌ای به طول m داشته باشیم که ، مرحلۀ اول در زمان و مرحلۀ دوم در بدترین حال در زمان انجام می‌شود . هر چند زمان میانگین اجرای مرحله دوم بر اساس فرضیات خاصی می‌تواند به بهبود یابد .