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

I vari algoritmi possono essere classificati in base al numero di pattern che utilizzano.

Algoritmi che usano un singolo pattern

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)

¹La 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.

Algoritmi che usano un set di pattern

• Aho-Corasick
• Commentz-Walter
• Rabin-Karp

Algoritmi che usano un numero infinito di pattern

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

Sono possibili altri approcci di classificazione. Uno dei più comuni usa il preprocessing come criterio principale.

Classi di algoritmi di ricerca di stringhe

	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

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

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

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

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

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

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

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

Bibliografia

• (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

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su algoritmo di pattern matching su stringhe

Collegamenti esterni

• (EN) Huge (maintained) list of pattern matching links, su cs.ucr.edu.
• (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.