Luca Tabarelli - Febbraio 2002 1

Algoritmi di String Matching

• Il problema dello SString tring MMatchingatching

• Algoritmo semplice di Forza BrutaForza Bruta

• Algoritmo di Rabin-KarpRabin-Karp

• Algoritmo basato sugli automi a stati finitiautomi a stati finiti

• Algoritmo di Knuth-Morris-PrattKnuth-Morris-Pratt

• Algoritmo di Boyer-MooreBoyer-Moore

2

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.

3

- 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;

Difficoltà:

4

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.

5

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

6

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;

7

Esempio:

Tutto cio’ che possiamo fare in base 10 si puo’ fare in qualsiasi altra base!

8

Rabin - Karp

• Vantaggi: • Svantaggi:

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 ;

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;

9

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!

10

Un automa a stati finiti.

11

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.

12

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

13

Automa a stati finiti

• Vantaggi: • Svantaggi:

Velocità di esecuzione della ricerca grazie all’automa che permette di leggere il testo un carattere alla volta.

L’algoritmo perde molto tempo per costruire l’automa soprattutto per pattern particolarmente lunghi.

14

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.

15

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.

16

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 2 3 4 5 6 7 8 9 10

P[i] A B A B A B A B C A

Pref[i] 0 0 1 2 3 4 5 6 0 1

17

Knuth – Morris – Pratt

• Vantaggi: • Svantaggi:

- è uno degli algoritmi più veloci;

- legge il testo un carattere alla volta senza tornare indietro

- il pattern non viene sempre riletto dall’inizio;

- sfrutta bene l’informazione del pattern;

- deve calcolare a priori la funzione prefisso per ogni pattern diverso;

18

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.

19

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 bad-character;

Fa scivolare il pattern a destra in modo da far coincidere il bad-character con la sua occorrenza più a destra nel pattern.

20

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.

21

Esempio (1):

22

Esempio (2):

23

Esempio (3):

24

Boyer - Moore

• Vantaggi: • Svantaggi:

- risulta essere l’algoritmo più efficiente se il pattern P è lungo e l’alfabeto utilizzato è grande;

- sfrutta bene le informazioni del pattern grazie alle due euristiche;

- anche questo algoritmo deve costruire a priori due strutture: una per l’euristica bad-character, l’altra per l’euristica good-suffix

25

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 …