Stringhe con Dynamic Programming

Sottosequenza comune massimale

Problema

Date due sequenze $T$ e $U$ , trovare la più lunga sottosequenza comune di $T$ e $U$ .
Vediamo la definizione di sottosequenza, sottosequenza comune e sottosequenza comune massimale

Sottosequenza

Una sequenza $P$ è una sottosequenza di $T$ se $P$ è ottenuto da $T$ rimuovendo uno o più dei suoi elementi
Alternativamente: P è definito come il sottoinsieme degli indici $1, . . ., n$ degli elementi di $T$ che compaiono anche in $P$
I rimanenti elementi sono elencati nello stesso ordine, senza essere necessariamente contigui
La sequenza vuota ∅ è sottosequenza di ogni altra sequenza

Esempio: $P$ = "AAATA", $T$ = "AAAATTGA"

Sottosequenza comune

Una sequenza $X$ è una sottosequenza comune (common subsequence) di due sequenze $T$ , $U$ , se è sottosequenza sia di $T$ che di $U$ .
Scriviamo $X \in CS (T, U)$

Esempio: $P$ = "AAATA", $T$ = "AAAATTGA", $X$ = "ATA"

Sottosequenza comune massimale

Una sequenza $X \in CS (T, U)$ è una sottosequenza comune massimale (longest common subsequence) di due sequenze $T$ , $U$ , se non esiste altra sottosequenza comune $Y \in CS (T, U)$ tale che $Y$ sia più lunga di $X (| Y | > | X |)$ . Scriviamo $X \in LCS (T, U)$ .

Esempio: $P$ = "AAAATTGGA", $T$ = "TAACGATATGGA", $X$ = "AAATTGGA"

Soluzione

Prima di procedere, definiamo il prefisso di $T$ . Data una sequenza $T$ composta dai caratteri $t_{1} t_{2} . . . t_{n}$ , $T (i)$ denota il prefisso di $T$ dato dai primi i caratteri.

Soluzione ricorsiva

Distinguiamo i vari casi che possono presentarsi quando vogliamo trovare la $LCS$ di due stringhe $T$ e $U$ .

Caso 1 - Gli ultimi caratteri coincidono

Gli ultimi caratteri di $T (i)$ e di $U (j)$ coincidono: $t_{i} = u_{j}$ .
Allora quel carattere è una sottosequenza e possiamo tranquillamente tenercela da parte per dopo e calcolare la $LCS (T (i - 1), U (j - 1))$ .
Dunque:

LCS (T (i), U (j)) = LCS (T (i - 1), U (j - 1)) + t_{i}

Esempio:
$LCS ("ALBERTO", "PIERO") = LCS ("ALBERT", "PIER") + "O"$

Caso 2 - Gli ultimi caratteri non coincidono

Gli ultimi caratteri di $T (i)$ e di $U (j)$ non coincidono: $t_{i} \neq u_{j}$ .
Allora bisogna controllare entrambi i casi $T (i - 1), U (j)$ e $T (i), U (j - 1)$ .

Dunque:

LCS (T (i), U (j)) = longest (LCS (T (i - 1), U (j)), LCS (T (i), U (j - 1)))

Esempio:
$LCS ("ALBERT", "PIER") = longest (LCS ("ALBER", "PIER"), LCS ("ALBERT", "PIE"))$

Caso base

La più lunga sottosequenza di $T (i)$ e $U (j)$ , quando uno dei prefissi è vuoto, i.e. se $i = 0$ or $j = 0$ , è $\emptyset$ .

Esempio:
$LCS ("ALBERT", \emptyset) = \emptyset$

Equazione di ricorrenza

