Algoritmo di Knuth-Morris-Pratt

L'algoritmo di Knuth-Morris-Pratt (spesso abbreviato come algoritmo KMP) è un algoritmo di pattern matching su stringhe, che permette di trovare le occorrenze di una stringa (pattern) $P$ in un testo $S$. La sua peculiarità risiede nel pretrattamento della stringa 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.

Principio di funzionamento

Approccio banale

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

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

1. Fissare $i=1$ ;
2. 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$ ;
3. 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.

Fasi

1. 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.
2. 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.

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 stringhe di caratteri, in questa voce 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 stringa $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]={\mathtt {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$ (è importante notare che $m$ prima diventa $3$ con $i=0$, in quanto $m+i-T[i]=3+0-0=3$, poi non essendoci corrispondenza diventa $4$ con $i=0$, in quanto $T[0]=-1$; si veda l'algoritmo più avanti per chiarimenti sulla tabella $T$).

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

Una corrispondenza quasi completa è ottenuta quando con m=4 e 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$ (come sopra, in realtà $m$ prima diventa $10$ con $i=0$, in quanto $m+i-T[i]=8+2-0=10$, poi non essendoci corrispondenza diventa $11$ con $i=0$, in quanto $T[0]=-1$).

              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 restituisce la posizione 15 (cioè $m$) come punto d'inizio.

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

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+i]$ e $P[i]$, allora la prossima occorrenza parziale inizierà alla posizione $m+i-T[i]$. In particolare, $T[0]$ esiste ed è posta a $-1$. Avendo questa tabella, l'algoritmo è relativamente semplice:

1. Fissare $i=m=0$. Supponiamo che $P$ abbia una lunghezza di $n$ caratteri, ed $S$ di $l$ caratteri;
2. 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 restituire $m$ come posizione iniziale della corrispondenza;
   • Se sono diversi, fissare $m=m+i-T[i]$, e se $i>0$, fissare $i=T[i]$ ;
3. 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'efficienza dell'algoritmo).

Esempio di codice per l'algoritmo di ricerca

Il codice C che segue è un'implementazione di questo algoritmo.

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;
    }
}

Efficienza 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$.

Partendo da questa assunzione, si dimostra che il ciclo viene eseguito al massimo $2l$ volte. Ad ogni iterazione, viene eseguito uno dei due rami dell'istruzione if.

• il primo ramo aumenta invariabilmente $i$ e non modifica $m$, cosicché l'indice $m+i$ dei caratteri confrontati nella stringa $S$ viene aumentato.
• il secondo ramo incrementa $m$ di $i-T[i]$. Essendo $i-T[i]$ sempre positivo, come visto precedentemente, si deduce che l'indice $m$ dell'inizio della possibile corrispondenza viene aumentato.

Il ciclo termina se $S[m+i]='\backslash 0'$, il che vuol dire, tenendo presente la convenzione del C secondo cui il carattere NUL indica la fine di una stringa, che $m+i=l$. Conseguentemente, ogni ramo dell'istruzione if può essere eseguito al più $l$ volte, dato che i due rami aumentano rispettivamente o $m+i$ o $m$, con $m\leq m+i$; cosicché se $m=l$, allora $m+i\geq l$, ed essendo l'aumento ad ogni ciclo almeno di una unità, $m+i=l$ è necessariamente vero per il passato.

Il ciclo dunque viene eseguito al massimo $2l$ volte, quindi la complessità computazionale è $O(l)$.

La tavola delle « corrispondenze parziali »

Lo scopo di questa tabella è quello di permettere all'algoritmo di non controllare ogni carattere del testo più di una volta. L'osservazione chiave per stabilire la natura lineare della ricerca, che consente a questo algoritmo di funzionare, è che dopo aver verificato una porzione di testo contenente una « porzione iniziale » della stringa, è possibile determinare in quale posizioni possono incominciare le successive possibili occorrenze e da esse continuare il confronto a partire dalla posizione corrente del testo. In altri termini, i motifs (le sotto-porzioni della stringa) vengono « pre-identificati » nella stringa e viene creata una lista che indica tutte le posizioni possibili da cui continuare saltando il maggior numero di caratteri inutili, senza tuttavia sacrificare alcuna corrispondenza potenziale.

