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

الگوریتم های تطبیق رشته ها بخش مهمی از الگوریتم های رشته هستند. وظیفه آنها یافتن تعداد رخداد رشته ها ( الگو نیز نامیده می شود) در داخل یک متن یا رشته بزرگ است.این الگوریتم های تطبیق رشته ها به طور گسترده در زیست شناسی محاسباتی، پردازش سیگنال، بازیابی متن، امنیت رایانه، ویرایشگرهای متن و بسیاری از برنامه های کاربردی دیگر استفاده می شوند. در سیستم هایی مانند تشخیص نفوذ یا جستجو، تکنیک های تطبیق رشته ها بیش از نیمی از کل زمان محاسبات را می گیرد.این الگوریتم های تطبیق رشته ها را می توان به طور عمده به دو دسته فرعی تقسیم کرد: الگوریتم های تطبیق تک رشته ای و تطبیق چند رشته ای.در این مقاله ما بر روی الگوریتم های تطبیق رشته های متعدد تمرکز می کنیم. در الگوریتم تطبیق چند رشته، اگر بخواهیم فقط بررسی کنیم که آیا الگو در متن است یا نه،الگوریتم بویر مور بهترین عملکرد را دارد، اما اگر بخواهیم همه وقوع الگو را در متن پیدا کنیم، رابین کارپ۱ بهترین نتایج را ارائه می دهد.ما شروع کردیم با تجزیه و تحلیل الگوریتم در حالت سریال برای بهتر شدن درک ماهیت الگوریتم و سپس آن را به صورت موازی طراحی کردیم.بعدا نتایج را با هم مقایسه می کنیم هر دو اجرای سریال و موازی به ما دیدی در مورد چگونگی عملکرد و کارایی ارائه میدهد.

Keywords:

الگوریتم رابین کار , بازیابی متن , الگوریتم تطبیق تک رشته ای , الگوریتم تطبیق چند رشته ای