|
|
Lo String Matching Approssimato è un esempio di algoritmo che utilizza la tecnica della programmazione dinamica. Il problema di String Matching Approssimato consiste nel ricercare un pattern P all’interno di un testo T ammettendo errori (o differenze) tra T e P. I possibili errori sono:
i corrispondenti caratteri in P e in T sono diversi
un carattere in P non compare in T
un carattere in T non compare in P
Il problema quindi consiste nel trovare un’ occorrenza approssimata di P in T. Supponiamo che sia P che T inizino con un carattere vuoto in posizione 0. Denotiamo gli elementi di P e T rispettivamente come P0 P1 … Pm e T0 T1 … Tn. Definiamo D[ i, j ] come il minimo numero K di errori tra P0…Pi ed un segmento di T che termina in Tj. Chiaramente avremo che:
D[ 0, j ] = 0, per ogni j
D[ i, 0 ] = i, per ogni i
Allora risulta che D[ i, j ] può essere uguale a:
D[ i-1, j-1 ] se pi=tj, altrimenti D[ i-1, j-1 ]+1, infatti se sono diversi il numero degli errori aumenta di uno. (errore tipo 1);
D[ i-1, j ]+1 perché “avanzando” di un carattere solo nel pattern il numero di errori aumenta di uno in quanto Pi non compare in T(errore tipo 2);
D[ i, j-1 ]+1 perché avanzando di un carattere solo nel testo il numero degli errori aumenta di uno in quanto Tj non compare in P (errore tipo 3).
Si ottengono per tanto le seguenti relazioni di programmazione dinamica:
dove sigma vale 0 se pi=tj, altrimenti 1. Il numero di errori D[ m, j ] =k (dove ricordiamo che m è il numero di elementi del pattern) , solo se c’è una occorrenza approssimata (con k errori) di P in T che termina in Tj. La soluzione del problema è data dal valore di D[ m, j ] più piccolo. In linguaggio C una funzione di String Matching Approssimato può essere la seguente:
La complessità della procedura proposta è O( n m ).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.