La distance d'édition en deux lignes

La récurrence ne consulte que la ligne $i-1$ et la case précédente de la ligne $i$. Deux tableaux suffisent :

(* Distance de Levenshtein entre u et v.
   Complexite : Theta(nm) en temps, Theta(m) en memoire. *)
let levenshtein u v =
  let n = String.length u and m = String.length v in
  let prec = Array.init (m + 1) (fun j -> j) in    (* ligne i-1, ici i = 0 *)
  let cour = Array.make (m + 1) 0 in
  for i = 1 to n do
    cour.(0) <- i;                                  (* i suppressions *)
    for j = 1 to m do
      cour.(j) <-
        if u.[i-1] = v.[j-1] then prec.(j-1)
        else 1 + min (min prec.(j) cour.(j-1)) prec.(j-1)
    done;
    Array.blit cour 0 prec 0 (m + 1)                (* la courante devient la precedente *)
  done;
  prec.(m)

Mesure, comparée au calcul par table complète :

lev chaud -> chat    : deux lignes = 2, table = 2
lev niveau -> nouveau: deux lignes = 2, table = 2
lev chien -> niche   : deux lignes = 4, table = 4
lev "" -> ""         : deux lignes = 0, table = 0
lev "a" -> ""        : deux lignes = 1, table = 1

Les deux cas dégénérés comptent : avec $n=0$ la boucle ne tourne pas et l'on rend prec.(m), c'est-à-dire $m$ — le nombre d'insertions. C'est correct par construction, sans cas particulier, à condition d'avoir initialisé prec par fun j -> j et non par des zéros.

Ce qu'on perd. Le chemin. La reconstruction des opérations (le problème sur la trace des opérations, plus bas) remonte la table entière ; avec deux lignes, il n'y a plus rien à remonter. C'est la mise en garde du chapitre, vérifiée : on ne réduit la mémoire qu'après avoir décidé qu'on n'aura pas besoin du chemin.

Une variante gratuite : puisque la mémoire vaut $\Theta (m)$, on appelle la fonction avec le plus court des deux mots en second, ce qui donne $\Theta (\min (n,m))$. La distance étant symétrique, cela ne change pas le résultat.