$LCS (T (i), U (j)) = {\begin{cases} \emptyset & i = 0 o r j = 0 \\ LCS (T (i - 1), U (j - 1)) + t_{i} & i > 0 a n d j > 0 a n d t_{i} = u_{j} \\ longest (LCS (T (i - 1), U (j)), LCS (T (i), U (j - 1))) & i > 0 a n d j > 0 a n d t_{i} \neq u_{j} \end{cases}$

Implementazione

string LCS(const string& t, const string& u) {
    return LCSHelper(t, t.size() - 1, u, u.size() - 1);
}

string LCSHelper(const string& t, int i, const string& u, int j) {
    if(i < 0 || j < 0)
        return "";
    else if(t.at(i) == u.at(j))
        return LCSHelper(t, i - 1, u, j - 1) + t.at(i);
    else
        return max(LCSHelper(t, i, u, j - 1), LCSHelper(t, i - 1, u, j));
}

Time complexity: $O (2^{n})$ (n è la lunghezza della stringa più lunga)
Space complexity: $O (1)$

Soluzione iterativa con dynamic programming

Date due sequenze $T$ e $U$ di lunghezza $n$ e $m$ , $D P [n] [m]$ contiene la lunghezza della $LCS$ del problema originale.

Equazione di ricorrenza

$D P [i] [j] = {\begin{cases} 0 & i = 0 o r c = 0 \\ D P [i - 1] [j - 1] + 1 & i > 0 a n d j > 0 a n d t_{i} = u_{j} \\ max (D P [i - 1] [j], D P [i] [j - 1]) & i > 0 a n d j > 0 a n d t_{i} \neq u_{j} \end{cases}$

Implementazione

int LCS(const string& t, int n, const string& u, int m) {
    vector<vector<int>> DP(n + 1, vector<int>(m + 1));

    for(int i = 0; i < m + 1; i++)
        DP[0][i] = 0;
    for(int i = 0; i < n + 1; i++)
        DP[i][0] = 0;

    for(int i = 1; i < n + 1; i++) {
        for(int j = 1; j < m + 1; j++) {
            if(t.at(i - 1) == u.at(j - 1))
                DP[i][j] = DP[i - 1][j - 1] + 1;
            else
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
        }
    }

    return DP[n][m];
}

Time complexity: $O (n \cdot m)$ (n ed m sono le lunghezze delle due stringhe)
Space complexity: $O (n \cdot m)$

Ricostruzione della soluzione

Visto che tramite dynamic programming possiamo solo ottenere la lunghezza della soluzione, è necessario fare un'altra passata sulla tabella $D P$ per ricostruirci la soluzione.

Implementazione

string LCS(const string& t, int n, const string& u, int m) {
    vector<vector<int>> DP(n + 1, vector<int>(m + 1));

    for(int i = 0; i < m + 1; i++)
        DP[0][i] = 0;
    for(int i = 0; i < n + 1; i++)
        DP[i][0] = 0;

    for(int i = 1; i < n + 1; i++) {
        for(int j = 1; j < m + 1; j++) {
            if(t.at(i - 1) == u.at(j - 1))
                DP[i][j] = DP[i - 1][j - 1] + 1;
            else
                DP[i][j] = max(DP[i - 1][j], DP[i][j - 1]);
        }
    }

    return solution(t, n - 1, u, m - 1, DP);
}

string solution(const string& t, int i, const string& u, int j, const vector<vector<int>>& DP) {
    if(i < 0 || j < 0)
        return "";
    else if(t.at(i) == u.at(j)) {
        return solution(t, i - 1, u, j - 1, DP) + t.at(i);
    }
    else if(DP[i - 1][j] > DP[i][j - 1])
        return solution(t, i - 1, u, j, DP);
    else
        return solution(t, i, u, j - 1, DP);
}

Se invece si vuole solo misurare la lunghezza della $LCS$ senza ricostruire la soluzione, è possibile conservare solo la riga precedente, ottimizzando così lo spazio a $O (m)$ .

Edit distance (string matching approssimato)

Problema

Siano:

$P = p_{1} . . . p_{m}$ una stringa detta pattern
$T = t_{1} . . . t_{n}$ una stringa detta testo, con $m \leq n$

Trovare un’occorrenza k-approssimata di $P$ in $T$ con $k$ minimo ( $0 \leq k \leq m$ ).

Occorrenza k-approssimata

Un’occorrenza k-approssimata di $P$ in $T$ è una copia di $P$ in $T$ in cui sono ammessi $k$ "errori" tra $P$ e $T$ , del seguente tipo:

I corrispondenti caratteri in $P$ , $T$ sono diversi (sostituzione)
Un carattere in $P$ non è incluso in $T$ (inserimento)
Un carattere in $T$ non è incluso in $P$ (cancellazione)

Esempio: $T$ = "questoèunoscempio", $P$ = "unesempio", Output = "2"
Devo cioè inserire una 'c' tra 's' ed 'e', e sostituire la 'e' in una 'o'.

Nota: Questo problema è praticamente identico al problema "edit distance" (detta anche distanza di Levenshtein), solo che non è necessario trasformare $P$ in $T$ , ma è sufficiente che $P$ sia una sottostringa di $T$ . Dunque nel nostro caso, dati $T$ = "questoèunoscempio" e $P$ = "unesempio" l'output sarà $2$ , nell'edit distance l'output è $2 + 10 = 12$ (perchè bisogna aggiungere anche "questoèuno"). Vedremo che l'unica differenza è che nel nostro problema basta fare un ulteriore passata sull'ultima riga di $D P$ .

Soluzione

Soluzione ricorsiva

Disclaimer

Come accennato sopra, questa soluzione ritorna il minimo numero di operazione per trasformare $P$ in $T$ , quindi non risolve proprio il nostro problema. Tuttavia è utile per capire la soluzione con dynamic progrramming.

Caso 1 - Gli ultimi caratteri coincidono

Gli ultimi caratteri di $P (i)$ e di $T (i)$ coincidono: $p_{i} = t_{j}$ (usiamo $i$ per scorrere $P$ e $j$ per scorrere $T$ ).
Dunque non dobbiamo fare nessuna operazione tra le tre elencate all'inizio, e possiamo chiamare $0 + editDistance (P, T, i - 1, j - 1)$ . Sommiamo $0$ perchè non è stata fatta alcuna operazione.

Esempio:
$editDistance ("ABA", "ACA") = editDistance ("AB", "AC") + 0$

Caso 2 - Gli ultimi caratteri non coincidono - sostituzione

Gli ultimi caratteri di $P (i)$ e di $T (i)$ non coincidono: $t_{i} \neq u_{j}$ . Assumiamo allora che sia stata fatta una sostituzione del carattere e chiamiamo $1 + editDistance (P, T, i - 1, j - 1)$ . Sommiamo $1$ perchè assumiamo sia stato fatta una sostituzione.

Esempio:
$editDistance ("CA", "CC") = editDistance ("C", "C") + 1$

Caso 3 - Gli ultimi caratteri non coincidono - inserimento

Gli ultimi caratteri di $P (i)$ e di $T (i)$ non coincidono: $p_{i} = t_{j}$ . Assumiamo allora che sia stata fatta un inserimento del carattere e chiamiamo $1 + editDistance (P, T, i, j - 1)$ . Sommiamo $1$ perchè assumiamo sia stato fatto un inserimento.

Esempio:
$editDistance ("AB", "ABB") = editDistance ("AB", "AB") + 1$

Caso 4 - Gli ultimi caratteri non coincidono - rimozione

Gli ultimi caratteri di $P (i)$ e di $T (i)$ non coincidono: $p_{i} = t_{j}$ . Assumiamo allora che sia stata fatta una rimozione del carattere e chiamiamo $1 + editDistance (P, T, i - 1, j)$ . Sommiamo $1$ perchè assumiamo sia stato fatto una rimozione.

Esempio:
$editDistance ("ABB", "AB") = editDistance ("AB", "AB") + 1$

Caso base

Se $i = 0$ or $j = 0$ , devo fare o $sizeof (P)$ rimozioni o $sizeof (T)$ inserimenti.

Esempio:
$editDistance ("ABC", \emptyset) = sizeof("ABC") = sizeof (P) = 3$
Ossia, devo effettuare 3 rimozioni per trasformare "ABC" in "".

Esempio:
$editDistance (\emptyset, "ABC") = sizeof("ABC") = sizeof (T) = 3$
Ossia, devo effettuare 3 inserimenti per trasformare "" in "ABC".

Implementazione

int min(int x, int y, int z) { return min(min(x, y), z); }

int editDistance(const string& p, const string& t) {
    // We pass size() so we can return i or j and not ++i or ++j (they would be -1)
    return editDistance(p, p.size(), t, t.size());
}

int editDistance(const string& p, int i, const string& t, int j) {
    // If first string is empty, the only option is to
    // insert all characters of second string into first
    if(i == 0)
        return j;
    // If second string is empty, the only option is to
    // remove all characters of first string
    else if(j == 0)
        return i;
    // If last characters of two strings are same, nothing much to do. 
    // Ignore last characters and get count for remaining strings.
    else if(p.at(i - 1) == t.at(j - 1))
        return editDistance(p, i - 1, t, j - 1) + 0;
    // If last characters are not the same, consider all three
    // operations on last character of first string,
    // recursively compute minimum cost for all three
    // operations and take minimum of three values.
    else return 1 + min(
                editDistance(p, i - 1, t, j - 1), // Replace
                editDistance(p, i, t, j - 1), // Insert
                editDistance(p, i - 1, t, j) // Remove
            );
}

Time complexity: $O (3^{n})$ (n è la lunghezza della stringa più lunga)
Space complexity: $O (n)$

Soluzione iterativa con dynamic programming

Sia $D P [0 . . . m] [0 . . . n]$ una tabella di programmazione dinamica tale che $D P [i] [j]$ sia il minimo valore $k$ per cui esiste un’occorrenza k-approssimata di $P (i)$ in $T (j)$ che termina nella posizione $j$ .

Equazione di ricorrenza

$D P [i] [j] = {\begin{cases} 0 & i = 0 \\ i & j = 0 \\ min (D P [i - 1] [j - 1] + 0, \\ D P [i - 1] [j - 1] + 1, \\ D P [i] [j - 1] + 1, \\ D P [i - 1] [j] + 1) & altrimenti \end{cases}$

Implementazione

int editDistance(const string& p, int n, const string& t, int m) {
    vector<vector<int>> DP(n + 1, vector<int>(m + 1));

    for(int i = 0; i < m + 1; i++)
        DP[0][i] = 0; // with DP[0][i] = i we would resolve the original edit distance
    for(int i = 1; i < n + 1; i++)
        DP[i][0] = i;

    for(int i = 1; i < n + 1; i++) {
        for(int j = 1; j < m + 1; j++) {
            if(p.at(i - 1) == t.at(j - 1))
                DP[i][j] = DP[i - 1][j - 1] + 0; // Nothing to do
            else
                DP[i][j] = 1 + min(DP[i - 1][j - 1], // Replace
                                   DP[i][j - 1], // Insert
                                   DP[i - 1][j]); // Remove
        }
    }
    return *min_element(DP[n].begin(), DP[n].end());
}

Time complexity: $O (n \cdot m)$ (n ed m sono le lunghezze delle due stringhe)
Space complexity: $O (n \cdot m)$

Dunque non è detto che la "soluzione finale" si trovi nella casella "in basso a destra". È invece possibile che la soluzione debba essere ricercata essa stessa nella tabella $D P$ .