Algoritmo di Boyer-Moore

In informatica, l'algoritmo di Boyer-Moore è un algoritmo di confronto fra stringhe efficiente che rappresenta il principale punto di riferimento nel suo ambiente.[1] È stato sviluppato da Robert S. Boyer e J Strother Moore nel 1977.[2] L'algoritmo preprocessa la stringa da cercare (il pattern), ma non la stringa esaminata (il testo). È quindi particolarmente adatto per applicazioni in cui il pattern è molto più breve del testo o persiste su più ricerche. L'algoritmo di Boyer–Moore utilizza informazioni raccolte durante la fase di preprocessamento per poter saltare sezioni del testo, risultando in un fattore costante più basso rispetto a molti altri algoritmi su stringhe. In generale, l'algoritmo è eseguito più velocemente con l'aumentare della lunghezza del pattern. La caratteristica fondamentale dell'algoritmo è il confronto in coda del pattern piuttosto che in testa, e la possibilità di muoversi lungo il testo saltando interi gruppi di caratteri piuttosto che verificare ogni singolo carattere presente nel testo.

Descrizione

Definizioni

A	N	P	A	N	M	A	N	-
P	A	N	-	-	-	-	-	-
-	P	A	N	-	-	-	-	-
-	-	P	A	N	-	-	-	-
-	-	-	P	A	N	-	-	-
-	-	-	-	P	A	N	-	-
-	-	-	-	-	P	A	N	-

Allineamento del pattern PAN al testo ANPANMAN, da k=3 a k=8. Si ha una corrispondenza per k=5.

• ${\displaystyle S[i]}$ indica il carattere in posizione ${\displaystyle i}$ in una stringa ${\displaystyle S}$, partendo da 1.
• ${\displaystyle S[i..j]}$ indica una sottostringa di una stringa ${\displaystyle S}$ che inizia in posizione ${\displaystyle i}$ e finisce in posizione ${\displaystyle j}$, estremi inclusi.
• Un prefisso di ${\displaystyle S}$ è una sottostringa ${\displaystyle S[1..i]}$ per qualche ${\displaystyle i}$ appartenente all'insieme ${\displaystyle [1,n]}$, dove ${\displaystyle n}$ è la lunghezza di ${\displaystyle S}$.
• Un suffisso di ${\displaystyle S}$ è una sottostringa ${\displaystyle S[i..n]}$ per qualche ${\displaystyle i}$ appartenente all'insieme ${\displaystyle [1,n]}$, dove ${\displaystyle n}$ è la lunghezza di ${\displaystyle S}$.
• La stringa da cercare viene chiamata pattern si indica con il simbolo ${\displaystyle P}$.
• La stringa in cui si effettua la ricerca viene chiamata testo e si indica con il simbolo ${\displaystyle T}$.
• La lunghezza di ${\displaystyle P}$ è ${\displaystyle n}$.
• La lunghezza di ${\displaystyle T}$ è ${\displaystyle m}$.
• Un allineamento di ${\displaystyle P}$ in ${\displaystyle T}$ è un indice ${\displaystyle k}$ in ${\displaystyle T}$ tale che l'ultimo carattere di ${\displaystyle P}$ è allineato con l'indice ${\displaystyle k}$ di ${\displaystyle T}$.
• Una corrispondenza o occorrenza di ${\displaystyle P}$ si verifica per un allineamento se ${\displaystyle P}$ è uguale a ${\displaystyle T[(k-n+1)..k]}$.

Caratteristiche

L'algoritmo di Boyer–Moore cerca occorrenze di ${\displaystyle P}$ in ${\displaystyle T}$ eseguendo un confronto diretto dei caratteri per diversi allineamenti. Invece di utilizzare un metodo forza bruta per la ricerca di tutti gli allineamenti (che sono in numero ${\displaystyle m-n+1}$), Boyer–Moore sfrutta le informazioni raccolte preprocessando ${\displaystyle P}$ per saltare più allineamenti possibile.

