[For Beginners] درک الگوریتم KMP با مقایسه با Brute-Force

الگوریتم Knuth-Morris-Pratt (KMP)، یک الگوریتم جستجوی رشته ای شناخته شده، روشی است که برای انجام کارآمد تطبیق الگو با به حداقل رساندن مقایسه های غیر ضروری طراحی شده است. برای اینکه هم به مبتدیان و هم به خودم کمک کنم تا درک خود را عمیق تر کنیم، ایده های اساسی و عملکرد الگوریتم KMP را توضیح خواهم داد.

در این مقاله به الگوی رشته ای که باید جستجو شود اشاره می کنیم پرس و جو و رشته ای که در آن می خواهیم پرس و جو را به عنوان متن.

محدودیت های روش Brute-Force

وقتی صحبت از الگوریتم های جستجوی رشته ای می شود، ساده ترین شکل آن است روش brute-force (به روش ساده لوح نیز گفته می شود). کمتر کسی این را رد می کند. در اینجا، بیایید یک متن طولانی را در نظر بگیریم n و یک پرس و جو از طول m. روش brute-force پرس و جو را با کاراکتر به کاراکتر متن مقایسه می کند، از ابتدا شروع می شود و تا زمانی که مطابقت پیدا شود ادامه می یابد.

با این حال، این رویکرد دارای پیچیدگی زمانی در بدترین حالت است O(nm)، آن را برای رشته های بلند ناکارآمد می کند. به عنوان مثال، در مثال زیر، روش brute-force نیاز دارد 20 مقایسه:

متن: ABABAABABAB

پرس و جو: ABABAB

از سوی دیگر، الگوریتم KMP می تواند این را به فقط کاهش دهد 14 مقایسه.

کلید الگوریتم: جدول شکست

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

جدول شکست دو ویژگی اصلی دارد:

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

جدول شکست فقط با استفاده از رشته پرس و جو ساخته می شود. با تجزیه و تحلیل زیر رشته های پرس و جو، از یک کاراکتر به بالا m کاراکترها، ثبت می کند که چه مقدار از پرس و جو از نظر پیشوندها و پسوندها مطابقت دارد. برای روشن شدن مطلب به مثالی نگاه می کنیم.

پرس و جو: ABABAB

استفاده از جدول شکست: یک مثال عملی

بیایید ببینیم که چگونه از جدول شکست در هنگام تطبیق الگو با الگوریتم KMP استفاده می شود. ما از همان استفاده خواهیم کرد text و query همانطور که قبلا ذکر شد.

در اولین تلاش، الگوریتم با موفقیت تا کاراکتر 5 مطابقت دارد. با این حال، شخصیت نهایی منجر به عدم تطابق می شود. اکنون، به جای شروع مجدد مقایسه از کاراکتر بعدی در متن، الگوریتم KMP از جدول شکست استفاده می کند تا تصمیم بگیرد که آیا از موقعیت فعلی ادامه دهد یا کمی به عقب برگردد.

در اینجا نحوه کار آن آمده است:

1. الگوریتم مشخص می کند که آخرین کاراکتر منطبق در آن بوده است موقعیت 5 (A). در جدول شکست، این مربوط به شاخص 4.
2. جدول شکست این را نشان می دهد FailureTable[4] = A، یک همپوشانی بالقوه را نشان می دهد. را تغییر مقدار برای این موقعیت است 3.
3. این بدان معنی است که مقایسه بعدی می تواند از سر گرفته شود text[5] و pattern[3]، از مقایسه های غیر ضروری صرف نظر می کنیم.

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

با تکرار این فرآیند، الگوریتم پس از مجموع یک تطابق را تعیین می کند 14 مقایسه. از منظر محاسباتی، ساخت جدول شکست دارای پیچیدگی است O(m)، و فرآیند جستجو دارای پیچیدگی است O(n). بنابراین، بدترین حالت پیچیدگی زمانی الگوریتم KMP است O(n + m).

یک نکته کلیدی که باید به خاطر بسپارید این است که الگوریتم KMP هرگز از نمایه سمت متن عقب نشینی نمی کند. در نظر گرفتن این ویژگی می تواند به جلوگیری از سردرگمی در هنگام اجرای الگوریتم کمک کند.

در نگاه اول، الگوریتم KMP ممکن است پیچیده به نظر برسد، اما ایده اصلی آن ساده است: برای کاهش مقایسه های غیر ضروری. با درک و استفاده از جدول شکست، جستجوی رشته کارآمد قابل دستیابی است.

امیدوارم این مقاله به شما در درک اصول اولیه الگوریتم KMP کمک کرده باشد.

مراجع