الگوریتم تطابق رشته‌ها

الگوریتم‌های تطابق رشته‌ای ، که گاهی الگوریتم‌های جسیتجوی رشته‌ای گقته می‌شوند، دسته مهمی از الگوریتم‌های رشته‌ای هستند که سعی می‌کنند محل رخداد یک یا چند رشته (الگو) در یک رشته بزرگتر (یا متن) را پیدا کنند.
را مجموعه الفبای محدودی فرض کنید.معمولا، هم الگو و هم متن مورد نظر، ترکیبی از عناصر می‌باشند.
می‌تواند یک الفبای انسانی معمولی باشد (مثلا، حروف A تا Z در زبان انگلیسی).
در کاربردهای دیگر ممکن است از الفبای دودویی ({( = {0,1) یا الفبای DNA در بیوانفورماتیک استفاده شود.
به‌طور خاص، این که رشته چگونه رمز شده‌است می‌تواند روی الگوریتم ملموس تطابق، تاثیر گذار باشد. مخصوصا اگر رمز نگاری طولی متغیر مورد استفاده قرار گیرد، به کندی می‌توان کاراکتر N ام را پیدا کرد.
این می‌تواند به‌طور محسوسی الگوریتم‌های جستجوی پیشرفته‌تر را کند، کند.
یک راه حل این است که به دنبال دنباله‌ای از واحدهای رمز بگردیم، اما این روش ممکن است باعث ایجاد مطابقت‌های اشتباه گردد.
اگر رمز نگاری به گونه‌ای خاص طراحی شده باشد، از این مشکل جلوگیری می‌شود.
تقسیم بندی کلی
الگوریتم‌های مختلف را می‌توان بر اساس تعداد الگوهایی که استفاده می‌کنند دسته بندی کرد.
الگوریتم‌های تک الگویی
الگوریتم جستجوی رشته نیو
الگوریتم جستجوی رشته رابین-کارپ
جستجو بر پایه ماشین‌های خودکار محدود حالته
الگوریتم جستحوی رشته‌ای Boyer-MooreKnuth-Morris-Pratt
لگوریتمBitap
الگوریتم‌هایی با مجموعه الگوهای متناهی
الگوریتم Aho-Corasick
الگوریتمCommentz-Walter
الگوریتم جستجوی رشته رابین-کارپ
الگوریتم‌های با تعداد الگوهای نامتناهی
طبیعتا در این حالت تعداد الگوها غیر قابل شمارش است.
آن‌ها را معمولا با یک عبارت عادی نمایش می‌دهند.
دیگر تقسیم بندی‌ها
تقسیم بندی‌های دیگری نیز امکان پذیر است. یکی از رایج‌ترین آن‌ها پیش پردازش را به عنوان معیار در نظر می‌گیرد.
+طبقه‌بندی الگوریتم‌های تطابق رشته‌ها
متن پیش پردازش نشده
متن پیش پردازش شده
الگوهای پیش پردازش نشده
الگوریتم‌های ابتدایی
روش‌های نمایه سازی
الگوهای پیش پردازش شده
موتورهای جستجوی ساخته شده
روش‌های دستینه سازی
جستجوی رشته‌ای naive
آسان‌ترین و ناکارامدترین راه برای آنکه ببینیم کجا یک رشته در رشته‌ای دیگر تکرار شده، آن است که تمام مکان‌های ممکن را یکی یکی بررسی کنیم.
در حالت نورمال، برای هر مکان اشتباه، فقط کافی است یک یا دو کاراکتر را چک کنیم پس در حالت متوسط، این
O(n + m) مرحله طول می‌کشد، که n طول متن وm اندازه کلمه مورد جستجو(کلید) است;
اما در بدترین حالت، جستجوی یک رشته مثل "aaaab" در یک رشته مثل "aaaaaaaaab", O(nm)مرحله طول می‌کشد.
جستجو بر اساس ماشین‌های خودکار محدود حالته
right
در این روش، با ساختن یکماشین محدود قطعی(deterministic) که رشته‌هایی را که حاوی رشته مطلوب مورد جستجو هستند، تشخیص می‌دهد.
ساخت آن‌ها هزینه بر است اما بسیار سربع هستند. مثلا DFA که در سمت راست نشان داده شده‌است کلمه "MOMMY" را تشخیص می‌دهد.این شیوه در عمل برای جستجوی عبارات معمولی دلخواه، عمومیت داده می‌شود.
نمونه‌هایی دیگر
Knuth-Morris-Pratt یک ماشین محدود قطعی می‌سازد که پسوندی از رشته مورد نظر را جستجو کند
کلید را از آخر در متن جستجو می‌کند تا بتواند در اکثر مواقع به انداره طول کلید در متن پرش کند. Baeza-Yates نگه می‌دارد که آیا کاراکترهای j قبلی پیشوندی از رشته مورد جستجو هستند یا نه، از این رو تطبیق پذیر با جستجوی رشته‌ای fuzzy می‌باشند. الگوریتم bitap کاربردی از روش Baeza-Yates
است.
روش‌های نمایه‌ای
الگوریتم‌های سریع‌تر بر پایه پیش پردازش متن کار می‌کنند.
پس از ساخت نمایه زیر رشته، مثلا درخت پسوند یاآرایه پسوند، رخدادهای یک الگو خیلی سریع یافت می‌شوند. به عنوان مثال، یک درخت پیشوند می‌تواند در زمان (Theta(m ساخته شود، و تمام رخدادهای یک الگو می‌توانند در زمان (O(m+z یافت شوند (اگر اندازه مجموعه الفبا را یک ثابت در نظر بگیریم).
انواع دیگر
بعضی از روش‌های جستجو، مثلا جستجویtrigram، به منظور محاسبه یک نمره شباهت بین دو رشته ساخته شده‌اند و نه صرفا برای نشخیص
"تطبیق با عدم تطبیق".
این نوع را گاهی جسنجوی کرکی یا fuzzy می‌گویند.
پیوندها
الگوریتم
مراجع
R. S. Boyer and J. S. Moore, , Carom. ACM 20, (10), 262–272(1977).
توماس اچ کورمن, Charles E. Leiserson, رونالد ریوست, and کلیفورد استین. مقدمه‌ای بر الگوریتم‌ها, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 32: String Matching, pp.906–932.
پیوندهای خارجی
– Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
— Animation in Java, Detailed description and C implementation of many algorithms.