Knut- Moris- Pratt algoritmlari va ularning dasturlari
![Matnda pattern mos kelmagan holatlardachi?
0-holatdan 1-holatga faqat A bo’lsagina o’tadi. Aks holda 0-holatda qoladi. Demak
tekshirilayotgan birinchi belgi B yoki C bo’lsa, birinchi holatda qoladi.
1-holatdan 2-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatida qoladi, sababi
pattern’ga ko’ra, biz uchun birinchi belgi A bo’lishi kerak. C bo’lsa, 0-holatga qaytadi – qidiruv
patt[0] dan boshlanadi.
2-holatdan 3-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
3-holatdan 4-holatga faqat B bo’lsagina o’tadi. Agar A bo’lsa, 1-holatiga qaytadi; C bo’lsa, 0-
holatga qaytadi.
4-holatdan 5-holatga faqat A bo’lsagina o’tadi. Agar B,C bo’lsa, 0-holatga qaytadi.
5-holatdan 6-holatga faqat C bo’lsagina o’tadi. Agar B bo’lsa 4-holatga qaytadi, sababi 5-
holatga ko’ra, qidiruvda patternning dastlabki 5 belgisi mos kelgan hisoblanadi, ya’ni
qidirilayotgan matnda ABABA allaqachon bor. Keyingi belgi C bo’lishi kerak edi, ammo B
chiqdi (ABABAB). Biz avvalgi mos kelgan harflarni bilar ekanmiz, qidiruvni 0-holatdan emas,
4-holatdan, AB ABAB holatidan davom ettiramiz. A chiqsa, 1-holatga qaytadi.
6-holatga kelganda qidiruv to’xtaydi, biz matn ichidan patternni topgan bo’lamiz.
Yuqoridagi shartlarni graph ko’rinishida ifodalasak:
Jadval ko’rinishida:](/data/documents/42834af9-3710-409f-8d9e-ab27db9abf01/page_6.png)
![AABACA ABABAC AA
6-holatga o’tadi.
Pattern topildi. Qidiruv tugaydi.
Holatlarning o’zgarishini graph va jadvalga qarab boshqatdan ko’rib chiqishingiz mumkin.
Pattern’dan DFAni yasash
Yuqoridagi jadval va graph’ni biz o’zimi ko’rib turib yasadik. Kodda qanday qilib berilgan
pattern’dan DFAni yasaymiz?
DFAni yasashda ikki xil holat bor:
Mos kelish . j-holatida, keyingi belgi c == pattern.charAt(j) bo’lsa, u holda j ni bittaga
oshiramiz.
Mos kelmaslik . j-holatida, keyingi belgi c != pattern.charAt(j) bo’lsa, u holda ohirgi j-1 belgilar
pattern[1..j-1] ichida bo’ladi.
Knuth-Morris-Pratt algoritmini kodda ifodalash](/data/documents/42834af9-3710-409f-8d9e-ab27db9abf01/page_8.png)
![BBBBBBBBBB
A BBBB
A BBBB
A BBBB
A BBBB
A BBBB
A BBBB
Masalan, yuqoridagi holatda ishlash vaqti O((N-M) * M) ga teng.
Rabin-Karp algoritmi
Bizda quyidagi matn bor bo’lsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE
1. patterndagi 0 dan M-1 gacha belgilar bo’yicha hash soni generatsiya qilinadi. Bunda
M – patterndagi belgilar soni.
2. har bir [i..N-1] sikl ichida matndagi i dan M + i – 1 gacha belgilar bo’yicha hash soni
generatsiya qilinadi. Bunda N – matndagi belgilar soni
3. Agar pattern hash va matn substring hash bir-biriga teng bo’lsa, pattern matn
ichidan topilgan hisoblanadi.
Hash sonini generatsiya qilishning eng tezkor, oson usullardan biri – pattern’ning har bir
belgisi kodini olib, ularni birlashtirish va uni biror katta tub songa bo’lib, qoldig’ini qoldirish
kerak. Javascript da bu ish quyidagicha bajariladi:
const primeNumber = 997 // tub son
const pattern = "NEEDLE" // qidiriladigan so'z
const hash = pattern.split('').map(char => char.charCodeAt()).join('') %
primeNumber
// pattern uchun hash soni 769
Demak bizda patternning hash soni generatsiya qilindi. Endi uni matndagi har bir i dan M + i –
1 gacha substring’lardan hash son generatsiya qilib uni pattern’ning hash soniga solishtirib
chiqiladi. Substring uchun ham, pattern uchun ham bir xil usulda hash generatsiya qilinadi.
FINDINAHAYSTACKNEEDLEINA
FINDIN // 5 != 769](/data/documents/42834af9-3710-409f-8d9e-ab27db9abf01/page_13.png)
![INDINA // 877 != 769
NDINAH // 105 != 769
DINAHA // 259 != 769
INAHAY // 541 != 769
NAHAYS // 414 != 769
AHAYST // 271 != 769
HAYSTA // 963 != 769
AYSTAC // 805 != 769
YSTACK // 535 != 769
STACKN // 507 != 769
TACKNE // 178 != 769
ACKNEE // 98 != 769
CKNEED // 615 != 769
KNEEDL // 317 != 769
NEEDLE // 769 == 769
Juda oddiy va mohirona usul!
Yuqoridagi hash generatsiya qilish usuli split() va join() metodlari ishlatilgani sababli sekinroq
ishlashi mumkin. Shuning uchun biz hash generatsiya qilishni sinalgan usul – Horner
metodi yordamida amalga oshiramiz. Umumiy formula quyidagicha:
x
i = ( t
i * R M-1
+ t
i+1 * R M-2
+ … + t
i+M-1 * R 0
) % Q
Bu yerda:
x
i – matndagi [i..M + i – 1] substring uchun hash soni.
t
i – str.charCodeAt(i) – matn/pattern belgisining ASCII jadvalidagi raqami.
R – radix soni. ASCII uchun 128 yoki 256.
M – patterndagi belgilar soni.
Q – tub son.
Hash funksiya kodi:
function hornerHash (str, M) {](/data/documents/42834af9-3710-409f-8d9e-ab27db9abf01/page_14.png)
Mavzu: Knut- Moris- Pratt algoritmlari va ularning dasturlari Reja: I. Kirish. II. Algoritmning asosiy xossalari 1. Knuth-Morris-Pratt algoritmi 2. Boyer-Moore algoritmi 3. Rabin-Karp algoritmi
KIRISH Avvalo algoritm tushunchasi IX asrlarda yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy nomi bilan uzviy bog’liqligini tushuntirish lozim. Algoritm so’zi al-Xorazmiyning arifmetikaga bag’ishlangan asarining dastlabki betidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan. Shundan so’ng al-Xorazmiyning sanoq sistemasini takomillashtirishga qo’shgan hissasi, uning asarlari algoritm tushunchasining kiritilishiga sabab bo’lganligi ta’kidlab o’tiladi. Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan ko’rsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda to’liq tizimi tushuniladi. Algoritm tushunchasi aniq shaklda XX-asr boshlarida D. Gilbert, K. Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A. Markov singari olimlarning asarlari tufayli shakllandi. Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy bo'luvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular o'zlarining rasmiy, izchil aksiomalar tizimi doirasida yechib bo'lmaydigan muammolar mavjudligini ko'rsatdi. Algoritm tushunchasi Algoritm – berilgan natijaga erishish uchun qilinishi kerak bo lgan aniq ko rsatmalar ketma-ketligi. Algoritm keng ma noda faqat ʻ ʻ kompyuterga oid atama bo lmay, balki unda berilgan ko rsatmalarni bajara ʼ oluvchi har qanday narsaga oiddir. Algoritm — ma lum bir turga oid ʻ ʻ masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi ʼ haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. Algoritm so’zi Al – Xorazmiy nomining lotincha talaffuzidan kelib chiqqan bo’lib. Muxammad Muso Al-Xorazmiyning X asrda yaratilgan qo’llanmasida keltirilgan o’nlik sanoq sistemasida arifmetik amallarni bajarish qoidalari soddaligi tufayli yevropada ham o’nlik sanoq sistemasi qo’llanishiga turtki bo’ldi. Bu qoidalar tarjimasida xar bir qoida “ Al-Xorazmiy aytadiki ” deb boshlangan va bora-bora talaffuz tufayli algoritm tarzida ifodalanib kelgan. Hozirgi paytda algoritm sifatida biror masalani ishlash yoki biror ishni bajarish uchun qilinishi kerak bo’lgan tartiblangan chekli sondagi aniq bir qiymatli ko’rsatmalar ketma-ketligi tushiniladi. Algoritm tushunchasi keng ma’noda tahlil qilish mumkin. Masalan, biror manzildan boshqa manzilga borish uchun shahar transportidan foydalanib qanday borish mumkin, degan savolga biz ma’lum algoritm tavsiya qilishimiz mumkin. Pazandalik kitobida, masalan, palovni pishirish qoidasi keltiriladi. Bu ham o’ziga xos algoritm hisoblashlar ishlanadigan masala algoritmini biz hisoblash algoritmi deymiz. Biz asosan
hisoblash algoritmlari haqida so’z yuritamiz. Algoritmlarga xos bo’lgan belgi va talablarni sanab o’tamiz. Har qanday algoritm quyidagi asosiy xususiyatlarga ega bo’lishi kerak: Algoritm so`zi barchamizga ma`lum bo`lganidek, vatandoshimiz Muhammad ibn Muso al-Xorazmiyning ismini yevropacha talaffuzidan kelib chiqqan. Demak, hozirda keng foydalanilayotgan algoritmlashning asosi bizning Vatanimizdan boshlangan. Maktab informatika kursidan ma`lumki, algoritm bu – ma`lum masalani hal qilish uchun bajarish kerak bo`lgan amallar ketma-ketligi. O`sha mashhur choy damlash algoritmidan chekingan holda hayotiy misol keltiramiz. Hayotda eng ko`p bo`ladigan holatimiz bu uyqu. Ko`pchilik rejim bilan uxlaydi , ya`ni uxlashga ma`lum bir vaqtni belgilagan. Misol uchun siz uxlashga yotish uchun 22:00ni tanladingiz. Har safar soatga qaraganingizda uxlash vaqti bo`lgan yoki bo`lmaganini tekshirasiz. Miyangizda esa quyidagi jarayon bo`ladi: Bu oddiy uyquga yotish algoritmi edi. Hayotda o`zimiz bilmagan holatda algoritmlardan foydalanamiz. Miyamiz juda tez ishlagani sabab qadamlar ketma- ketligi haqida o`ylab ko`rmaymiz. Endi maqolamizning asosiy qismi, dasturlashda algoritmlashga o`tamiz. Dasturlashda algoritm bu – masalani yechish uchun bajarilishi kerak bo`lgan amallar ketma-ketligini kodga o`girilgan varianti. Bunda masalani yechish uchun miyamizda kechayotgan jarayonni kompyuter tushunadigan qilib yozish talab etiladi. Algoritmlashning asosi matematika hisoblanadi. Bunda fikrlash muhim rol o`ynaydi. So`zimni quyidagicha isbot qilaman. Dasturlash sanoatida gigant korporatsiya hisoblangan Microsoftning asoschisi Bill Geytsning shunday so`zlari dasturchilar orasidda mashhur:"Qo`shish va ayirishni biladigan har qanday inson dasturchi bo`la oladi". Bu so`zlarni mag`zini chaqish uchun sizlarni boshlang`ich sinflarga qaytishga taklif etaman. Har birimiz boshlang`ich sinflarda qo`shish va ayirish amallarini o`rgangan edik. Ko`pchilik buni barmoqlari orqali bajargan. Chunki barmoqlar 10ta va raqamlarni qo`shish va ayirishda qo`l keladi. Keyinchalik matematik evolutsiyamiz sonlar bilan qo`shish va ayirish amallarini bajarish bosqichiga yetib keladi. Bu rivojlanish jarayoni yangi amallar bilan boyidi va endi bir xil raqamlarni bir necha marta qo`shishni osonlashtirish uchun ko`paytirish jadvalini o`rgandik. E`tibor bering, ko`paytirish algoritmi qo`shish algoritmining asosiga qurilgan. Rivojlanishimiz davom etib, endilikda qoldiqli bo`lish va shu kabi murakkabroq amallarga o`tamiz. Maktabni bitirish vaqtida esa juda murakkab amallarni ham bajara oladigan darajada bo`lamiz. Ana ko`rdingizmi, hamma murakkab amallarning asosi qo`shish va ayirishdan boshlanadi. U yog`i esa fikrlash doirangiz kengligiga bog`liq. Demak, dasturlashdagi asosiy masalalar matematik fikrlashga bog`liq.
Algoritmning asosiy xossalari Knuth-Morris-Pratt algoritmi Matn ichida qidiruv uchun brute-force yondashuvining kamchiligi – pattern’dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boshqatdan boshlashi kerak. Shuning uchun worst case O(N*M) bo’lib ketadi. Misol uchun, bizda matn A B A A A A B A A A A A A A A A bo’lsin. Pattern esa BAAAAAAAAA . Qidiruv jarayoni: E’tibor bergan bo’lsangiz, ikkinchi siklda patternning 6-belgisi mos kelmay qoldi. Demak biz text’dagi biz ko’rib o’tgan ohirgi 6 belgi BAAAAB ekanini bilamiz. Nima uchun qidiruvni yana boshqatdan boshlashimiz kerak? 3-6 sikllarni tushirib qoldirib, 7-sikldan davom ettirishning imkoni bormi? Knuth-MorrisPratt (KMP) algoritmi mana shu muammoga yechim sifatida kelib, qidiruvni boshqatdan boshlamaslikning imkonini beradi. U Deterministic Finite Automaton g’oyasiga asoslangan. Deterministic Finite Automaton Deterministic finite automaton (DFA) – kompyuter nazariyasida (computer science) abstrakt string qidiruvchi mashina. U holatlarning aniq bir to’plami bo’lib, berilgan (yoki tekshirilayotgan) input qiymatiga qarab, bir holatdan ikkinchi holatga o’tishi mumkin. U asil holatdan boshlanib, ohirgi holatga yetganda tugaydi. Oson misol bilan tushuntirishga harakat qilaman. Bizda quyidagi ro’yhat bor:
Biz ular ichidan A dan boshlanadiganlarini topishimiz kerak. Shart asosida DFAni yasaymiz. Shartga ko’ra, stringning birinchi belgisi A bo’lishi kerak, shunda keyingi belgilarni tekshirishni davom ettiradi. Aks holda dastlabki holatda qoladi. Ro’yhatdan stringlarni tekshirib chiqamiz: A . 0 holatdan 1 holatga o’tdi. Qidiruv yakunlandi. 1 holatga o’tgani uchun string topilgan hisoblanadi. AA . A: 0 holatdan 1 holatga o’tdi. A: 1 holatda istalgan belgi bo’lishi mumkin bo’lgani bois, 1 holatda qoldi. BAC . B: 0 holatda qoldi, sababi 1 holatga faqat birinchi belgi A bo’lgandagina o’tadi. DBCA . D: 0 holatda qoldi, sababi 1 holatga faqat birinchi belgi A bo’lgandagina o’tadi. Yana bir misol. ABABAC pattern uchun DFA yasashimiz kerak. DFA holatlari 0 dan 6gacha bo’ladi. Ideal holatda, ABABAC uchun 6-holatga yetib kela oladi. Jadval ko’rinishida: