WALKER

Dasturchi, frilanser, gik va introvert

by Sherzod Shermukhamedov

Matn içida qidiruv. Boyer-Moore algoritmi

boyer-moore-algorithm-1-638

Avvalgi mavzuda ötganimiz - Knuth-Morris-Pratt algoritmi yordamida biz matn içida qidiruvni O(N + M) vaqt içida bajara olamiz. Navbatdagi algoritm - Boyer-Moore algoritmi bizga O(N) ni kafolatlay olmasada, amaliyotda KMPdan samaraliroq işlaydi. Örganişga ham osonroq ;)

Boyer-Moore'ning taklifiga köra:

  • pattern'dagi belgilarni öngdan çapga (pattern ohiridan boşiga) qarab körib çiqiş;
  • pattern'da yöq bölgan belgi topilganda maksimum M miqdordagi belgilarni tekşirmay taşlab ketiş. Bu yerda M - pattern'dagi belgilar soni

Bizda quyidagi matn bor bölsin: FINDINAHAYSTACKNEEDLEINA
Pattern: NEEDLE

qidiruvni pattern'ning ohirgi harfidan boşlaymiz.

FINDINAHAYSTACKNEEDLEINA NEEDLE

Dastlabki tekşirilayotgan belgi - E matnning dastlabki M-elementiga teng emas (N != E). Ammo N pattern içida bor. Keyingi tekşiriş uçun pointerni N qilib belgilaymiz.

FINDINAHAYSTACKNEEDLEINA NEEDLE

S != E, şu bilan birga S pattern içida yöq. Demak bizga S va undan oldingi belgilarning qiziği yöq. Keyingi tekşiriş uçun pointerni S dan keyingi elementga beramiz (bu yerda -T).

FINDINAHAYSTACKNEEDLEINA NEEDLE

E == E lekin keyingi element N != L. Patternda N bor. Keyingi tekşiriş uçun pointerni mana şu Nga beramiz.

FINDINAHAYSTACKNEEDLEINA NEEDLE

Pattern matn içidan topildi.

Misoldagi tuşirib qoldirişlar turini tahlil qiladigan bölsak, bizda pattern'dagi belgining mos kelmasligi böyiça (character mismatç) bir neça holatlar mavjud.

1. Mos kelmagan belgi pattern içida yöq. Bu holda pointer mos kelmagan belgidan keyinga qöyiladi. Masalan

matn: ......TLE...... patt: NEEDLE

D != T, pointer T dan keyingi element - L ga beriladi.

matn: .......TLE...... patt: NEEDLE

2a. Mos kelmagan belgi pattern içida bor.

matn: ......NLE...... patt: NEEDLE

Bu holda agar belgi pattern'ning birinçi belgisi bölsa, pointer şu belgiga qöyiladi.

matn: ......NLE...... patt: NEEDLE

2b. Mos kelmagan belgi pattern içida bor, lekin u patternning birinçi elementiga mos kelmaydi.

matn: ......ELE...... patt: NEEDLE

matn: ......ELE...... patt: NEEDLE

Biz E pattern'dagi qaysi Ega mos kelişini bilmaymiz. Şuning uçun pointerni bittaga oşiramiz xolos.

Umuman, algoritmdagi eng muhim jihat - qança belgini tekşirmasdan taşlab ketişni aniqlab oliş kerak böladi. Buning uçun pattern'dagi belgilar asosida ikki ölçamli array yasab olinadi. Unda alfavitdagi har bir harfning pattern'dagi örni belgilanadi.
-1 - pattern'da yöq degani.

NEEDLE
c012345right[c]
A-1-1-1-1-1-1-1-1
B-1-1-1-1-1-1-1-1
C-1-1-1-1-1-1-1-1
D-1-1-1-13333
E-1-1122255
...-1
L-1-1-1-1-1444
M-1-1-1-1-1-1-1-1
N-10000000
...-1

Boyer-Moore'ning tuşirib qoldirişni hisoblaş jadvali

Biz bu jadvalni kodga ögiradigan bölsak:

Töliq kod

Algoritmning işlaş vaqti ~ O(N/M) ga teng. Bu degani pattern qança uzun bölsa, algoritmning işlaş vaqti qisqarib boraveradi.

Worst case. Şuni ham qayd etiş kerakki, işlaş vaqti ba'zi holatlarda O(N*M) bölib ketişi mumkin:

BBBBBBBBBB ABBBB ABBBB ABBBB ABBBB ABBBB ABBBB

Masalan, yuqoridagi holatda işlaş vaqti O((N-M) * M) ga teng.