Algoritmi di String Matching
• Il problema dello String Matching
• Algoritmo semplice di Forza Bruta
• Algoritmo di Rabin-Karp
• Algoritmo basato sugli automi a stati finiti
• Algoritmo di Knuth-Morris-Pratt
• Algoritmo di Boyer-Moore
Luca Tabarelli - Febbraio 2002
1
Il problema dello String Matching
• Problema:
cercare all’interno di un documento il numero e la posizione
delle occorrenze di un insieme di elementi chiamato Pattern.
• Text ( T ): stringa di elementi molto spesso di dimensione
elevata, rappresenta il documento nel quale si effettua la
ricerca.
• Pattern ( P ): e’ l’insieme di elementi che si deve
ricercare all’interno di T.
2
Difficoltà:
- automatizzare la ricerca in programmi di text-editing
- ottimizzare il tempo di ricerca in sequenze lunghe e complicate;
Obiettivo dei ricercatori:
- evitare di controllare in dettaglio parti di testo diverse dal pattern;
- sfruttare tutte le informazioni che il pattern stesso puo’ contenere;
3
Algoritmo semplice di Forza Bruta
Come funziona?
* Semplicemente, fa scivolare il pattern sopra il testo;
* Se gli elementi di P si confrontano esattamente con quelli
di T
occorrenza trovata!
* Altrimenti, P viene spostato a destra di una posizione.
4
Forza Bruta
• Vantaggi:
• Svantaggi:
• molto semplice da implementare
• inefficiente
• Caso pessimo:
-ricerca di una stringa am in un testo composto da an
aaaa…….aaaa
aaaa……………….aa
m elementi
n elementi
5
Algoritmo di Rabin-Karp
Trasforma il pattern ed il blocco di testo che vuole
analizzare in singoli elementi numerici, confrontabili piu’
velocemente;
Tutti i risultati sono calcolati modulo un terzo numero
(q) per ridurre la loro grandezza;
6
Esempio:
Tutto cio’ che possiamo fare in base 10 si puo’ fare in
qualsiasi altra base!
7
Rabin - Karp
• Vantaggi:
La trasformazione di ogni blocco
del testo puo’ essere ricavata dal
valore del blocco precedente 
posso leggere il testo un carattere
alla volta senza tornare indietro;
Esecuzione più veloce con valori
opportuni di q ;
• Svantaggi:
Lavorando in modulo,
alcuni blocchi non validi
forniscono comunque valori
uguali a quelli del pattern 
si devono confrontare tutti
gli elementi dei blocchi presi
in considerazione;
Peggioramento dei tempi di
esecuzione se esistono
troppe posizioni valide;
8
Algoritmo basato su Automi a
stati finiti
• Per ricercare le occorrenze si appoggia ad una
struttura che costruisce prima di esaminare il testo: un
automa a stati finiti;
• L’automa è formato da una serie di stati nei quali si
“naviga” ricevendo un particolare elemento;
• L’algoritmo legge il testo un carattere alla volta e si
sposta nel relativo stato dell’automa;
• Se arrivo allo stato finale ho trovato un’occorrenza,
altrimenti continuo nella ricerca;
Ogni pattern diverso forma un automa diverso!
9
Un automa a stati finiti.
10
Come viene implementato un
automa?
Generalmente attraverso una
matrice chiamata “matrice
di transizione di stato”:
le righe rappresentano gli
stati;
le colonne, i possibili
prossimi elementi esaminati.
11
Come viene inizializzata la
matrice?
Per creare la matrice l’algoritmo si avvale di una funzione
chiamata funzione suffisso, che restituisce la lunghezza
del più lungo prefisso di P (Pk) che è suffisso di Pq+
carattere.
Esempio: con il pattern ‘ababaca’
(1) la matrice in posizione [3][‘f’] conterrà 0 poiché il
prefisso più lungo di P che è suffisso di P3+’f’=‘abaf’ è la
stringa vuota;
(2) la matrice in posizione [3][‘b’] = 4 poiché il prefisso
più lungo di P che è suffisso di P3+’b’=‘abab’ è proprio
‘abab’.
12
Automa a stati finiti
• Vantaggi:
Velocità di esecuzione
della ricerca grazie
all’automa che permette
di leggere il testo un
carattere alla volta.
• Svantaggi:
L’algoritmo perde molto
tempo per costruire
l’automa soprattutto per
pattern particolarmente
lunghi.
13
Algoritmo di Knuth-Morris-Pratt
* E’ l’algoritmo che riesce a sfruttare al meglio le
informazioni contenute nel pattern;
* Confronta il pattern P con se stesso;
* Cerca di capire se il pattern contiene al suo interno
l’inizio di una nuova occorrenza;
* Così facendo non serve ricominciare a confrontare i
caratteri del testo con i caratteri iniziali di P, ma dalla
posizione indicata dall’algoritmo.
14
Esempio:
1
2
3 4 5 6 7 8 9 10
P:
A B A B C
T: C D A B A B A B C D
I primi caratteri del pattern vengono riconosciuti a partire
dalla 3° posizione di T con un mismatch nella 7° posizione.
Perché ripartire confrontando P con il 4° carattere di T?
Sappiamo a priori che la 4° pos. non sarà l’inizio di una nuova
occorrenza poiché le prime due lettere di P sono diverse!
Ricominciamo a confrontare dalla 5° di T.
15
Come ricavare l’informazione che
il pattern contiene?
- Utilizza una tecnica simile a quella degli automi;
- Ma evita il calcolo della funzione di transizione;
- Utilizza un’altra funzione precalcolata detta funzione
prefisso;
- Questa funzione restituisce la lunghezza del più lungo
prefisso di P che è suffisso di Pq.
i
1
P[i]
A
Pref[i] 0
2
B
0
3
A
1
4
B
2
5 6
A B
3 4
7
A
5
8
B
6
9 10
C A
0 1
16
Knuth – Morris – Pratt
• Vantaggi:
• Svantaggi:
- è uno degli algoritmi più veloci;
- deve calcolare a priori la
funzione prefisso per ogni
pattern diverso;
- legge il testo un carattere alla
volta senza tornare indietro
- il pattern non viene sempre
riletto dall’inizio;
- sfrutta bene l’informazione del
pattern;
17
Algoritmo di Boyer - Moore
* Il suo funzionamento è simile a quello di forza bruta;
* Fa scivolare il pattern sopra il testo;
* Utilizza due tecniche euristiche: Bad Character e Good
Suffix;
* Se i caratteri del pattern si confrontano con quelli del testo
ho trovato un’occorrenza;
* Altrimenti, sposta il pattern di K posizioni, dove
K è il massimo fra i valori proposti dalle due euristiche.
18
Euristica Bad Character
Quando nella ricerca un carattere del testo crea un
mismatch con il carattere relativo del pattern,
l’euristica dichiara quel carattere come badcharacter;
Fa scivolare il pattern a destra in modo da far
coincidere il bad-character con la sua occorrenza più
a destra nel pattern.
19
Euristica Good Suffix
Simile all’euristica precedente, ma quando occorre
un mismatch, dichiara come good-suffix tutti i
caratteri che si sono allineati correttamente a P.
Fa scivolare il pattern di uno spostamento minimo
da far coincidere il good-suffix con gli eventuali
caratteri di P.
20
Esempio (1):
21
Esempio (2):
22
Esempio (3):
23
Boyer - Moore
• Vantaggi:
• Svantaggi:
- risulta essere l’algoritmo più
efficiente se il pattern P è lungo e
l’alfabeto utilizzato è grande;
- anche questo algoritmo deve
costruire a priori due strutture:
una per l’euristica badcharacter, l’altra per l’euristica
good-suffix
- sfrutta bene le informazioni del
pattern grazie alle due euristiche;
24
Conclusioni
Gli algoritmi di string matching che si comportano meglio
in generale sono senza dubbio quello di Knuth-Morris-Pratt
e quello di Boyer-Moore.
In casi particolari comunque, anche gli altri algoritmi
possono essere utilizzati tranquillamente;
Tutto dipende dal TESTO e dal PATTERN: da quanto sono
lunghi, come sono strutturati, da quanti elementi diversi dell’alfabeto
sono composti …
25