Étant donné deux textes, il est parfois utile de savoir à quel point ils sont semblables ou différents. Un des outils utilisé pour répondre à ce problème est la distance de Levenshtein ou distance d’édition. Elle est notamment utilisé dans les correcteurs orthographiques.
Exercice
À partir d’un mot donné, on définit les opérations élémentaires comme l’ensemble d’actions suivants :
- Suppression d’une lettre
- Insertion d’une lettre
- Substitution d’une lettre par une autre.
On définit alors la distance d’édition $d$ entre deux mots comme le nombre d’opérations élémentaires nécessaires pour passer d’un mot à l’autre.
Pour $x$ un mot, on note $x_k$ la $k$-ème lettre de $x$. De plus on note $x^i$ le préfixes de $x$ composés de ses $i$ premières lettres. Ainsi on a $x^{0} = \epsilon$.
$1.$ Montrer que $d$ définit bien une distance.
$2.$ Quelle est la valeur de $d(x^i,y^0)$ ?
$3.$ Exprimer $d(x^i,y^j)$ en fonction de mots plus petits.
$4.$ Donner un algorithme pour calculer $d(x,y)$.
$5.$ Quel est sa complexité ?
Correction
$1.$ On rappel qu’une distance est un fonction $f$ positive à deux paramètres qui vérifie les propriétés de séparation (annulation de $f(x,y)$ si et seulement si $x = y$), de symétrie et l’inégalité triangulaire. La fonction $d(x,y)$ est une fonction positive qui ne s’annule que s’il n’y a pas d’opérations élémentaires à effectuer pour passer de $x$ à $y$, donc si $x=y$. Elle est également symétrique. En effet si on peut aller de $u$ à $v$ en une opération élémentaire, alors on peut aller de $v$ à $u$ également en une opération. Il nous reste à montrer que $d$ satisfait bien l’inégalité triangulaire. Si on avait $z$ tel que $d(x,z)+d(z,y)$ soit supérieur strictement à $d(x,z)$ cela signifierait qu’en considérant le chemin minimal pour aller de $x$ à $z$ puis de $z$ à $y$, on aurait un chemin de $x$ à $y$ de taille plus courte que $d(x,y)$ ce qui contredirait notre définition.
Ainsi $d$ définit bien une distance.
$2.$ On désigne la taille d’un mot $x$ par $|x|$. Commençons par noter que $d(x,y) \geq ||x|-|y||$. En effet, une opération élémentaire ne modifie la taille d’un mot que d’au plus une lettre. Ainsi, comme $y^0 = \epsilon$ on a $|y^0|=0$. On note donc que $d(x^i,y^0) \geq |x^i|$. Or le chemin qui consiste à ajouter une à une les lettres de $x_i$ prend $|x_i|$ étapes. On a donc :
\[d(x^i,y^0) = i\]
$3.$ Commençons par remarquer qu’il existe un chemin de taille minimal de $x$ à $y$ où chaque lettre n’est modifié qu’au plus une fois et que les modifications peuvent être effectuées dans l’ordre que l’on souhaite. En effet, si une solution nous incite à effectuer une opération sur une lettre à laquelle on a déjà touché, on aurait pu effectuer l’opération la première fois. De ce fait, les lettres sont indépendantes et peuvent être modifiées dans n’importe quel ordre.
Soit $i,j \geq 1$. On s’intéresse aux deux dernières lettres de $x^i$ et $y^j$. On note qu’une solution optimale ne permet pas de supprimer $x_i$ et d’ajouter $y_i$. En effet, si une telle solution existait, on remarque qu’en substituant $x_i$ en $y_i$ on gagne une étape. Il ne reste donc que trois possibilités. Soit on a modifié $x_i$ en $y_i$, ce qui a un coût de $0$ dans le cas où $x_i=y_i$, soit on a supprimé $x_i$ et dans ce cas là, il nous reste à transformer $x^{i-1}$ en $y^{j}$ ce qui a un coût de $d(i-1,j)$. Enfin, soit on a supprimé $y_j$ et il nous faut modifier $x^{i}$ en $y^{j-1}$. Notre but est de prendre la solution la moins coûteuse, ce qui nous permet donc d’obtenir la formule suivant.
\begin{align*} \forall\;0 \leq i \leq |x|,\quad d(x^i,y^0) = &\; i \\ \forall\;0 \leq j \leq |y|,\quad d(x^0,y^j) = &\; j \end{align*}
\[\forall\;1 \leq i \leq |x|,\quad 1 \leq j \leq |y|,\]
\[d(x^i,y^j) = \min(d(x^{i-1},y^{j-1}) + \delta_{i,j},\; d(x^{i-1},y^{j}) + 1,\; d(x^{i},y^{j-1}) + 1)\]
où $\delta_{i,j}$ vaut $1$ si $x_i \neq y_j$ et $0$ sinon.
On remarque que lors d’un calcul récursif de $d(x,y)$ on recalcule souvent les mêmes objets. En réalité si on écrit une fonction récursive, le temps de calcul est exponentiel. C’est pourquoi, il est plus efficace de stocker les valeurs dans un tableau pour proposer l’algorithme de programmation dynamique suivant.
$5.$ L’initialisation a un coût en $O(|x|+|y|)$. Le calcul des éléments du tableau est en $O(1)$ par case. Ainsi notre algorithme tourne en $\displaystyle \boxed{O\left(|x||y|\right)}$.