Économiser la mémoire — exercice corrigé d'algorithmique (école d'ingénieur) (chapitre 8)

Économiser la mémoire

Séquences et chaînes de caractères · niveau 2

Énoncé

On ne veut que la longueur $l (m, n)$ d'une plsc, pas la plsc elle-même.

Montrer que, pour calculer la ligne $p$ du tableau $L$ , il suffit de connaître la ligne $p - 1$ .
Écrire int longueur(String T, String U) en mémoire $Θ (n)$ . Quelle est sa complexité en temps ?
Pourquoi cette version ne permet-elle plus de reconstruire une plsc ?

Corrigé

$l (p, q)$ ne dépend que de $l (p - 1, q - 1)$ , $l (p - 1, q)$ (ligne $p - 1$ ) et $l (p, q - 1)$ (ligne $p$ , déjà calculée à gauche).
On garde deux tableaux et on les échange après chaque ligne :


static int longueur(String T, String U) {
    int m = T.length(), n = U.length();
    int[] avant = new int[n + 1], ligne = new int[n + 1]; // avant = L[p-1], ligne = L[p]
    for (int p = 1; p < m + 1; p++) {
        ligne[0] = 0;
        for (int q = 1; q < n + 1; q++)
            if (T.charAt(p - 1) == U.charAt(q - 1)) ligne[q] = 1 + avant[q - 1];
            else ligne[q] = Math.max(avant[q], ligne[q - 1]);
        int[] x = avant; avant = ligne; ligne = x;           // la ligne p devient « avant »
    }
    return avant[n];
}

Le temps reste $Θ (mn)$ , la mémoire passe de $Θ (mn)$ à $Θ (n)$ . Sur l'exercice 8.1, on retrouve $4$ .

La reconstruction remonte de $(m, n)$ vers $(0, 0)$ et consulte des lignes déjà effacées. (Hirschberg a montré qu'on peut quand même reconstruire une plsc en mémoire $Θ (n)$ , par diviser pour régner.)