Blogo simbolio taisyklė

Blogo simbolio taisyklė (arba Boyer-Moore algoritmas) – teksto paieškos ilgoje eilutėje algoritmas.

Algoritmas ieško palyginti trumpos eilutės kitoje (paprastai daug ilgesnėje) iš anksto nežinomoje eilutėje. Tuo jis skiriasi nuo priesagų medžius naudojančių algoritmų, kuriems ilgąja eilutę reikia žinoti iš anksto – medžiui sukurti.

Klasikinis Boyer-Moore algoritmas remiasi trimis paprastomis taisyklėmis:

1. Trumpoji eilutė (kurios ieškoma) prieš paiešką analizuojama, sudarant lentelę. Kiekvienai eilutės padėčiai įsimenama, kiek toli į kairę nuo jos eilutėje yra kiekviena abėcėlei priklausanti raidė. Specialiu kodu pažymimi atvejai, kai tokios raidės į kairę nuo šios padėties ieškomoje eilutėje nėra.
2. Nors pati paieška vyksta iš kairės į dešinę, simboliai lyginami iš dešines į kairę („atbulai“).
3. Nustačius kad duotojoje padėtyje ieškomos eilutės nėra, pirmajame žingsnyje atliktos analizės rezultai panaudojami nustatyti, kur pradėti ieškoti iš naujo:

• a) Jei nesutampančio ilgosios eilutės simbolio kairiojoje trumposios eilutės dalyje nėra, lyginimo rėmels patraukiamas tiek, kad šis simbolis į jį nebepatektų.
• b) Jei šis simbolis trumpojoje eilutėje labiau į kairę yra, rėmelis patraukiamas tiek, kad šieji du simboliai atsidurtų vienas virš kito.

Pavyzdys

Blogo simbolio taisyklės taikymas ieškant žodžio LIULA frazėje LŪGNĖS LAPAI LIULA EŽERE.

• a) Kažkuriame etape lyginant pastebima, kad U nesutampa su tarpu. Kadangi tarpo ieškomame žodyje nėra, rėmelis patraukiamas paliekant tarpą kairėje.
• b) Patraukus nustatoma jog A nelygus I, tačiau I ieškomoje eilutėje sutinkamas už dviejų simbolių į kairę nuo lyginamos padėties. Rėmelis patraukiamas tris žingsius (vienu daugiau, kad simboliai atsidurtų vienas virš kito).
• c) Ir vėl iš karto paaiškėja, jog I nelygus A. Pagal tą pačią informaciją patraukus rėmelį dar tris žingsnius…
• d) …ieškoma eilutė randama.

Taigi skirtingai nuo naiviojo algoritmo, kuris paieškos rėmelį kiekvieną kartą patraukia tik per vieną simbolį, Boyer-Moore algoritmas paprastai rėmelį patraukia gerokai daugiau ir todėl yra pastebimai greitesnis. Jis gerai tinka ieškant teksto fragmentų žmonių kalboje arba baltymų sekose ir sunkiau pritaikomas DNR sekoms, kur abėcėle apribota keturiais simboliais.

Šaltiniai

1. Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.