Loading AI tools
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.
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) |
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
- 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.
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
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).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
