Distance d'édition

• Transformer un $p$-préfixe en la chaîne vide demande $p$ suppressions : $e(p,0)=p$. De même $e(0,q)=q$ (insertions).
• Dans une transformation optimale, le dernier symbole $t_{p-1}$ est soit supprimé (il reste à transformer $T[0:p-1]$ en $U[0:q]$ : $1+e(p-1,q)$), soit placé en face de $u_{q-1}$ (gratuitement s'ils sont égaux, par un remplacement sinon : $e(p-1,q-1)$ ou $1+e(p-1,q-1)$), soit $u_{q-1}$ est inséré ($1+e(p,q-1)$). Si $t_{p-1}=u_{q-1}$, les placer en face est toujours au moins aussi bon, d'où la formule.
• Calcul du tableau puis reconstruction à rebours, en retrouvant quel cas a donné le minimum :

static int[][] calculerE(String T, String U) {
    int m = T.length(), n = U.length();
    int[][] E = new int[m + 1][n + 1];
    for (int p = 0; p < m + 1; p++) E[p][0] = p;          // base : p suppressions
    for (int q = 0; q < n + 1; q++) E[0][q] = q;          // base : q insertions
    for (int p = 1; p < m + 1; p++)
        for (int q = 1; q < n + 1; q++)
            if (T.charAt(p - 1) == U.charAt(q - 1)) E[p][q] = E[p - 1][q - 1];
            else E[p][q] = 1 + Math.min(E[p - 1][q - 1], Math.min(E[p - 1][q], E[p][q - 1]));
    return E;
}
static void operations(String T, String U, int[][] E, int p, int q) {
    if (p == 0 && q == 0) return;
    if (p > 0 && q > 0 && T.charAt(p - 1) == U.charAt(q - 1) && E[p][q] == E[p - 1][q - 1]) {
        operations(T, U, E, p - 1, q - 1);                // symbole conservé
    } else if (p > 0 && q > 0 && E[p][q] == E[p - 1][q - 1] + 1) {
        operations(T, U, E, p - 1, q - 1);
        System.out.println("  remplacer " + T.charAt(p - 1) + " par " + U.charAt(q - 1));
    } else if (p > 0 && E[p][q] == E[p - 1][q] + 1) {
        operations(T, U, E, p - 1, q);
        System.out.println("  supprimer " + T.charAt(p - 1));
    } else {
        operations(T, U, E, p, q - 1);
        System.out.println("  insérer " + U.charAt(q - 1));
    }
}

Le calcul est en $\Theta (mn)$, la reconstruction en $\Theta (m+n)$.

• Exécution :

e(chat, champ) = 2
  insérer m
  remplacer t par p
e(algorithme, logarithme) = 3
  remplacer a par l
  remplacer l par o
  remplacer o par a

nom : T
valeurs : c h a _ t
indices : non
colorier : 3 4

nom : U
valeurs : c h a m p
indices : non
colorier : 3 4
legende : distance 2

nom : T
valeurs : a l g o r i t h m e
indices : non
colorier : 0 1 3

nom : U
valeurs : l o g a r i t h m e
indices : non
colorier : 0 1 3
legende : trois remplacements : distance 3