Algoritmul Boyer-Moore-Horspool

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).

Descrierea algoritmului

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 abbad

Mută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|-i

Un exemplu despre cum funcționează algoritmul

Modelul dorit este „abbad” (tabelul pentru acest model este construit mai sus).

abeccacbadbabbad abbad

Impunem 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 abbad

Trei 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 abbad

Ultimul 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 abbad

Opțiuni

Algoritmul lui Sandi

Pentru caracterul stop, luăm caracterul care urmează acul .

Algoritmul lui Wright

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.

Avantaje

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.

Dezavantaje

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.

Literatură

• Niklaus Wirth Algoritmi și structuri de date. — M.: Dialectul Nevski, 2006. S. 352. ISBN 5-7940-0065-1

Note

1. ↑ Algoritmul Horspool . Preluat la 12 august 2012. Arhivat din original la 29 august 2012. (nedefinit)

Link -uri

• Un exemplu de implementare a algoritmului Horspool

Siruri de caractere
Măsuri de similitudine a șirurilor	Distanța de la Damerau la Loewenstein Distanța Levenshtein Distanța de Hamming Asemănări Jaro-Winkler
Căutare subșir	Algoritmul Boyer-Moore Algoritmul Boyer-Moore-Horspool Algoritmul Knuth-Morris-Pratt Algoritmul Rabin-Karp funcția de prefix Funcția Z Algoritmul Aho - Korasik
palindromuri	arbore palindrom Algoritmul lui Manaker
Alinierea secvenței	Algoritmul Needleman-Wunsha Algoritmul Smith-Waterman
Structuri de sufix	Matrice de sufixe Sufix automat arbore de sufix arbore de prefix
Alte	analizare Potrivire de model Cea mai mare succesiune comună Cel mai mare subșir comun