luca tabarelli - febbraio 20021 algoritmi di string matching string matchingil problema dello string...
TRANSCRIPT
![Page 1: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/1.jpg)
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
![Page 2: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/2.jpg)
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.
![Page 3: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/3.jpg)
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à:
![Page 4: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/4.jpg)
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.
![Page 5: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/5.jpg)
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
![Page 6: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/6.jpg)
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;
![Page 7: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/7.jpg)
7
Esempio:
Tutto cio’ che possiamo fare in base 10 si puo’ fare in qualsiasi altra base!
![Page 8: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/8.jpg)
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;
![Page 9: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/9.jpg)
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!
![Page 10: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/10.jpg)
10
Un automa a stati finiti.
![Page 11: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/11.jpg)
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.
![Page 12: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/12.jpg)
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’.
![Page 13: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/13.jpg)
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.
![Page 14: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/14.jpg)
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.
![Page 15: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/15.jpg)
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.
![Page 16: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/16.jpg)
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
![Page 17: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/17.jpg)
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;
![Page 18: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/18.jpg)
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.
![Page 19: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/19.jpg)
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.
![Page 20: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/20.jpg)
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.
![Page 21: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/21.jpg)
21
Esempio (1):
![Page 22: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/22.jpg)
22
Esempio (2):
![Page 23: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/23.jpg)
23
Esempio (3):
![Page 24: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/24.jpg)
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
![Page 25: Luca Tabarelli - Febbraio 20021 Algoritmi di String Matching String MatchingIl problema dello String Matching Forza BrutaAlgoritmo semplice di Forza Bruta](https://reader035.vdocumenti.com/reader035/viewer/2022070312/5542eb5c497959361e8c9e70/html5/thumbnails/25.jpg)
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 …