Proiect Analiza Algoritmilor
Dacă "întoarcerea" nu este dificilă, atunci o metodă semnificativ mai rapidă de căutare pe şiruri poate fi dezvoltată parcurgând şablonul de la dreapta la stânga atunci când se încearcă potrivirea acestuia cu textul. Când căutăm şablonul considerat şi până acum 10100111 , dacă găsim potriviri ale caracterelor 8, 7, şi 6 dar nu şi 5, atunci putem imediat deplasa şablonul 7 poziţii la dreapta şi putem verifica al cincisprezecelea caracter, pentru că potrivirea parţială a găsit 111 , care poate apărea altundeva în şablon. Evident, şablonul de la sfârşit apare altundeva în general, deci avem nevoie de un tablou urmator ca în cazul algoritmului Knuth - Morris - Pratt.
O versiune "de la dreapta la stânga" a vectorului urmator pentru şablonul 10110101 este arătată în figura următoare: în acest caz, urmator[j] este numărul de caractere cu care şablonul poate fi deplasat spre dreapta, considerând că o nepotrivire într-o căutare de la dreapta la stânga a apărut la caracterul j din dreapta în şablon. Acesta este găsit ca mai înainte (cazul algoritmului Knuth - Morris - Pratt) deplasând o copie a şablonului peste ultimele j caractere ale acestuia de la stânga la dreapta, începând cu caracterul cel mai aproape de ultimul caracter al copiei aliniat cu ultimul caracter al şablonului şi terminând atunci când toate caracterele care se suprapun se potrivesc (având în vedere şi caracterul care a cauzat nepotrivirea). De exemplu, urmator [2] este 7 deoarece dacă se potrivesc ultimele 2 caractere iar o nepotrivire este detectată într-o scanare de la dreapta la stânga, atunci 001 a fost întâlnit în text; acesta nu apare în şablon cu excepţia cazului când 1 se aliniază cu primul caracter în şablon, deci ne putem deplasa cu 7 poziţii spre dreapta.
| j | urmator[j] | |
| 2 | 4 | 10110101 10110101 |
| 3 | 7 | 10110101 10110101 |
| 4 | 2 | 10110101 10110101 |
| 5 | 5 | 10110101 10110101 |
| 6 | 5 | 10110101 10110101 |
| 7 | 5 | 10110101 10110101 |
| 8 | 5 | 10110101 10110101 |
Se obţine un algoritm similar cu implementarea precedentă a algoritmului Knuth - Morris - Pratt. Nu îl vom detalia însă aici, pentru că diferă modul de deplasare peste caractere.
Ideea este de a decide care este următoarea acţiune de îndeplinit pe baza atât a caracterului care a provocat nepotrivirea cât şi a şablonului. Pasul de preprocesare constă în a decide pentru fiecare caracter care s-ar putea găsi în text ce am face dacă acest caracter ar provoca o nepotrivire. Cea mai simplă realizare pentru aceasta duce imediat la un program util.
Figura următoare arată această metodă pentru căutarea şablonului STING
în textul
Figura 3.3.1 Algoritmul Boyer - Moore folosind euristica caracterului nepotrivit
Începând de la dreapta la stânga, verificăm întâi caracterul G în şablon cu R (al cincilea caracter) în text. Nu numai că acestea nu se potrivesc, dar putem observa că R nu apare nicăieri în şablon, deci putem să ne deplasăm peste acest caracter. Următoarea comparaţie este făcută între G şi al cincilea caracter ce urmează după R (S în SEARCHING). De data aceasta putem deplasa şablonul spre dreapta până ce S -ul său se potriveşte cu S -ul din text. Apoi G este comparat cu C în SEARCHING care nu apare în şablon, deci acesta poate fi deplasat încă 5 poziţii spre dreapta. După încă 3 deplasări de câte 5 poziţii spre dreapta, ajungem la T în CONSISTING, moment în care aliniem şablonul astfel încât T -ul său se potrivească cu T -ul din text, şi găsim o potrivire completă. Această metodă ne-a condus la o primă potrivire cu un cost de numai 7 compariţii în text (şi încă 5 pentru a verifica potrivirea).
Acest algoritm (al "caracterului nepotrivit") este uşor de implementat. El doar îmbunătăţeşte scanarea şablonului prin algoritmul forţei brute de la dreapta la stânga prin iniţializarea unui vector deplasare , care spune, pentru fiecare caracter din alfabet cât de multe caractere vor fi sărite dacă acel caracter apare în text şi cauzează o nepotrivire. Trebuie să fie o intrare în vector pentru fiecare caracter care este posibil să apară în text: pentru simplitate, presupunem că avem o funcţie index care primeşte un caracter drept argument şi returnează 0 pentru blank-uri şi i pentru a i -a literă din alfabet. Presupunem că dispunem de o subrutină initDepl care iniţializează vectorul deplasare cu M pentru caractere care nu se află în şablon, şi apoi, pentru j de la 0 la M - 1 , atribuie lui deplasare[index(p[j])] valoarea M - j - 1 . Apoi implementarea este simplă:
01: CARACTER-NEPOTRIVIT(p, a)
|
În continuare prezentăm implementarea în limbajul C++ este:
01: int caracternepotrivit(char *p, char *a)
|
Dacă vectorul deplasare ar avea toate componentele 0 (niciodată nu este aşa), algoritmul ar corespunde unei versiuni de la dreapta la stânga a metodei forţei brute, deoarece i ← i + M - j stabileşte i la poziţia următoare în text, apoi j ← M - 1 pregăteşte indicele şablonului. Tabloul deplasare conduce la deplasarea şablonului în text exact cât este garantat, cel mai adesea M caractere odată (atunci când în text sunt întâlnite caractere care nu se află în şablon). Pentru şablonul STING , intrarea în deplasare pentru G este 0 , pentru N este 1 , pentru I este 2 , pentru T este 3 , pentru S este 4 , iar pentru celelalte caractere este 5 . Astfel, de exemplu, când un S este întâlnit într-o cşutare de la dreapta la stânga, indicele i este incrementat cu 4 astfel încât sfârşitul şablonului este aliniat 4 poziţii la dreapta lui S. Dacă ar fi existat mai multe caractere S în şablon, am fi dorit să-l folosim pe cel mai din dreapta, deci vectorul deplasare este construit de la stânga la dreapta.
Boyer şi Moore au sugerat combinarea celor două metode prezentate pentru căutare de la dreapta la stânga, alegând vectorul deplasare cel mai mare dintre cele două chemate.
Proprietatea 3.3.1: Algoritmul Boyer - Moore are complexitatea Θ(M + N), iar dacă
alfabetul nu este mic şi şablonul nu este lung, foloseşte aproximativ N / M paşi.
Liniaritatea în cel mai rău caz, se demonstrează în acelaşi mod în care se arată şi
pentru algoritmul Knuth - Morris - Pratt (algoritmul de mai sus, care implementează una dintre
cele două euristici Boyer - Moore, nu este liniar). Rezultatul pentru cazul mediu N / M
poate fi dovedit pentru diverse modele de şiruri aleatoare, dar acestea tind să nu fie realistice
şi vom sări peste detalii. Este adevărat că în multe situaţii practice, puţine
caractere ale alfabetului apar în şablon, deci fiecare comparaţie duce la sărirea a
M caractere, ceea ce duce la rezultatul enunţat.
Este evident că algoritmul "caracterului nepotrivit" nu va fi folositor pentru şiruri binare, deoarece sunt doar 2 posibilităţi pentru caractere care provoacă nepotriviri (şi acestea probabil că se află în şablon). Cu toate acestea, biţii pot fi grupaţi pentru a forma "caractere", care pot fi folosite exact ca mai sus. Dacă vom considera b biţi, vom avea nevoie de un tablou deplasare cu 2 b intrări. Valoarea lui b trebuie aleasă destul de mică astfel încât vectorul să nu fie prea lung, şi destul de mare astfel încât cele mai multe secţiuni de b biţi să nu fie în şablon. În particular, sunt M - b + 1 secţiuni de 8 biţi diferite în şablon, deci dorim ca M - b + 1 să fie semnificativ mai mic decât 2 b . De exemplu, dacă vom considera b aproximativ lg(4M), atunci tabloul deplasare va avea pentru mai mult de trei sferturi dintre elemente valoarea M. De asemenea, b trebuie să fie mai mic decât M / 2, din moment ce am putea pierde întreg şablonul dacă acesta ar fi împărţit între două secţiuni de b biţi.