Prima dell'introduzione di tale algoritmo, il tipico metodo per cercare qualcosa all'interno di un testo era esaminare ogni carattere del testo con il carattere iniziale del pattern. Una volta trovato un riscontro si procedeva con un confronto tra i successivi caratteri del testo con il resto del pattern. Se non si verificava un'occorrenza si continuava a controllare il testo carattere per carattere nel tentativo di ottenere un altro riscontro. In questo modo bisognava esaminare quasi ogni carattere del testo. L'intuizione fondamentale in questo algoritmo è che se si confronta la fine del pattern con il testo allora possono essere compiuti dei salti all'interno del testo piuttosto che confrontare ogni singolo carattere. Il motivo è che allineando il pattern al testo, l'ultimo carattere del pattern viene confrontato col carattere nel testo. Se i caratteri non corrispondono non c'è bisogno di effettuare confronti con i caratteri precedenti. Se il carattere nel testo non corrisponde ad alcun carattere del pattern, allora il prossimo carattere del testo da confrontare si trova a n caratteri di distanza lungo il testo, dove n è la lunghezza del pattern. Se il carattere nel testo è presente nel pattern, allora viene compiuto uno spostamento parziale lungo il testo per allineare i caratteri corrispondenti, dopodiché viene ripetuto l'intero processo. Lo scorrimento a salti lungo il testo per effettuare confronti piuttosto che controllare ogni singolo carattere riduce il numero di confronti da compiere, che è la chiave per l'aumento dell'efficienza dell'algoritmo.

