% Probl\`eme de la distance entre deux mots
% Alain FRISCH    Mars 1998

% d\'eclarations g\'en\'erales

\documentclass[a4paper]{article}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amssymb}
\usepackage{amscd}

\usepackage[cp850]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[french]{babel}
\selectlanguage{french}

\newcommand{\eps}{\varepsilon}
\renewcommand{\a}{\overline{a}}
\renewcommand{\b}{\overline{b}}
\newcommand{\fl}{\rightarrow}

\textwidth 17.8cm
\textheight 23.5 cm
\oddsidemargin -.25in
\evensidemargin -.25in
\topskip 0cm
\headheight 0cm


\title{Probl\`eme de la distance entre deux mots}
\author{Alain \sc{Frisch}}
\date{\today}

\begin{document}
\maketitle

\section{Notations et pr\'eliminaires}
Soient $a$ et $b$ deux mots. Un chemin de $a$ \`a $b$ est
une suite finie $(a,...,b)$ de mots dans laquelle chacun se d\'eduit du
pr\'ec\'edent par une des trois op\'erations :
\begin{enumerate}
 \item Suppression d'une lettre

 \item Ajout d'une lettre

 \item Modification d'une lettre
\end{enumerate}
La distance entre $a$ et $b$, not\'ee $d(a,b)$ est la longueur
minimale d'un tel chemin (moins un) (il s'agit bien
d'une distance). Le probl\`eme est de calculer
cette distance et de trouver un chemin minimal.

\noindent Si $m$ est un mot, on note $\overline{m}$ le mot obtenu
en supprimant de $m$ sa derni\`ere lettre.

\section{R\'esolution}
Il est utile de consid\'erer que les lettres sont \'ecrites sur
des plaques (physiques, que l'on d\'eplace). Les trois op\'erations sont alors :
\begin{enumerate}
 \item Suppression d'une plaque

 \item Insertion d'une plaque

 \item Modification de la lettre port\'ee par une plaque
\end{enumerate}

Si $a=\eps$ ou $b=\eps$, le probl\`eme est trivial :
$d(a,\eps)=|a|$ et on exhibe facilement un chemin
minimal. On suppose donc $a\neq \eps$ et $b\neq \eps$.
On a clairement :
$d(a,b)\leq 1+\min \{d(a,\b), d(\a,b), d(\a,\b)\}$
et si $a$ et $b$ se terminent par la m\^eme lettre :
$d(a,b)\leq d(\a,\b)$. On construit \`a partir d'un chemin minimal
entre $a$ et $\b$ un chemin entre $a$ et $b$ de longueur $1+d(a,\b)$, et de m\^eme pour
les autres.

Prenons un chemin minimal reliant $a$ \`a $b$ et consid\'erons
la plaque portant la derni\`ere lettre de $b$ dans l'etape
finale. Plusieurs cas sont possibles :

\begin{enumerate}
 \item cette plaque a \'et\'e ajout\'ee lors d'une \'etape interm\'ediaire
(elle ne se trouvait pas dans $a$) : on peut supposer que
l'op\'eration d'ajout de cette plaque s'effectue en dernier,
d'o\`u le chemin $a \fl \b \fl b$, dont le sous chemin
$a \fl \b$ est minimal (si on pouvait le raccourcir, le chemin
complet $a \fl b$ ne serait pas minimal). Alors :
$d(a,b)=1+d(a,\b)$.

 \item cette plaque se trouvait en derni\`ere position
dans $a$ (premi\`ere \'etape du chemin). Si elle porte d\`es la
premi\`ere \'etape sa lettre d\'efinitive, c'est-\`a-dire si
$a$ et $b$ ont la m\^eme derni\`ere lettre, alors cette plaque
ne subit aucune modification au cours des diff\'erentes
\'etapes (sinon le chemin n'est pas minimal !). En supprimant
cette plaque de toutes les \'etapes du chemin, on obtient
un chemin $\a \fl \b$ qui est minimal, donc
$d(a,b)=d(\a,\b)$.

Par contre, si $a$ et $b$ n'ont pas la m\^eme derni\`ere lettre,
alors cette plaque subit une modification et une seule
au cours des \'etapes du chemin. On peut supposer que cette
op\'eration s'effectue en dernier et cela donne :
$d(a,b)=1+d(\a,\b)$.

 \item cette plaque se trouvait autre part dans $a$. La derni\`ere
case de $a$ (premi\`ere \'etape du chemin) doit \^etre supprim\'ee lors
d'une \'etape, car l'ordre (\`a gauche/\`a droite) des plaques de $a$ qui se retrouvent dans
$b$ n'est pas modifi\'e. Avant d'\^etre supprim\'ee, la
plaque ne subit pas de modification (sinon on peut
raccourcir le chemin), donc on peut supposer que la suppression
s'effectue lors de la premi\`ere \'etape : $a \fl \a \fl b$
d'o\`u $d(a,b)=1+d(\a,b)$.
\end{enumerate}

Conclusion: si $a$ et $b$ ont la m\^eme derni\`ere lettre,
alors $d(a,b)=\min \{1+d(a,\b), 1+d(\a,b), d(\a,\b)\}$,
sinon $d(a,b)=\min \{1+d(a,\b), 1+d(\a,b), 1+d(\a,\b)\}$.

\newpage

\section {Algorithme et programme}

On d\'eduit de l'\'etude pr\'ec\'edente l'algorithme suivant,
qui consiste \`a calculer la matrice
$(d_{i,j})_{0\leq i\leq |a|, 0\leq j\leq |b|}$
ligne par ligne, colonne par colonne, o\`u $d_{i,j}$ est
la distance entre le pr\'efixe de $a$ avec $i$ lettres,
et celui de $b$ avec $j$ lettres. En fait, il n'est
pas n\'ecessaire de conserver toute la matrice, seule la
ligne pr\'ec\'edente est utilis\'ee dans le calcul de la ligne
courante (encore mieux: il suffit de conserver les derni\`eres
$j+1$ cases trait\'ees dans un tableau circulaire).

\begin{verbatim}
(* Distance et chemin entre deux mots *)
(* Alain FRISCH    mars 1998 *)

let distance a b =
 let n = string_length a
 and m = string_length b
 in
 let v = ref (make_vect (n+1) 0)
 and w = ref [||]
 in
 for i=0 to n do !v.(i)<-i done;
 for j=1 to m do
  w:=make_vect (n+1) j;
  for i=1 to n do
  !w.(i)<- min (1+min !v.(i) !w.(i-1)) (if a.[i-1]=b.[j-1] then !v.(i-1) else 1+(!v.(i-1)))
  done;
  v:=!w;
 done;
 !v.(n);;

let chemin a b =
 let n = string_length a
 and m = string_length b
 in
 let v = ref (make_vect (n+1) (0,[]))
 and w = ref [||]
 and p (l,ch) = l+1,ch
 and plus_petit x y z =
 if (fst x<=fst y) & (fst x<=fst z) then 1,x
 else if (fst y<=fst x) & (fst y<=fst z) then 2,y
 else 3,z
 in
 !v.(0)<-0,[""];
 for i=1 to n do !v.(i)<-i,sub_string a 0 i::(snd !v.(i-1)) done;
 for j=1 to m do
  w:=make_vect (n+1) (j,[""]);
  !w.(0)<-j,(snd !v.(0))@[sub_string b 0 j];
  for i=1 to n do
  !w.(i)<-
  match
   (plus_petit (p !v.(i)) (p !w.(i-1)) (if a.[i-1]=b.[j-1] then !v.(i-1) else (p !v.(i-1))))
  with
   | 1,(l,ch) -> (l,ch@[sub_string b 0 j])
   | 2,(l,ch) -> (l,sub_string a 0 i ::ch)
   | _,(l,ch) ->
   let ch2=map (fun m->m^(char_for_read b.[j-1])) ch in
   if (a.[i-1]=b.[j-1]) then (l,ch2)
   else (l,sub_string a 0 i ::ch2)
  done;
  v:=!w;
 done;
 !v.(n);;



(* ESSAIS *)
chemin "echarde" "charrue";;
chemin "knuth" "cheno";;
chemin "cheno" "chameau";;
chemin "nelson monfort" "mets le son moins fort";;
chemin "frankenstein" "fantastique";;

["echarde"; "echarre"; "charre"; "charrue"]
["knuth"; "knuto"; "knuno"; "kneno"; "kheno"; "cheno"]
["cheno"; "chenu"; "cheau"; "chaeau"; "chameau"]
["nelson monfort"; "melson monfort"; "metlson monfort"; "metslson monfort";
 "mets lson monfort"; "mets leson monfort"; "mets le son monfort";
 "mets le son moinfort"; "mets le son moinsfort"; "mets le son moins fort"]
["frankenstein"; "frankensteiq"; "frankenstiq"; "frankestiq"; "frankastiq";
 "frantastiq"; "fantastiq"; "fantastiqu"; "fantastique"]
\end{verbatim}

Remarque: dans \verb!chemin!, il serait plus efficace
de conserver toute la matrice et de construire le chemin
explicite \`a <<~rebours~>>.

\end{document}