Algoritmo di pattern matching su stringhe
In Informatica gli algoritmi di pattern matching su stringhe, a volte chiamati algoritmi di confronto fra stringhe o algoritmi di ricerca di stringhe, sono una classe importante degli algoritmi sulle stringhe che provano a individuare una posizione all'interno di una stringa più grande o di un testo, in cui una o più stringhe solitamente più piccole (dette anche pattern) si trovano.
Sia Σ un alfabeto (formato da elementi appartenenti a un insieme finito). Formalmente, sia il pattern cercato che il testo su cui è effettuata la ricerca sono vettori di elementi di Σ. Σ può essere un alfabeto umano comune (per esempio, le lettere dalla A alla Z nell'alfabeto Latino). Altre applicazioni possono usare un alfabeto binario (Σ = {0,1}) o un alfabeto del DNA (Σ = {A,C,G,T}) in bioinformatica.
Nella pratica, il modo in cui le stringhe sono codificate può influenzare la fattibilità degli algoritmi di ricerca di stringhe. In particolare se usiamo una codifica a lunghezza variabile allora l'algoritmo sarà lento (in termini di tempo proporzionale a N) per trovare l'N-esimo carattere. Questo rallenterà significativamente molti dei più avanzati algoritmi di ricerca. Una soluzione possibile è invece cercare la sequenza di unità di codice (codeword): così facendo si potrebbero però produrre falsi riscontri se la codifica non fosse appositamente progettata per evitarli.
Classificazioni di base
[modifica | modifica wikitesto]I vari algoritmi possono essere classificati in base al numero di pattern che utilizzano.
Algoritmi che usano un singolo pattern
[modifica | modifica wikitesto]Sia m la lunghezza del pattern e sia n la lunghezza del testo su cui effettuare la ricerca.
| Algoritmo | Tempo di Preprocessing | Tempo di Match1 |
|---|---|---|
| Algoritmo di ricerca di stringhe Naïve | 0 (no preprocessing) | Θ((n-m+1) m) |
| Algoritmo di ricerca di stringhe di Rabin-Karp | Θ(m) | medio Θ(n+m), pessimo Θ((n-m+1) m) |
| Ricerca basata su Automa a stati finiti | Θ(m |Σ|) | Θ(n) |
| Algoritmo di Knuth-Morris-Pratt | Θ(m) | Θ(n) |
| Algoritmo di ricerca di stringhe di Boyer-Moore | Θ(m + |Σ|) | Ω(n/m), O(n) |
| Algoritmo Bitap (shift-or, shift-and, Baeza–Yates–Gonnet) | Θ(m + |Σ|) | O(mn) |
1La notazione asintotica dei tempi è espressa usando la notazione O, Ω, e Θ
L'algoritmo di ricerca di stringhe di Boyer-Moore è stato il riferimento standard in letteratura come applicazione pratica della ricerca di stringhe.[1]
Algoritmi che usano un set di pattern
[modifica | modifica wikitesto]Algoritmi che usano un numero infinito di pattern
[modifica | modifica wikitesto]Ovviamente i pattern non si possono quantificare numericamente in questo caso. Essi sono rappresentati solitamente da una grammatica regolare o da un'espressione regolare.
Altre classificazioni
[modifica | modifica wikitesto]Sono possibili altri approcci di classificazione. Uno dei più comuni usa il preprocessing come criterio principale.
| Testo non preprocessato | Testo preprocessato | |
|---|---|---|
| Pattern non preprocessati | Algoritmi elementari | Metodi con gli indici |
| Pattern preprocessati | Motori di ricerca costruiti | Metodi di firma |
Ricerca di stringhe Naïve
[modifica | modifica wikitesto]Il più semplice e meno efficiente modo di trovare le occorrenze di una stringa all'interno di un'altra è controllare se per ogni posizione, una per una, si verifica l'occorrenza di tutti i caratteri. Quindi prima di tutto vediamo se c'è una occorrenza del primo carattere del pattern nel primo carattere del testo, altrimenti la cerchiamo nel secondo carattere del testo, altrimenti nel terzo e così via; una volta trovata l'occorrenza del primo carattere del pattern nel testo, deve verificarsi sequenzialmente anche l'occorrenza degli altri caratteri del pattern, altrimenti si torna a cercare le occorrenze dei caratteri del pattern dal primo, nel carattere del testo successivo. Normalmente sarà sufficiente guardare uno o due caratteri prima di determinare una posizione nel testo come errata, così nel caso medio l'algoritmo Naïve impiega O(n + m) passi, dove n è la grandezza del testo e m la lunghezza del pattern; ma nel caso peggiore ricercare ad esempio un pattern come “aaaab” in un testo come “aaaaaaaaaab” impiegherà O(nm) passi (complessità subquadratica).
Ricerca basata su automa a Stati Finiti
[modifica | modifica wikitesto]
In questo approccio evitiamo di controllare più volte lo stesso carattere, operazione che farebbe sprecare tempo, costruendo un Automa a stati finiti deterministico (DFA) che riconosca le stringhe contenenti la stringa da ricercare desiderata. Gli automi sono complessi da costruire –essi sono solitamente creati usando la costruzione dei sottoinsiemi-, ma viceversa risultano molto veloci da usare. Per esempio l'automa a destra riconosce la parola “MOMMY”. Questo approccio è frequentemente generalizzato nella pratica per cercare espressioni regolari arbitrarie.
Ricerca troncata
[modifica | modifica wikitesto]Knuth-Morris-Pratt calcola un DFA che riconosce in input la stringa da cercare come suffisso, Boyer-Moore inizia la ricerca scorrendo testo e pattern in maniera inversa, da destra verso sinistra, così riesce solitamente a saltare l'intera dimensione del pattern ad ogni passo se questo non dovesse combaciare col testo. Baeza-Yates registra se i j caratteri precedenti fossero un prefisso della stringa ricercata ed è quindi adattabile agli algoritmi di ricerca approssimata (fuzzy). L'Algoritmo Bitap è un'applicazione dell'approccio di Baeza-Yates.
Metodi con gli indici
[modifica | modifica wikitesto]Gli algoritmi di ricerca più veloci sono basati sul preprocessing del testo. Dopo aver costruito una struttura dati detta substring index, per esempio un albero dei suffissi o un array dei suffissi, le occorrenze del pattern possono essere trovate velocemente. Per esempio, un albero dei suffissi può essere costruito in tempo Θ(n), e tutte le occorrenze Ζ del pattern possono essere trovate in tempo O(m + Ζ) (se consideriamo la dimensione dell'alfabeto come costante).
Ricerca in testi compressi
[modifica | modifica wikitesto]Gli algoritmi di ricerca di stringhe all'interno di file compressi prendono il nome di algoritmi di pattern matching su stringhe compresse (in inglese Compressed pattern matching).
Problema dell'allineamento delle codeword
[modifica | modifica wikitesto]Se il file è compresso con una codifica a lunghezza variabile si presenta un problema relativo all'allineamento delle unità di codifica, dette codeword (problema noto in inglese come "crossing codeword boundaries"): si verifica quando esistono codeword che risultano essere contenute anche all'interno di altre codeword (o "a cavallo" fra più codeword consecutive); supponiamo ad esempio che il carattere a abbia codifica "100" e che il carattere b abbia codifica "110100", in tal caso la codifica di a è suffisso della codifica di b. Questo dà vita ai cosiddetti falsi riscontri: nel momento in cui l'algoritmo di ricerca di stringhe vada alla ricerca di un'occorrenza di a potrebbe in effetti restituire come risultato una posizione corrispondente alla codifica di b. È sempre possibile decodificare (e quindi decomprimere) l'intero testo compresso per verificare se l'occorrenza del pattern compresso corrisponda effettivamente ad un'occorrenza del pattern decompresso, ma questa pratica è assolutamente da evitare in quanto richiede spazio e tempo aggiuntivi per la decompressione, pretesa eccessiva soprattutto pensando a dei file compressi disponibili online. Vi sono varie strategie adottabili per individuare i confini delle codeword con sicurezza ed evitare la decompressione totale, ad esempio:
- Lista indici iniziali di ogni codeword, ricercabili tramite ricerca binaria;
- Lista indici iniziali di ogni codeword con codifica differenziale, per occupare meno spazio all'interno del file;
- Maschera di bit, in cui il bit 1 indica il bit iniziale di ogni codeword;
- Suddivisione in blocchi per una successiva decompressione mirata parziale.
Altre varianti
[modifica | modifica wikitesto]Alcuni metodi di ricerca, per esempio la ricerca di trigrammi, hanno lo scopo di trovare il riscontro (match) “migliore”, quello che si avvicina di più al match esatto, tra pattern e testo, piuttosto che ritornare come risultato soltanto “match/non match”. Queste solitamente sono chiamate ricerche approssimate (fuzzy).
Note
[modifica | modifica wikitesto]- ^ (EN) Hume and Sunday (1991) [Fast String Searching] SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 21(11), 1221–1248 (NOVEMBER 1991 )
Bibliografia
[modifica | modifica wikitesto]- (EN) R. S. Boyer and J. S. Moore, A fast string searching algorithm, Carom. ACM 20, (10), 262–272(1977).
- (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 32: String Matching, pp. 906–932.
- (EN) Shmuel T. Klein and Dana Shapira PATTERN MATCHING IN HUFFMAN ENCODED TEXTS (2003)
Altri progetti
[modifica | modifica wikitesto]
Wikimedia Commons contiene immagini o altri file su algoritmo di pattern matching su stringhe
Collegamenti esterni
[modifica | modifica wikitesto]- (EN) Huge (maintained) list of pattern matching links, su cs.ucr.edu. URL consultato il 17 dicembre 2012 (archiviato dall'url originale il 23 marzo 2009).
- (EN) StringSearch – high-performance pattern matching algorithms in Java – Implementations of many String-Matching-Algorithms in Java (BNDM, Boyer-Moore-Horspool, Boyer-Moore-Horspool-Raita, Shift-Or)
- (EN) Exact String Matching Algorithms — Animation in Java, Detailed description and C implementation of many algorithms.
- (EN) Boyer-Moore-Raita-Thomas, su concentric.net. URL consultato il 17 dicembre 2012 (archiviato dall'url originale il 30 giugno 2007).
- (EN) (PDF) Improved Single and Multiple Approximate String Matching (PDF), su cs.ucr.edu. URL consultato il 17 dicembre 2012 (archiviato dall'url originale l'11 marzo 2017).
- (EN) Kalign2: high-performance multiple alignment of protein and nucleotide sequences allowing external features, su ncbi.nlm.nih.gov.
