Algoritmul Boyer-Moore-Horspool este un algoritm pentru găsirea unui subșir într-un șir , o versiune simplificată a algoritmului Boyer-Moore . ABMX funcționează mai bine decât algoritmul Boyer-Moore pe texte aleatorii, scorul mediu este de la până la un caracter al textului [1] . În plus, euristica sufixului de potrivire intensivă din punct de vedere computațional este omisă.
Cu toate acestea, estimarea ( în cel mai rău caz pe șabloane neperiodice) pentru ABMX este | ac |·| carul de fan | (în loc de 3 | carul de fân | pentru Boyer-Moore).
Algoritmul este o modificare a algoritmului Boyer-Moore . Ideea algoritmului este aceasta.
1. Scanare de la stânga la dreapta, comparație în modul „cutie neagră”. Ca și în algoritmul primitiv, începutul textului și șablonul sunt combinate, se face o comparație folosind procedura obișnuită „ comparare secțiuni de memorie ” . Dacă toate caracterele modelului se potriveau cu caracterele suprapuse ale șirului, atunci subșirul a fost găsit și căutarea s-a încheiat.
Dacă vreun caracter al modelului nu se potrivește cu caracterul corespunzător al șirului, modelul este deplasat cu câteva caractere la dreapta. Acești „puțini” sunt aleși după o astfel de euristică.
2. Schimbat euristic simbol stop. Luăm caracterul textului care a apărut deasupra ultimului caracter al modelului (indiferent de locul unde s-a întâmplat nepotrivirea!). Este „b” în imagine.
↓ caracter de oprire Text abadb * * * * model abbad Următoarea verificare abbadMutăm șablonul astfel încât litera „b” a șablonului să fie sub simbolul stop. Acest lucru este implementat folosind un tabel de compensare: pentru fiecare caracter al alfabetului, stocăm deplasarea maximă posibilă care nu omite un caracter de oprire. Adică (la numerotarea liniilor cu 1): shift ( c ) = | needle |−lastpos( c , needle [1..| needle |−1]) , unde lastpos este ultima apariție a unui caracter din șir, needle [ a .. b ] este operația sub șir.
Pentru modelul „abbad”, tabelul arată așa.
Simbol | A | b | (alte) |
---|---|---|---|
Părtinire | unu | 2 | 5 |
Pentru simbolurile care nu sunt incluse în șablon, valoarea offset este setată egală cu lungimea șablonului - 5. Ultimul simbol al șablonului nu este luat în considerare la calcularea tabelului de offset (este plin de bucle ).
Este mai convenabil să calculați tabelul parcurgând toate simbolurile șablonului:
pentru c=MIN_CHAR..MAX_CHAR shift[c] = |ac| pentru i=1..|ac|-1 deplasare[ac[i]] = |ac|-iModelul dorit este „abbad” (tabelul pentru acest model este construit mai sus).
abeccacbadbabbad abbadImpunem un eșantion pe linie. Ultimul caracter al șirului sursă „c” nu este conținut în model. Deplasați modelul la dreapta cu 5 poziții în funcție de valoarea offset-ului pentru „c”:
abeccacbadbabbad abbadTrei caractere ale modelului s-au potrivit, dar al patrulea nu. Deplasați modelul la dreapta cu 5 poziții în funcție de valoarea offset-ului pentru „d”:
abeccacbadbabbad abbadUltimul caracter al șirului „a” nu se potrivește cu caracterul modelului. Mutați modelul la dreapta cu 1 în funcție de valoarea offset pentru „a” și obțineți apariția dorită a modelului:
abeccacbadbabbad abbadPentru caracterul stop, luăm caracterul care urmează acul .
Un algoritm empiric optimizat pentru textele în limba engleză . Compară ultimul caracter, apoi primul, apoi mijlocul, apoi toate celelalte; în caz de nepotrivire, schimbarea Horspool.
Foarte rapid în medie[ specificați ] . Ușor de implementat. Utilizează funcția standard pentru compararea zonelor de memorie, de regulă, optimizată la nivel de asamblare pentru un anumit procesor.
Ca și alți algoritmi ai familiei Boyer-Moore, nu este modificat pentru căutarea aproximativă, căutarea simultană pentru mai multe șiruri.
Regresia asupra datelor „proaste” are loc ceva mai des decât în algoritmul Boyer-Moore. Cu cât caracterele din textul sursă sunt mai diverse, cu atât ABMX se comportă mai bine.
Siruri de caractere | |
---|---|
Măsuri de similitudine a șirurilor | |
Căutare subșir | |
palindromuri | |
Alinierea secvenței | |
Structuri de sufix | |
Alte |