Mavzu : matnda qidiruv algoritimini tahlil qilish

Mavzu : MATNDA QIDIRUV ALGORITIMINI TAHLIL QILISH
( KNUT, MORRIS, PRATT, BOYER VA MUR, KOLUS )


Reja:

1. 
   Matn ichida qidiruv. Knuth-Morris-Pratt algoritmi
   

2. Matn ichida qidiruv. Boyer-Moore algoritmi

3. Har ikkala algoritmni o’zaro tahlil qilish

1. 
   Matn ichida qidiruv. 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: