Algoritmo di Boyer-Moore per il SSM

Nel 1977 Robert Boyer e J Moore hanno sviluppato un algoritmo molto efficiente per il String Searching Matching che prende appunto il nome degli autori.

Questo algoritmo è divenuto molto famoso, tant’è che non solo è considerato l’ algoritmo più efficiente nel caso comune, ma viene implementato (tutto o in una versione più semplice) nelle funzioni di ricerca degli editor di testo. L’ algoritmo di Boyer-Moore poi, è implementato anche dal programma di utilità grep.

Dati:

• n: E’ la lunghezza del pattern e P il pattern da ricercare
• m: E’ la lunghezza del testo in cui cercare e T il testo in cui cercare
• σ: E’ la lunghezza dell’ alfabeto di supporto

Come vedremo fra poco, l’ algoritmo esegue i confronti partendo da destra verso sinistra. Prima di iniziare la ricerca viene effettuato in tempo O(m+σ) un preprocessamento del pattern da ricercare,  che permette poi all’ algoritmo di svolgere la ricerca in tempo O(mn) nel caso in cui il pattern sia presente nel testo, e  O(3m) nel caso in cui il pattern non sia presente.

Come funziona

Una delle idee chiave dell’ algortimo è il fatto di cercare di eseguire il matching del pattern dalla fine di questo, e non dall’ inizio. Questo ci permette, in caso di mismatch, di spostarci avanti di n posizioni (ovvero della lunghezza del pattern) nel caso migliore.

Per esempio:

         0 . j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 . . . . m
T:       P   I   A   R   C   I   A   O
P:       C   I   A   O                          n = 4

In questo caso, visto che T[j+3] = 'R' e P[4] = 'O' sono diversi, possiamo spostare il puntatore avanti di n posizioni. Questo è il caso migliore, lo spostamento in avanti si calcola prendendo il massimo fra due funzioni chiamate Good-Suffix Shift e Bad-Character Shift.

Bad-Character Shift: spostamento del carattere discordante

Il  Bad-Character Shift ci dice di trovare la prima occorrenza del carattere discordante del testo T in P, che indicheremo con k.

Ci sono 3 casi, che vediamo per esempi:

Primo caso: s = 0

E’ l’ esempio visto poco fa, che riproponiamo:

   0 . . j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 . . . . m
T:       P   I   A   R   C   I   A   O
P:       C   I   A   O                          n = 4

“R” è il carattere discordante. Cerchiamo la posizione k in P tale per cui P[k] = T[j+1] e la indichiamo con s. Visto che "R" non è presente in P, e quindi k=0, questa euristica ci suggerisce che possiamo spostare tranquillamente il pattern di 4 posizioni:

   0 . . j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 . . . . m
T:       P   I   A   R   C   I   A   O
P:                       C   I   A   O          n = 4

Secondo caso: s < k

Abbiamo un carattere discordante in posizione k=j+4:

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 . . . . m
T:          A   S   D   F   P   I   A   R   C   I   A    O
P:          R   C   A   P   C   I   A   O                          n = 8

Cerchiamo nel pattern P la prima occorrenza del carattere discordante T[k] (ovvero “P”). Questo si trova in posizione s=j+3.
Visto che k si trova a destra di s (la fine del nostro pattern) possiamo spostare avanti il pattern di k-s posizioni.

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 . . . . m
T:          A   S   D   F   P   I   A   R   C   I   A    O
P:              R   C   A   P   C   I   A   O                        n = 8

Terzo caso: s > k

Abbiamo un carattere discordante in posizione k=j+4:

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 . . . . m
T:          A   S   D   F   R   I   A   R   C   I   A    O
P:          S   C   A   P   C   I   A   R                          n = 8

Come in precedenza, l’ algoritmo del carattere errato cerca una corrispondenza del carattere discordante T[j+4] = “R” in P. In questo caso, lo troverà a destra di k, in posizione s=j+7. In questo caso quindi ci proporrà un poco conveniente spostamento negativo di s-k posizioni. L’ altra euristica verrà quindi scelta per questo caso.

Good Suffix Shift

Partiamo da un esempio come prima:

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 j+12 . . . . m
T:          A   S   D   F   R   I   A   R   O   C    I   A    R
P:          I   A   R   O   C   I   A   R                                 n = 8

In questo caso, il Bad Character abbiamo visto che ci suggerisce uno spostamento negativo. Il Good Suffix Shift invece, cerca nel nostro pattern P una sequenza di caratteri uguale a quella che ha determinato il “buon suffisso” (ovvero tutto ciò che c’è a destra del carattere discordante k=j+4). Visto che la sequenza [j+5 … j+7] = “IAR” è presente nel nostro pattern, ci suggerisce di spostarci in modo da far combaciare le sequenze:

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 j+12 . . . . m
T:          A   S   D   F   R   I   A   R   O   C    I   A    R
P:                              I   A   R   O   C    I   A    R           n = 8

In caso non sia possibile “riciclare” il suffisso, ci viene suggerito uno spostamento del pattern in avanti fino a dopo l’ultima posizione in T considerata (quindi di n posizioni):

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 j+12 . . . . m
T:          A   S   D   F   R   I   A   R   O   C    I   A    R
P:          I   B   R   O   C   I   A   R                                 n = 8

Visto che il suffisso nonè presente nel pattern:

   0 . . .  j  j+1 j+2 j+3 j+4 j+5 j+6 j+7 j+8 j+9 j+10 j+11 j+12 . . . . m
T:          A   S   D   F   R   I   A   R   O   C    I   A    R
P:                                          I   B   R   O   C   I   A   R  n = 8

Da questo algoritmo, è nata una famiglia di algoritmi chiamata appunto Boyer-Moore. La caratteristica di eseguire un matching dalla fine della stringa, gli permette di eseguire molti meno confronti e di essere quindi molto efficiente.