WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Matn içida qidiruv. Knuth-Morris-Pratt algoritmi

maxresdefault (1)

Matn içida qidiruv uçun brute-force yondaşuvining kamçiligi - pattern'dagi belgilardan biri qidiruvda mos kelmay qolganda, qidiruvni boşqatdan boşlaşi kerak. Şuning uçun worst case O(N*M) bölib ketadi. Misol uçun, bizda matn A B A A A A B A A A A A A A A A bölsin. Pattern esa BAAAAAAAAA.

Qidiruv jarayoni:

A B A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A B A A A A A A A A A

E'tibor bergan bölsangiz, ikkinçi siklda patternning 6-belgisi mos kelmay qoldi. Demak biz text'dagi biz körib ötgan ohirgi 6 belgi BAAAAB ekanini bilamiz. Nima uçun qidiruvni yana boşqatdan boşlaşimiz kerak? 3-6 sikllarni tuşirib qoldirib, 7-sikldan davom ettirişning imkoni bormi?

Knuth-MorrisPratt (KMP) algoritmi mana şu muammoga yeçim sifatida kelib, qidiruvni boşqatdan boşlamaslikning imkonini beradi. U Deterministic Finite Automaton ğoyasiga asoslangan.

Deterministic Finite Automaton

Deterministic finite automaton (DFA) - kompyuter nazariyasida (computer science) abstrakt string qidiruvçi maşina. U holatlarning aniq bir töplami bölib, berilgan (yoki tekşirilayotgan) input qiymatiga qarab, bir holatdan ikkinçi holatga ötişi mumkin. U asil holatdan boşlanib, ohirgi holatga yetganda tugaydi.

Oson misol bilan tuşuntirişga harakat qilaman. Bizda quyidagi röyhat bor:

[ 'A', 'AA', 'BAC', 'DBCA', 'AFAB', 'AWAVABBBB', 'ABABAB', 'GAAAA', 'FRBABA', 'AJECB' ]

Biz ular içidan A dan boşlanadiganlarini topişimiz kerak.

Şart asosida DFAni yasaymiz. Şartga köra, stringning birinçi belgisi A bölişi kerak, şunda keyingi belgilarni tekşirişni davom ettiradi. Aks holda dastlabki holatda qoladi.

Röyhatdan stringlarni tekşirib çiqamiz:

A. 0 holatdan 1 holatga ötdi. Qidiruv yakunlandi. 1 holatga ötgani uçun string topilgan hisoblanadi.
AA. A: 0 holatdan 1 holatga ötdi. A: 1 holatda istalgan belgi bölişi mumkin bölgani bois, 1 holatda qoldi.
BAC. B: 0 holatda qoldi, sababi 1 holatga faqat birinçi belgi A bölgandagina ötadi.
DBCA. D: 0 holatda qoldi, sababi 1 holatga faqat birinçi belgi A bölgandagina ötadi.

Yana bir misol. ABABAC pattern uçun DFA yasaşimiz kerak.

DFA holatlari 0 dan 6gaça böladi. Ideal holatda, ABABAC uçun 6-holatga yetib kela oladi.

Jadval körinişida:

j012345
pat.charAt(J)ABABAC
A135
B24
C6

Matnda pattern mos kelmagan holatlardaçi?

0-holatdan 1-holatga faqat A bölsagina ötadi. Aks holda 0-holatda qoladi. Demak tekşirilayotgan birinçi belgi B yoki C bölsa, birinçi holatda qoladi.

1-holatdan 2-holatga faqat B bölsagina ötadi. Agar A bölsa, 1-holatida qoladi, sababi pattern'ga köra, biz uçun birinçi belgi A bölişi kerak. C bölsa, 0-holatga qaytadi - qidiruv patt[0] dan boşlanadi.

2-holatdan 3-holatga faqat A bölsagina ötadi. Agar B,C bölsa, 0-holatga qaytadi.

3-holatdan 4-holatga faqat B bölsagina ötadi. Agar A bölsa, 1-holatiga qaytadi; C bölsa, 0-holatga qaytadi.

4-holatdan 5-holatga faqat A bölsagina ötadi. Agar B,C bölsa, 0-holatga qaytadi.

5-holatdan 6-holatga faqat C bölsagina ötadi. Agar B bölsa 4-holatga qaytadi, sababi 5-holatga köra, qidiruvda patternning dastlabki 5 belgisi mos kelgan hisoblanadi, ya'ni qidirilayotgan matnda ABABA allaqaçon bor. Keyingi belgi C bölişi kerak edi, ammo B çiqdi (ABABAB). Biz avvalgi mos kelgan harflarni bilar ekanmiz, qidiruvni 0-holatdan emas, 4-holatdan, ABABAB holatidan davom ettiramiz. A çiqsa, 1-holatga qaytadi.

6-holatga kelganda qidiruv töxtaydi, biz matn içidan patternni topgan bölamiz.

Yuqoridagi şartlarni graph körinişida ifodalasak:

Jadval körinişida:

j012345
pat.charAt(J)ABABAC
A113151
B020404
C000006

Bizda quyidagi matn mavjud: AABACAABABACAA
Pattern esa yuqorida körib ötganimiz: ABABAC

Matn içidan patternni topişimiz kerak bölsin. Qidiruvni 0-holatdan boşlaymiz.

AABACAABABACAA

1-holatga ötadi.

AABACAABABACAA

**1-holatda qoladi.

AABACAABABACAA

**2-holatga ötadi.

AABACAABABACAA

**3-holatga ötadi.

AABACAABABACAA

**0-holatga qaytadi.

AABACAABABACAA

**1-holatga ötadi.

AABACAABABACAA

**1-holatda qoladi.

AABACAABABACAA

**2-holatga ötadi.

AABACAABABACAA

**3-holatga ötadi.

AABACAABABACAA

**4-holatga ötadi.

AABACAABABACAA

**5-holatga ötadi.

AABACAABABACAA

**6-holatga ötadi.

Pattern topildi. Qidiruv tugaydi.

Holatlarning özgarişini graph va jadvalga qarab boşqatdan körib çiqişingiz mumkin.

Pattern'dan DFAni yasaş

Yuqoridagi jadval va graph'ni biz özimi körib turib yasadik. Kodda qanday qilib berilgan pattern'dan DFAni yasaymiz?

DFAni yasaşda ikki xil holat bor:

Mos keliş. j-holatida, keyingi belgi c == pattern.charAt(j) bölsa, u holda j ni bittaga oşiramiz.

Mos kelmaslik. j-holatida, keyingi belgi c != pattern.charAt(j) bölsa, u holda ohirgi j-1 belgilar pattern[1..j-1] içida böladi.

Knuth-Morris-Pratt algoritmini kodda ifodalaş