موضوع مقاله: الگوریتم جستجوی رشته | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # الگوریتم جستجوی رشته | مقدمه: الگوریتم‌های جستجوی رشته (و یا تطبیق رشته‌ها) به رده‌ی مهمی از الگوریتم‌های موجود در رابطه با رشته‌ها اطلاق می‌شود. | ## بخش 1: الگوریتم جستجوی رشته | در این مثال، رشته‌ها از کنار هم گذاشتن تعدادی کاراکتر متعلق به یک مجموعه‌ی متناهی به نام الفبا ساخته می‌شوند. می‌تواند حروف الفبای معمولی (از A تا Z)، الفبای دودویی یا الفبای DNA باشد که بسته به محل و کاربرد مسئله، تعیین می‌شود. شرایط انتخاب الگوریتم در هر حالت از محیط اجرای الگوریتم و شرایط مسئله، باید این شرایط را به خوبی بررسی کرد و بهترین الگوریتم را برای پیاده‌سازی و استفاده برگزید. برای گرفتن بهترین کارایی در هر یک از این شرایط، باید الگوریتم مشخصی را انتخاب کرد. همچنین در نوعی از این مسئله، رشته‌های Pattern به صورت یک عبارت منظم داده می‌شوند، و باید جایگاه تمام زیررشته‌هایی که با آن عبارت منظم مطابق هستند به عنوان خروجی برگردانده‌شود. | ## بخش 2: الگوریتم جستجوی رشته | طبقه بندی کلی الگوریتم‌های جستجوی رشته به صورت کلی به سه دسته‌ی زیر تقسیم می‌شوند: الگوریتم‌های جستجوی تک الگو در جدول زیر، چند الگوریتم معروف ذکر شده و از نظر مرتبه‌ی زمانی و حافظه با هم مقایسه شده‌اند. ( طول الگو (Pattern)، طول رشته متن (Text) و برابر با تعداد حروف الفبا است) نام الگوریتم زمان پیش‌پردازش زمان تطبیق حافظه مورد نیاز الگوریتم جستجوی ساده‌لوحانه بدون پیش‌پردازش بدون حافظه جانبی الگوریتم رابین-کارپ در حالت میانگین در بدترین حالت الگوریتم کنوث-موریس-پرت (KMP) الگوریتم بویر-مور در بهترین حالتدر بدترین حالت الگوریتم‌های جست‌و‌جوی تعدادی متناهی الگو الگوریتم آهو-کوراسیک (تعمیم‌یافته‌ی الگوریتم KMP) الگوریتم تطابق رشته‌ Commentz-Walter (تعمیم‌یافته‌ی الگوریتم Boyer-Moore) الگوریتم رابین‌کارپ برای جست‌وجوی چندالگویی الگوریتم‌های جست‌و‌جوی تعدادی نامتناهی الگو در این نوع از الگوریتم‌ها، استراتژی‌ها و ایده‌های متنوعی برای تطابق الگوهای ورودی (که به شکل عبارت منظم یا زبان منظم داده می‌شوند) به کار گرفته می‌شود. یعنی یک اشاره‌گر را به عنوان ابتدای الگو، روی متن جلو می‌بریم و بررسی می‌کنیم که آیا این اشاره‌گر، می‌تواند ابتدای یک تکرار از الگو در متن باشد یا خیر. برای این‌کار، کاراکترهای بعد از اشاره‌گر را دانه‌به‌دانه با الگو مقایسه می‌کنیم؛ در صورت عدم انطباق یکی از آن کاراکتر‌ها، مشخص می‌شود که اشاره‌گر در مکان فعلی نمی‌تواند نمایان‌گر یک تکرار برای رشته باشد، پس اشاره‌گر را یک واحد به جلو می‌بریم. و در صورتی تا انتهای مقایسه، هیچ تناقضی وجود نداشت، به این معنی است که اشاره‌گر به یک تکرار از الگو در متن اشاره می‌کند. | ## بخش 3: الگوریتم جستجوی رشته | مثلاً State نماینده‌ی پیشوند ، با یال به State نماینده‌ی پیشوند می‌رود، اگر و تنها اگر بزرگ‌ترین پیشوندی از الگو باشد که برای پسوند است. با خواندن کاراکتر از رشته متن و حرکت روی این DFA، هر بار که به State پذیرش برسیم، یک تکرار از الگو را در متن پیدا کرده‌ایم. همچنین با تعمیم این روش، می‌توان الگوریتمی را برای جست‌وجوی عبارت‌های منظم در متن طراحی کرد. البته هزینه ساخت چنین پذیرنده‌ای زیاد است (در صورت استفاده از ایده‌ی الگوریتم KMP، می‌توان با زمان این پذیرنده را ساخت) اما استفاده از آن سریع است. DFA شکل زیر برای تشخیص دادن واژه‌ی MOMMY استفاده شده‌است: روش‌های مبتنی بر اندیس این الگوریتم‌های جستجو متن را پیش‌پردازش می‌کنند؛ بعد از ساختن زیررشته اندیسیSubstring Index (برای مثال درخت پسوندی یا آرایه پسوندی)، تعداد بارهایی که الگوی مورد جستجو در متن اتفاق افتاده‌است، به سرعت مشخص می‌شود؛ برای مثال یک درخت پسوندی را می‌توان در ساخت و همه‌ی z رخ‌داد الگوی مورد نظر در متن را می‌توان در پیدا کرد. | ## جمع‌بندی | این کار به سادگی با استفاده از یک بار جست‌و‌جوی عمق اول روی درخت پسوندی انجام می‌شود.