Per ciascuna posizione nella stringa, è necessario determinare la lunghezza massima del motif iniziale, che termina nella posizione corrente, ma che non consente una corrispondenza completa (e che quindi probabilmente fallirà). Quindi, $T[i]$ indica esattamente la massima lunghezza del motif iniziale che termina in $P[i]$. Per convenzione, la stringa nulla ha lunghezza zero. Essendo la verifica iniziale della stringa un caso particolare (non essendoci la possibilità del backtracking), si pone $T[0]=-1$, come discusso in precedenza.

Descrizione dello pseudocodice

Il principio è quello della ricerca in generale: buona parte del lavoro è già stato fatto nel raggiungere la posizione corrente, e quindi ce ne resta poco. Utilizziamo la parte già popolata della tabella $T$ per trovare potenziali sottostringhe, in modo analogo all'algoritmo di ricerca. La sola piccola complicazione è che la logica che in seguito è corretta, purtroppo restituisce sottostringhe non corrette all'inizio. Questo problema richiede del codice di inizializzazione.

algoritmo kmp_table:
    input:
        un array di caratteri, W (la parola da analizzare)
        un array di interi, T (la tabella da riempire)
    output:
        niente (ma durante l'operazione popoliamo la tabella)

    definire le variabili:
        un intero, pos ← 2 (la posizione corrente della computazione di T)
        un intero, cnd ← 0 (l'indice che parte da zero in W del prossimo carattere della sottostringa candidata)

    (i primi pochi valori sono fissi ma diversi da quelli che l'algoritmo potrebbe suggerire)
    let T[0] ← -1, T[1] ← 0

    while pos è minore della lunghezza di W, do:
        (primo caso: la sottostringa continua)
        if W[pos - 1] = W[cnd], let T[pos] ← cnd + 1, pos ← pos + 1, cnd ← cnd + 1

        (secondo caso: non lo fa ma non possiamo tornare indietro)
        else, if cnd > 0, let cnd ← T[cnd]

        (terzo caso: abbiamo finito i candidati.  Nota cnd = 0)
        else, let T[pos] ← 0, pos ← pos + 1

Efficienza della costruzione della tabella

La complessità dell'algoritmo della tabella è O(n), dove n è la lunghezza di W. A parte l'inizializzazione, tutto il lavoro è svolto nel ciclo while, è sufficiente mostrare che il ciclo viene eseguito O(n) volte, che dovrebbe essere fatto esaminando simultaneamente i valori pos e pos - cnd.

• Nel primo ramo, pos - cnd rimane costante, visto che pos e cnd vengono incrementati insieme ma, ovviamente, pos aumenta di continuo.
• Nel secondo caso, cnd viene sostituito da T[cnd], che abbiamo visto essere strettamente minore di cnd, per cui pos - cnd viene aumentato.
• Nel terzo caso, pos viene aumentato, mentre cnd resta stabile, e quindi pos e pos - cnd aumentano.

Dal momento che pos ≥ pos - cnd, questo significa che ad ogni ciclo sia pos che una quantità inferiore a pos aumentano; quindi, visto che l'algoritmo termina al raggiungimento di pos = n, deve terminare dopo al massimo 2n iterazioni, dato che pos - cnd parte da 1. Quindi la complessità dell'algoritmo della tabella è O(n).

Efficienza dell'algoritmo KMP

Dal momento che le due parti dell'algoritmo hanno, rispettivamente, complessità di O(k) e di O(n), la complessità totale è O(n + k).

Bibliografia

• (EN) Donald Knuth, James H. Morris, Jr. e Vaughan Pratt. Fast pattern matching in strings. SIAM Journal on Computing, 6(2):323–350. 1977. Citations. Pubblicazione originale
• (EN) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein. Introduction to Algorithms, Seconda edizione. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capitolo 32.4: The Knuth-Morris-Pratt algorithm, pp.923–931.

Voci correlate

• Algoritmo di Boyer-Moore.

Collegamenti esterni

• (EN) Una spiegazione dell'algoritmo.
• (EN) Un esempio dell'algoritmo di Knuth-Morris-Pratt, sul sito Internet di J Strother Moore, co-inventore dell'algoritmo di Boyer-Moore.