Algoritmo di Knuth-Morris-Pratt

Da Wikipedia, l'enciclopedia libera.

Questa voce riguardante un argomento di matematica non è ancora stata tradotta completamente dalla lingua francese. Terminala o riscrivila tu.

Nota: il testo da tradurre potrebbe essere nascosto: vai in modifica per visualizzarlo.

L'algoritmo di Knuth-Morris-Pratt (spesso abbreviato come algoritmo KMP) è un algoritmo di ricerca di sottosequenze, che permette di trovare le occorrenze di una sequenza $P$ in un testo $S$ . La sua peculiarità risiede nel pretrattamento della sequenza da cercare, la quale contiene l'indicazione sufficiente a determinare la posizione da cui continuare la ricerca in caso di non-corrispondenza. Questo permette all'algoritmo di non riesaminare i caratteri che erano stati precedentemente verificati, e dunque di limitare il numero di confronti necessari.

L'algoritmo é stato inventato da Knuth e Pratt, e indipendentemente da J. H. Morris nel 1975.

Indice

1 Principio di funzionamento

[modifica] Principio di funzionamento

[modifica] Approccio banale

Al fine di comprendere meglio la logica dell'algoritmo di Knuth-Morris-Pratt, é bene comprendere l'approccio banale al problema.

La sottosequenza B può essere trovata nel testo A con l'algoritmo seguente:

Fissare $i = 1$ ;
Finché restano posizioni da analizzare
- Comparare lettera a lettera la stringa B ed il testo A a partire dalla posizione $i$ ;
- Se la stringa è stata trovata, allora terminare il trattamento e restituire $i$ come posizione iniziale dell'occorrenza ;
- Altrimenti fissare $i = i + 1$ ;
Terminare la ricerca, nessuna occorrenza é stata trovata.

Questa procedura può essere migliorata interrompendo la comparazione al terzo passo, appena trovato un carattere che differisce, senza verificare l'intera stringa.

Questa soluzione ha un inconveniente: dopo una comparazione infruttuosa, la comparazione seguente inizierà alla posizione $i + 1$ , senza tenere in considerazione quelle comparazioni che sono state fatte al passo precedente, cioè alla posizione $i$ . L'algoritmo di Knuth-Morris-Pratt prima esamina la stringa B deducendo delle informazioni che permettono di evitare di trattare ogni singolo carattere più di una volta.

[modifica] Fasi

La prima fase dell'algoritmo costruisce una tabella, che indica per ogni posizione uno « sfasamento », cioè la posizione successiva dove é possibile trovare una potenziale occorrenza della stringa B.
La seconda fase effettua la vera e propria ricerca, confrontando i caratteri della stringa da ricercare a quelli del testo. Nel caso di differenza, utilizza la tabella per conoscere lo « sfasamento » da prendere in conto per continuare la ricerca senza ritornare indietro.

[modifica] Esempio

Per presentare il principio di funzionamento dell'algoritmo, consideriamo un esempio particolare: la stringa $P$ é ABCDABD mentre il testo $S$ é ABC ABCDAB ABCDABCDABDE.

Notazione: Per rappresentare le sequenze di caratteri, in questo articolo si utilizzeranno delle tabelle nelle quali gli indici iniziano da zero. Dunque, il C della stringa $P$ sarà espresso come $P [2]$ . $m$ designa la posizione, nel testo $S$ , alla quale la sequenza $P$ é in corso di verifica, e $i$ la posizione del carattere attualmente verificato in $P$ .

              1         2
    01234567890123456789012
m : v
S : ABC ABCDAB ABCDABCDABDE
P : ABCDABD
i : ^
    0123456

L'algoritmo inizia testando la corrispondenza dei caratteri, uno dopo l'altro. Quindi, al quarto passo, $m = 0$ e $i = 3$ . $S [3]$ é uno spazio e $P [3] = ' D'$ , la corrispondenza non é possibile.

              1         2
    01234567890123456789012
m : v
S : ABC ABCDAB ABCDABCDABDE
P : ABCDABD
i :    ^
    0123456

Piuttosto che ricominciare da $m = 1$ , l'algoritmo tiene conto che nessuna A era presente in $P$ tra le posizioni 0 e 3, ad eccezione della posizione 0. Di conseguenza, poiché sono stati testati tutti i caratteri precedenti, l'algoritmo sa che non c'é possibilità di trovare l'inizio di una corrispondenza se verifica nuovamente. Per questa ragione, l'algoritmo avanza fino al carattere successivo in cui potrebbe esserci una eventuale occorrenza, ponendo $m = 4$ e $i = 0$ .

              1         2
    01234567890123456789012
m :     v
S : ABC ABCDAB ABCDABCDABDE
P :     ABCDABD
i :     ^
        0123456

Una corrispondenza quasi completa é ottenuta quando, con $i = 6$ , la verifica fallisce.

              1         2
    01234567890123456789012
m :     v
S : ABC ABCDAB ABCDABCDABDE
P :     ABCDABD
i :           ^
        0123456

Tuttavia, appena prima della fine di questa corrispondenza parziale, l'algoritmo é passato sul motivo AB, che potrebbe essere l'inizio di un'altra corrispondenza. Questa informazione dev'essere dunque tenuta in conto. Poiché l'algoritmo sa già che questi primi due caratteri corrispondono con i due caratteri che precedono la posizione corrente, non é necessario di verificarli nuovamente. Quindi, l'algoritmo riprende il trattamento al carattere corrente, con $m = 8$ e $i = 2$ .

              1         2
    01234567890123456789012
m :         v
S : ABC ABCDAB ABCDABCDABDE
P :         ABCDABD
i :           ^
            0123456

Questa verifica fallisce immediatamente (C non corrisponde allo spazio in $S [10]$ ). Poiché la stringa non contiene alcuno spazio (come nel primo passo), l'algoritmo prosegue la ricerca da $m = 11$ e reinizializzando $i = 0$ .

              1         2
    01234567890123456789012
m :            v
S : ABC ABCDAB ABCDABCDABDE
P :            ABCDABD
i :            ^
               0123456

Nuovamente, l'algoritmo trova una corrispondenza parziale ABCDAB, ma il carattere seguente C non corrisponde al carattere finale D della stringa.

              1         2
    01234567890123456789012
m :            v
S : ABC ABCDAB ABCDABCDABDE
P :            ABCDABD
i :                  ^
               0123456

Usando lo stesso ragionamento di prima, l'algoritmo riprende con $m = 15$ , per ricominciare il confronto a partire dai due caratteri AB, fissando $i = 2$ come nuova posizione corrente.

              1         2
    01234567890123456789012
m :                v
S : ABC ABCDAB ABCDABCDABDE
P :                ABCDABD
i :                  ^
                   0123456

Questa volta, la corrispondenza tra stringa e testo é completa, quindi l'algoritmo ritorna la posizione 15 (cioè $m$ ) come punto d'inizio.

              1         2
    01234567890123456789012
m :                v
S : ABC ABCDAB ABCDABCDABDE
P :                ABCDABD
i :                      ^
                   0123456

[modifica] L'algoritmo di ricerca

L'esempio precedente illustra in modo intuitivo il principio di funzionamento dell'algoritmo. Suppone, cioè, la presenza di una tabella di « corrispondenze parziali » (vedi seguito dell'articolo), che indica il probabile inizio della prossima occorrenza, nel caso in cui la verifica dell'occorrenza attuale fallisca. Per ora, questa tabella, che indichiamo con $T$ , può essere considerata come una black box che ha la proprietà seguente: se abbiamo a disposizione una corrispondenza parziale fino a $S [m]$ , ma che fallisce quando compariamo $S [m + 1]$ e $P [i]$ , allora la prossima occorrenza parziale inizierà alla posizione $m + i - T [i - 1]$ . In particolare, $T [ - 1]$ esiste ed é posta a $- 1$ . Avendo questa tabella, l'algoritmo é relativamente semplice :

Fissare $i = m = 0$ . Supponiamo che $P$ abbia una lunghezza di $n$ caratteri, ed $S$ di $l$ carattere ;
Se m + i = l, allora terminare il confronto, nessuna corrispondenza é stata trovata. Altrimenti, comparare P[i] e S[m + i] ;
- Se sono uguali, allora fissare $i = i + 1$ . Se $i = n$ , allora la corrispondenza é completa. Terminare il confronto e ritornare $m$ come posizione iniziale della corrispondenza ;
- Se sono diversi, fissare $e = T [i - 1]$ . Fissare $m = m + i - e$ , e se $i > 0$ , fissare $i = e$ ;
Riprendere dal passo n° 2.

Questa descrizione mette in pratica l'algoritmo usato nell'esempio precedente. Ogni volta che avviene un errore nella verifica, viene consultata la tabella per trovare l'inizio della prossima occorrenza potenziale, ed i contatori sono aggiornati di conseguenza. Di conseguenza, la verifica dei caratteri non é mai fatta all'indietro. In particolare, ogni carattere non é verificato che una volta soltanto (fatto salvo che possa essere scartato più volte in seguito ad una non-corrispondenza. Si veda più in basso per l'efficacia dell'algoritmo).

[modifica] Esempio di codice per l'algoritmo di ricerca

Il codice C che segue è un'implementazione di questo algoritmo. Per ovviare alle limitazione intrinseche delle tabelle in C, gli indici sono traslati di una unità, cioè che $T [i]$ nel codice é equivalente a $T [i + 1]$ nella descrizione fornita sopra.

int kmp_ricerca(char *P, char *S)
{
    extern int T[];
    int m = 0;
    int i = 0;
    
    while (S[m + i] != '\0' && P[i] != '\0') {
        if (S[m + i] == P[i]) {
            ++i;
        } else {
            m += i - T[i];
            if (i > 0) i = T[i];
        }
    }
    
    if (P[i] == '\0') {
        return m;
    } else {
        return m + i;
    }
}

[modifica] Efficacia dell'algoritmo di ricerca

Supponendo l'esistenza di una tabella $T$ , la fase « ricerca » dell'algoritmo di Knuth-Morris-Pratt é di complessità O $(l)$ , dove $l$ designa la lunghezza di $S$ . Se si esclude il trattamento supplementare fissato, indotto dall'inizio e dalla fine della funzione, tutti i trattamenti sono effettuati nel ciclo principale. Per calcolare un limite sul numero d'iterazioni, é necessaria una prima osservazione riguardo della natura di $T$ . Per definizione, é costruita in maniera che se una corrispondenza parziale che inizia a $S [m]$ fallisce durante il confronto tra $S [m + i]$ e $P [i]$ , la prossima corrispondenza potenziale non inizia prima di $S [m + (i - T [i])]$ . In particolare, la potenziale corrispondenza successiva deve trovarsi una posizione dopo $m$ , in modo che $T [i] < i$ .