Probleme – De la distance d'édition à la trace des opérations

1. La trace. On remonte de la case $(n,m)$ vers $(0,0)$, et à chaque pas on reconnaît laquelle des quatre situations a produit la valeur. On note levenshtein_table la fonction qui remplit et rend la table $D$ complète.

(* Renvoie la liste des operations transformant u en v, dans l'ordre.
   Precondition : d est la table complete de Levenshtein pour u et v.
   Complexite : Theta(n + m) apres le remplissage en Theta(nm). *)
let operations u v =
  let d = levenshtein_table u v in
  let ops = ref [] in
  let i = ref (String.length u) and j = ref (String.length v) in
  (* VARIANT : i + j ; INVARIANT : ops est une suite optimale
     transformant le suffixe u[i..] en le suffixe v[j..]. *)
  while !i > 0 || !j > 0 do
    if !i > 0 && !j > 0 && u.[!i-1] = v.[!j-1] && d.(!i).(!j) = d.(!i-1).(!j-1) then begin
      ops := Printf.sprintf "garder %c" u.[!i-1] :: !ops; decr i; decr j
    end else if !i > 0 && !j > 0 && d.(!i).(!j) = 1 + d.(!i-1).(!j-1) then begin
      ops := Printf.sprintf "substituer %c en %c" u.[!i-1] v.[!j-1] :: !ops; decr i; decr j
    end else if !i > 0 && d.(!i).(!j) = 1 + d.(!i-1).(!j) then begin
      ops := Printf.sprintf "supprimer %c" u.[!i-1] :: !ops; decr i
    end else begin
      ops := Printf.sprintf "inserer %c" v.[!j-1] :: !ops; decr j
    end
  done;
  !ops

L'ordre des quatre tests n'est pas libre. Il faut tester la conservation avant la substitution : quand $u_i=v_j$, la table peut aussi valoir $1+D[i-1][j-1]$ par un autre chemin, et l'on émettrait une substitution d'une lettre par elle-même — de coût $1$ au lieu de $0$. La condition d.(!i).(!j) = d.(!i-1).(!j-1) verrouille ce point.

2. La preuve.

Terminaison. Le variant est $i+j$. Chacune des quatre branches décrémente $i$, ou $j$, ou les deux : il décroît strictement, et il est minoré par $0$. La boucle fait au plus $n+m$ tours. Il faut toutefois vérifier qu'aucune branche n'est vide : quand $i=0$ et $j>0$, les trois premiers tests échouent (ils exigent $i>0$) et la dernière branche insère ; quand $j=0$ et $i>0$, seuls les deux premiers échouent et le troisième supprime, car $D[i][0]=i=1+D[i-1][0]$. Le cas de bord est donc couvert par la structure des tests, pas par un cas particulier.

Correction. L'invariant est écrit dans le code : à chaque tour, ops est une suite optimale transformant $u_{i+\mathrm{1..}n}$ en $v_{j+\mathrm{1..}m}$, et il reste $D[i][j]$ opérations à trouver. Il tient à l'initialisation ($\mathtt{ops}$ vide, suffixes vides). Il se conserve : la branche choisie est, par construction, celle qui réalise le minimum de la récurrence — donc l'opération émise appartient à une suite optimale. À la sortie, $i=j=0$ et $D[0][0]=0$ : la suite est complète et de coût $D[n][m]$.

3. Les mesures.

chaud  -> chat    : garder c, garder h, garder a, supprimer u, substituer d en t
niveau -> nouveau : garder n, inserer o, substituer i en u, garder v,
                    garder e, garder a, garder u

Deux opérations dans chaque cas, conformément aux distances $2$ et $2$. Noter que la trace obtenue pour chaud n'est pas celle que le chapitre décrit (« substituer u en t, supprimer d ») : les deux sont optimales, et le chemin remonté dépend de l'ordre des tests. Il y a une distance, il n'y a pas « la » trace.

4. La mémoire. La trace exige la table entière, $\Theta (nm)$. On ne peut pas la produire avec les deux lignes de l'exercice sur la distance d'édition : l'information a été écrasée.

Peut-on faire mieux que $\Theta (nm)$ ? Oui, et c'est l'algorithme de Hirschberg, hors programme mais instructif : on coupe $u$ en deux, on calcule en deux lignes la dernière ligne du problème gauche et la dernière ligne du problème droit renversé, on en déduit par où passe le chemin optimal au milieu, et l'on recommence des deux côtés. Le temps double au plus (la somme $nm+nm/2+nm/4+\cdots <2nm$, un raisonnement de série géométrique comme au chapitre chap:diviser), et la mémoire tombe à $\Theta (\min (n,m))$. C'est le seul moyen connu de garder le chemin sans garder la table, et il illustre que « diviser pour régner » et « programmation dynamique » se combinent au lieu de s'opposer.