Knut-Morris-Prat algoritmi

Аннотация

В данной статье рассматривается алгоритм Кнута-Морриса-Пратта (КМП), являющийся эффективным методом поиска подстроки в тексте. В отличие от традиционных алгоритмов, КМП минимизирует количество ненужных сравнений за счёт использования заранее вычисленной префикс-функции, обеспечивая временную сложность O(n). Алгоритм широко используется в обработке текстов, биоинформатике, поисковых системах и системах обнаружения плагиата. В статье подробно изложен принцип работы алгоритма, этапы построения префикс-функции и приведены практические примеры на языке программирования C#. Ключевые слова: Алгоритм Кнута-Морриса-Пратта, поиск шаблонов, поиск подстроки, префикс-функция, сложность алгоритма, программирование на C#, обработка текста Matn ichida ma’lum bir namunani yoki so‘zni qidirish masalasi kompyuter fanining eng asosiy va keng tarqalgan muammolaridan biridir. Har qanday matnli ma’lumotlar bazasida, hujjatlarni qayta ishlashda, veb-saytlarda izlash tizimlarida yoki dasturlash tillarida kod qidirishda samarali va tezkor qidiruv algoritmlari talab qilinadi. Oddiy, ya’ni naive algoritm har bir pozitsiyadan boshlab satrning har bir belgisi bilan namunani taqqoslash orqali ishlaydi, ammo bu yondashuv katta hajmdagi matnlarda sekin va samarasiz bo‘lib qoladi. Ayniqsa, uzun matn va qidirilayotgan namunada ko‘p takrorlanuvchi belgilar mavjud bo‘lsa, oddiy yondashuv ko‘plab keraksiz taqqoslashlarga sabab bo‘ladi. Shu nuqtai nazardan, samarali va optimallashtirilgan algoritmlarga ehtiyoj tug‘iladi. Knut-Morris-Pratt (KMP) algoritmi aynan shunday masalani hal qilish uchun ishlab chiqilgan. U prefiks-funksiyasi asosida ishlaydi va keraksiz taqqoslashlarni minimallashtirish orqali qidiruv jarayonini sezilarli darajada tezlashtiradi. Bu algoritmning samaradorligi va ishonchliligi ko‘plab amaliy sohalarda, jumladan, matn tahlili, biologik ketma-ketliklarni o‘rganish, plagiat aniqlash va real https://scientific-jl.org/obr Выпуск журнала №-70 167 Часть–4_ Мая –2025 ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ 2181- 3187 vaqt tizimlarida keng qo‘llanilishiga olib keldi. Ushbu maqolada KMP algoritmining nazariy asoslari, ishlash printsiplari va uning amaliy ahamiyati batafsil yoritiladi, shuningdek, boshqa matn qidiruv algoritmlari bilan solishtirish orqali uning o‘ziga xos afzalliklari ko‘rsatib beriladi. Maqolaning maqsadi o‘quvchilarga KMP algoritmini chuqur tushunish va uni samarali qo‘llash bo‘yicha bilim berishdir. Knut-Morris-Pratt (KMP) algoritmi satrlar ichida namunani (pattern) samarali izlash uchun ishlab chiqilgan algoritmdir. Uning asosiy afzalligi — har bir belgini faqat bir marta ko‘rib chiqishi, ya’ni ortiqcha taqqoslashlarni oldini olishi bilan bog‘liq. KMP algoritmi ikki asosiy bosqichdan iborat: birinchi bosqichda qidirilayotgan namunaga tegishli maxsus yordamchi massiv — prefiks-funksiyasi (yoki failure function) quriladi. Ushbu prefiks-funksiyada har bir indeksda o‘sha pozitsiyagacha bo‘lgan substring ichida qanday qilib o‘zi bilan bir xil boshlanadigan va tugaydigan eng uzun substring mavjudligi haqida ma’lumot saqlanadi. Bu yordamchi massiv kelajakdagi qidiruvda qaysi belgidan davom etishni aniqlashda muhim rol o‘ynaydi. Algoritmning ikkinchi bosqichi — to‘g‘ridan-to‘g‘ri matn ichida namunani izlash jarayoni hisoblanadi. Bu bosqichda matn va namunadagi belgilar navbatma-navbat taqqoslanadi. Belgilar bir-biriga mos kelgan holatda ikkala indeks oldinga siljitiladi. Agar mos kelmaslik aniqlansa, KMP algoritmi prefiks-funksiyadagi qiymatlardan foydalanib, namunadagi indeksni shunday o‘zgartiradiki, u ilgari tekshirib chiqilgan mos kelgan belgilarni qayta ko‘rib chiqmaydi. Bu yondashuv natijasida har bir belgining maksimal bir marta tahlil qilinishi ta’minlanadi, bu esa umumiy ishlash tezligini O(n + m) — ya’ni matn uzunligi n va namunalar uzunligi m ga bog‘liq bo‘lgan chiziqli murakkablikda saqlab qoladi. KMP algoritmining ishlash mantig‘i zamirida optimallik tamoyili yotadi. Oddiy string qidiruv algoritmlarida biror mos kelmaslik aniqlangach, butun namunani qaytadan taqqoslashga to‘g‘ri keladi. KMP esa shu bosqichgacha o‘zaro mos kelgan belgilarni tahlil qilganligi tufayli, mos kelmaslik holida to‘liq qaytish emas, balki faqat zarur pozitsiyadan davom etishni ta’minlaydi. Bu esa algoritmning samaradorligini keskin oshiradi. KMP algoritmi nafaqat nazariy jihatdan, balki amaliyotda — masalan, https://scientific-jl.org/obr Выпуск журнала №-70 168 Часть–4_ Мая –2025 ОБРАЗОВАНИЕ НАУКА И ИННОВАЦИОННЫЕ ИДЕИ В МИРЕ 2181- 3187 matnli fayllarda ma’lumot izlash, plagiat aniqlash, kodni indekslash kabi vazifalarda ham keng qo‘llaniladi. Knut-Morris-Pratt (KMP) algoritmining amaliy qo‘llanilishi juda keng va u turli sohalarda samarali ishlatiladi. Eng avvalo, matnni tahlil qilish bilan bog‘liq vazifalarda — masalan, fayllarda yoki hujjatlarda aniq bir ifodani izlashda KMP algoritmi ancha yuqori samaradorlikka ega. Katta hajmdagi matnlar ustida ishlaydigan dasturlar, masalan, fayl qidiruv tizimlari, kod indeksatsiyasi yoki o