Più formalmente, l'algoritmo incomincia con un allineamento ${\displaystyle k=n}$, cioè l'inizio di ${\displaystyle P}$ corrisponde all'inizio di ${\displaystyle T}$. I caratteri in ${\displaystyle P}$ e ${\displaystyle T}$ vengono confrontati a partire dalla posizione ${\displaystyle n}$ in ${\displaystyle P}$ e ${\displaystyle k}$ in ${\displaystyle T}$, e spostandosi all'indietro: le stringhe vengono verificate dalla fine di ${\displaystyle P}$ all'inizio di ${\displaystyle P}$. Il confronto continua finché non viene raggiunto l'inizio di ${\displaystyle P}$ (significa che si è verificata un'occorrenza) o si ha un mismatch che genera uno spostamento a destra dell'allineamento del massimo valore consentito da alcune regole. I confronti vengono nuovamente eseguiti col nuovo allineamento, e il processo si ripete finché l'allineamento non viene allineato oltre la fine di ${\displaystyle T}$, che significa che non verranno trovate altre corrispondenze.

Le regole di spostamento sono implementate come ricerche su tabelle in tempo costante, utilizzando tabelle generate nel preprocessamento di ${\displaystyle P}$.

Regole di spostamento

Uno spostamento viene calcolato applicando entrambe le seguenti regole: la regola del "carattere errato" e la regola del "buon suffisso". L'attuale offset di spostamento è il massimo degli spostamenti calcolati da queste regole.

Regola del carattere errato

Descrizione

-	-	-	-	X	-	-	K	-	-	-
A	N	P	A	N	M	A	N	A	M	-
-	N	N	A	A	M	A	N	-	-	-
-	-	-	N	N	A	A	M	A	N	-

Dimostrazione della regola del carattere errato con il pattern NNAAMAN.

La regola del carattere errato prende in considerazione il carattere in ${\displaystyle T}$ per cui il processo di confronto è fallito (ipotizzando che tale fallimento si sia verificato). Viene trovata la successiva occorrenza di tale carattere in ${\displaystyle P}$ verso sinistra, e viene proposto uno spostamento tale che porti quella occorrenza in linea con la relativa occorrenza in ${\displaystyle T}$. Se il carattere in ${\displaystyle T}$ che ha causato il mismatch non presenta occorrenze in ${\displaystyle P}$ verso sinistra, viene allora suggerito uno spostamento che porti interamente ${\displaystyle P}$ oltre la posizione in cui il confronto era fallito.

Preprocessamento

I metodi variano riguardo l'esatta forma che dovrebbe assumere la tabella per la regola del carattere errato, ma una semplice soluzione per una ricerca a tempo costante è la seguente: si crea una tabella bidimensionale che viene indicizzata prima con l'indice del carattere ${\displaystyle c}$ nell'alfabeto e poi con l'indice ${\displaystyle i}$ nel pattern. Questa ricerca restituirà l'occorrenza di ${\displaystyle c}$ in ${\displaystyle P}$ con il successivo più alto indice ${\displaystyle j<i}$ oppure ${\displaystyle -1}$ se non esiste tale occorrenza. Lo spostamento proposto sarà allora ${\displaystyle i-j}$, con ${\displaystyle O(1)}$ tempo di ricerca e ${\displaystyle O(kn)}$ spazio, assumendo un alfabeto finito di dimensione k.

Regola del buon suffisso

Descrizione

-

-

-

-

X

-

-

K

-

-

-

-

-

M

A

N

P

A

N

A

M

A

N

A

P

-

A

N

A

M

P

N

A

M

-

-

-

-

-

-

-

-

-

A

N

A

M

P

N

A

M

-

Dimostrazione della regola del buon suffisso con il pattern ANAMPNAM.

La regola del buon suffisso è decisamente più complessa sia come concetto che come implementazione rispetto alla regola del cattivo carattere. È il motivo per cui i confronti avvengono alla fine del pattern e non all'inizio, ed è formalmente indicato così:[3]

Si supponga che, per un certo allineamento di ${\displaystyle P}$ e ${\displaystyle T}$, una sottostringa ${\displaystyle t}$ di ${\displaystyle T}$ corrisponda a un suffisso di ${\displaystyle P}$, ma si verifichi un mismatch al successivo confronto verso sinistra. Quindi si trovi, se esiste, la copia più a destra ${\displaystyle t}$ di ${\displaystyle t}$ in ${\displaystyle P}$ tale che ${\displaystyle t}$ non è un suffisso di ${\displaystyle P}$ e il carattere a sinistra di ${\displaystyle t}$ in ${\displaystyle P}$ è diverso dal carattere a sinistra di ${\displaystyle t}$ in ${\displaystyle P}$. Si sposti ${\displaystyle P}$ verso destra così che la sottostringa ${\displaystyle t}$ in ${\displaystyle P}$ si allinei con la sottostringa ${\displaystyle t}$ in ${\displaystyle T}$. Se ${\displaystyle t}$ non esiste, allora si sposti l'estremità sinistra di ${\displaystyle P}$ oltre l'estremo sinistro di ${\displaystyle t}$ in ${\displaystyle T}$. Se non è possibile nessuno di questi spostamenti, allora si sposti ${\displaystyle P}$ di ${\displaystyle n}$ posizioni verso destra. Se viene trovata un'occorrenza di ${\displaystyle P}$, si sposti ${\displaystyle P}$ del minor numero di posti possibile cosicché un corretto prefisso del pattern ${\displaystyle P}$ spostato corrisponda a un suffisso dell'occorrenza di ${\displaystyle P}$ in ${\displaystyle T}$. Se tale spostamento non è possibile, si sposti ${\displaystyle P}$ di ${\displaystyle n}$ posizioni, che significa spostare ${\displaystyle P}$ oltre ${\displaystyle t}$.

Preprocessamento

La regola del buon suffisso richiede due tabelle: una da usare nel caso generale, e un'altra da usare o quando il caso generale non restituisce risultati utili o avviene una corrispondenza. Indichiamo queste tabelle rispettivamente con ${\displaystyle L}$ e ${\displaystyle H}$, e le definiamo come segue:[3]

Per ogni ${\displaystyle i}$, ${\displaystyle L[i]}$ è la posizione più grande a meno di ${\displaystyle n}$ tale che la stringa ${\displaystyle P[i..n]}$ corrisponda a un suffisso di ${\displaystyle P[1..L[i]]}$ e tale che il carattere precedente tale suffisso sia diverso da ${\displaystyle P[i1]}$. ${\displaystyle L[i]}$ vale zero se non esiste una posizione che soddisfi la condizione.

${\displaystyle H[i]}$ denoti la lunghezza del più grande suffisso di ${\displaystyle P[i..n]}$ che sia anche prefisso di ${\displaystyle P}$, se ne esiste uno. Se non ne esistono, ${\displaystyle H[i]}$ vale zero.

Entrambe le tabelle sono costruibili in tempo ${\displaystyle O(n)}$ e utilizzano spazio ${\displaystyle O(n)}$. Lo spostamento di allineamento per l’indice ${\displaystyle i}$ in ${\displaystyle P}$ è dato da ${\displaystyle n-L[i]}$ oppure ${\displaystyle n-H[i]}$. ${\displaystyle H}$ dovrebbe essere usato soltanto se ${\displaystyle L[i]}$ è zero o se si è verificata una corrispondenza.

Regola di Galil

Una semplice ma importante ottimizzazione del Boyer–Moore fu avanzata da Galil nel 1979.[4] In contrasto con lo spostamento, la regola di Galil si occupa di accelerare i confronti effettivamente compiuti per ogni allineamento saltando quelle sezioni che si sa che corrisponderanno. Supponiamo che per un allineamento ${\displaystyle k_{1}}$, ${\displaystyle P}$ venga confrontato con ${\displaystyle T}$ fino al carattere ${\displaystyle c}$ di ${\displaystyle T}$. Allora se ${\displaystyle P}$ viene spostato in un ${\displaystyle k_{2}}$ tale che la sua estremità sinistra sia compresa tra ${\displaystyle c}$ e ${\displaystyle k_{1}}$, nella prossima fase di confronto un prefisso di ${\displaystyle P}$ deve corrispondere alla sottostringa ${\displaystyle T[(k_{2}-n)..k_{1}]}$. Così se i confronti arrivano fino alla posizione ${\displaystyle k_{1}}$ di ${\displaystyle T}$, un'occorrenza di ${\displaystyle P}$ può essere individuata senza effettuare espressamente confronti dopo ${\displaystyle k_{1}}$. Oltre ad aumentare l'efficienza del Boyer–Moore, la regola di Galil è necessaria per dimostrare l'esecuzione a tempo lineare nel caso peggiore.

Prestazioni

L'algoritmo di Boyer–Moore per com'è stato presentato nel documento originale ha nel caso peggiore un tempo di esecuzione ${\displaystyle O(n+m)}$ solo se il pattern non appare all'interno del testo. Questo venne dimostrato per la prima volta da Knuth, Morris, e Pratt nel 1977,[5] seguiti da Guibas e Odlyzko nel 1980[6] con un upper bound di ${\displaystyle 5m}$ di confronti nel caso peggiore. Richard Cole riuscì a fornire una dimostrazione con un upper bound di ${\displaystyle 3m}$ di confronti nel caso peggiore nel 1991.[7]

Quando il pattern è presente all'interno del testo, il tempo di esecuzione dell'algoritmo originale è ${\displaystyle O(nm)}$ nel caso peggiore. Questo si nota facilmente quando sia il pattern che il testo consistono unicamente dello stesso carattere ripetuto. Tuttavia, l'inclusione della regola di Galil risulta in tempo di esecuzione lineare in tutti i casi.

Note

1. Hume e Sunday, Fast String Searching, in Software—Practice and Experience, vol. 21, n. 11, November 1991, pp. 1221–1248.
2. Robert S. Boyer e J Strother Moore, A Fast String Searching Algorithm., in Comm. ACM, vol. 20, n. 10, New York, NY, USA, Association for Computing Machinery, October 1977, pp. 762–772, DOI:10.1145/359842.359859, ISSN 0001-0782 (WC · ACNP).
3. Dan Gusfield, Chapter 2 - Exact Matching: Classical Comparison-Based Methods, in Algorithms on Strings, Trees, and Sequences, 1ª ed., Cambridge University Press, 1999 [1997], pp. 19–21, ISBN 0-521-58519-8.
4. Z. Galil, On improving the worst case running time of the Boyer-Moore string matching algorithm, in Comm. ACM, vol. 22, n. 9, New York, NY, USA, Association for Computing Machinery, September 1979, pp. 505–508, DOI:10.1145/359146.359148, ISSN 0001-0782 (WC · ACNP).
5. Donald Knuth, James H. Morris e Vaughan Pratt, Fast pattern matching in strings, in SIAM Journal on Computing, vol. 6, n. 2, 1977, pp. 323–350, DOI:10.1137/0206024.
6. Odlyzko Guibas e Andrew Odlyzko, A new proof of the linearity of the Boyer-Moore string searching algorithm, in Proceedings of the 18th Annual Symposium on Foundations of Computer Science, Washington, DC, USA, IEEE Computer Society, 1977, pp. 189–195, DOI:10.1109/SFCS.1977.3.
7. Richard Cole, Tight bounds on the complexity of the Boyer-Moore string matching algorithm, in Proceedings of the 2nd annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, September 1991, pp. 224–233, ISBN 0-89791-376-0.

Voci correlate

• Algoritmo di Knuth-Morris-Pratt
• Albero dei suffissi
• Algoritmo Apostolico-Giancarlo

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sull'algoritmo di Boyer-Moore

Collegamenti esterni

• Original paper on the Boyer-Moore algorithm (PDF), su cs.utexas.edu.
• An example of the Boyer-Moore algorithm from the homepage of J Strother Moore, co-inventor of the algorithm
• Richard Cole's 1991 paper proving runtime linearity (ps), su cs.nyu.edu.