Cautarea de siruri Boyer-Moore

Cautarea de siruri Boyer-Moore

Metoda ingenioasa de cautare KMP conduce la beneficii numai daca nepotrivirea dintre sir si model a fost precedata de o potrivire partiala de o anumita lungime.

Numai in acest caz deplasarea modelului se realizeaza peste mai mult de o pozitie.

Din pacate aceasta situatie in realitate este mai degraba exceptia decat regula; potrivirile apar mult mai rar ca si nepotrivirile.

In consecinta, beneficiile acestei metode sunt reduse in marea majoritate a cautarilor normale de texte.

Metoda de cautare inventata in 1975 de R.S. Boyer si J.S. Moore imbunatateste performanta atat pentru situatia cea mai defavorabila cat si in general.

Cautarea BM, dupa cum mai este numita, este bazata pe ideea neobisnuita de a incepe compararea caracterelor de la sfarsitul modelului si nu de la inceput.

Ca si in cazul metodei KMP, modelul este precompilat anterior intr-un tablou d.

Analiza cautarii Boyer-Moore

Autorii cautarii BM, au demonstrat proprietatea remarcabila ca in toate cazurile, cu exceptia unora special construite, numarul de comparatii este substantial mai redus decat n.

In cazul cel mai favorabil cand ultimul caracter al modelului nimereste intotdeauna in sir peste un caracter diferit de cele ale modelului, numarul de comparatii este n/m .

Autorii indica anumite directii de imbunatatire a performantelor algoritmului.

Una din ele este aceea de a combina strategia BM care realizeaza o deplasare substantiala in prezenta unei nepotriviri cu strategia KMP care permite o deplasare mai substantiala dupa detectia unei potriviri (partiale).

Aceasta metoda necesita doua tablouri precalculate: d₁ (tabloul specific cautarii BM) si d₂ (tabloul corespunzator cautarii KMP).

Toate acestea conduc la complicarea algoritmului si la cresterea regiei sale prin precompilarea tablourilor.            

De fapt in multe cazuri trebuie analizata oportunitatea implementarii unor extensii sofisticate care desi rezolva anumite situatii punctuale, pot avea drept consecinta deteriorarea performantelor de ansamblu prin cresterea excesiva a regiei algoritmului implicat.

• O definitie recursiva este acea definitie care se refera la un obiect care se defineste ca parte a propriei sale definiri.
• Desigur o definitie de genul 'o floare este o floare' care poate reprezenta in poezie un univers intreg, in stiinta in general si in matematica in special nu furnizeaza prea multe informatii despre floare.
• O caracteristica foarte importanta a recursivitatii este aceea de a preciza o definitie intr-un sens evolutiv, care evita circularitatea.
• Spre exemplu o definitie recursiva este urmatoarea: 'Un buchet de flori este fie (1) o floare, fie (2) o floare adaugata buchetului'
• Afirmatia (1) serveste ca si conditie initiala, indicand maniera de amorsare a definitiei
• Afirmatia (2) precizeaza definirea recursiva (evolutiva) propriu-zisa.
• Varianta iterativa a aceleasi definitii este 'Un buchet de flori consta fie dintr-o floare, fie din doua, fie din 3 flori, fie etc".
• Dupa cum se observa, definitia recursiva este simpla si eleganta dar oarecum indirecta, in schimb definitia iterativa este directa dar greoaie.

• Despre un obiect se spune ca este recursiv daca el consta sau este definit prin el insusi.
• Prin definitie orice obiect recursiv implica recursivitatea ca si proprietate intrinseca a obiectului in cauza.

Algoritmii recursivi sunt potriviti a fi utilizati atunci cand problema care trebuie rezolvata sau datele care trebuiesc prelucrate sunt definite in termeni recursivi.

Cu toate acestea, un astfel de mod de definire nu justifica intotdeauna faptul ca utilizarea unui algoritm recursiv reprezinta cea mai buna alegere.

Mai mult, utilizarea recursivitatii in anumite situatii nepotrivite, coroborata cu regia relativ ridicata a implementarii si executiei unor astfel de algoritmi, a generat in timp un curent de opinie potrivnic destul de vehement.

Cu toate acestea recursivitatea ramane o tehnica de programare fundamentala cu un domeniu de aplicabilitate bine delimitat.