Voir la source de Distance de Levenshtein

La '''distance de Levenshtein''' est une [[distance (mathématiques)|distance]], au sens mathématique du terme, donnant une mesure de la différence entre deux [[chaîne de caractères|chaînes de caractères]]. Elle est égale au nombre minimal d'opérations nécessaires pour transformer une chaîne de caractères en une autre, à l'aide des trois opérations autorisées : remplacement, suppression et ajout.

Elle a été proposée par [[Vladimir Levenshtein]] en [[1965 en science|1965]]. Elle est également connue sous les noms de '''distance d'édition''' ou de '''déformation dynamique temporelle''', notamment en [[reconnaissance de formes]] et particulièrement en [[reconnaissance vocale]]<ref>Frédéric Sur, [http://www.loria.fr/~sur/enseignement/distance_edition_FSur.pdf La distance d’édition (ou distance de Levenshtein)], École des Mines de Nancy, consulté le 20 novembre 2013.</ref>{{,}}<ref>Deller, John R., John G. Proakis, and John HL Hansen. ''{{Lang|en|Discrete-time processing of speech signals}}''. New York, NY, États-Unis : IEEE, 2000, {{p.|651-671}}.</ref>.

Cette distance est d'autant plus grande que le nombre de différences entre les deux chaînes est grand. La distance de Levenshtein peut être considérée comme une généralisation de la [[distance de Hamming]]. On peut montrer en particulier que la distance de Hamming est un [[majorant]] de la distance de Levenshtein.

== Définition ==
On appelle distance de Levenshtein entre deux chaînes M et P le coût minimal pour transformer M en P en effectuant les seules opérations élémentaires (au niveau d'un caractère) suivantes (on agit exclusivement sur M et successivement sur ses transformés) :
* substitution ;
* insertion (ou ajout) ;
* suppression (ou effacement).
Formellement, on définit cette distance, avec deux chaînes <math>a</math> et <math>b</math>, <math>|a|</math> le cardinal de <math>a</math> (ou son nombre de lettres), et <math>a-1</math> la chaîne <math>a</math> tronquée de sa {{1re}} lettre <math>a[0]</math>:
<math>\qquad\operatorname{lev}(a,b) = 
\begin{cases}
  \max(|a|,|b|) & \text{ si } \min(|a|,|b|)=0, \\
  \operatorname{lev}(a-1,b-1) & \text{ si } a[0]=b[0], \\
  1 + \min \begin{cases}
          \operatorname{lev}(a-1,b)\\
          \operatorname{lev}(a,b-1)\\
          \operatorname{lev}(a-1,b-1)
       \end{cases} & \text{ sinon.}
\end{cases}
</math>

On associe à chacune de ces opérations un coût. Généralement, le coût est égal à 1 pour les trois opérations. La distance est la somme des coûts des opérations effectuées. On peut montrer que définir une distance au sens mathématique du terme entre les caractères d'un alphabet, entraine que la distance de Levenshtein soit aussi une distance au sens mathématique du terme, sur l'ensemble des chaines construites sur l'alphabet.

== Exemples ==
Si M = « examen » et P = « examen », alors <math>\operatorname{lev}(M,P) = 0</math>, parce qu'aucune opération n'a été réalisée.

Si M = « exam'''e'''n » et P = « exam'''a'''n », alors <math>\operatorname{lev}(M,P) = 1</math>, parce qu’il y a eu une substitution (changement du ''e'' en ''a''), et que l'on ne peut pas en faire moins.

== Algorithme ==

L’algorithme ci-dessous, dû à [[Algorithme de Wagner-Fischer|Wagner et Fischer]] (1974), permet de calculer la distance de Levenshtein entre deux chaînes de caractères courtes. Cet algorithme est un exemple de [[programmation dynamique]] (solution de type du bas en haut), qui utilise une [[Matrice (mathématiques)|matrice]] de dimension <math>(n + 1)\times(m + 1)</math> où <var>n</var> et <var>m</var> sont les dimensions des deux chaînes de caractères. Dans le [[pseudo-code]] suivant, la chaîne ''chaine1'' est de longueur ''longueurChaine1'' et ''chaine2'', de longueur ''longueurChaine2''.

Cet algorithme renvoie un [[Entier naturel|entier positif]] ou nul. Par définition d'une distance au sens mathématique du terme, l'algorithme renvoie 0, si et seulement si les deux chaînes sont égales. Pour deux chaînes de longueurs données, la valeur maximale de la distance est la longueur de la chaîne la plus longue.
  '''entier''' DistanceDeLevenshtein('''caractere''' chaine1[1..longueurChaine1],
                               '''caractere''' chaine2[1..longueurChaine2])
    ''// D est un tableau de longueurChaine1+1 rangées et longueurChaine2+1 colonnes''
    ''// D est indexé à partir de 0, les chaînes à partir de 1''
    '''déclarer''' '''entier''' D[0..longueurChaine1, 0..longueurChaine2]
    ''// i et j itèrent sur chaine1 et chaine2''
    '''déclarer''' '''entier''' i, j, coûtSubstitution
  
    '''pour''' i '''de''' 0 '''à''' longueurChaine1
        <math>D[i, 0]:= i</math>
    '''pour''' j '''de''' 0 '''à''' longueurChaine2
        <math>D[0, j]:= j</math>
  
    '''pour''' i '''de''' 1 '''à''' longueurChaine1
       '''pour''' j '''de''' 1 '''à''' longueurChaine2
           '''si''' chaine1[i] = chaine2[j] '''alors''' coûtSubstitution := 0
           '''sinon''' coûtSubstitution:= 1    
           <math>D[i, j]:=</math> minimum(
              D[i-1, j  ] + 1,                 ''// effacement du nouveau caractère de chaine1''
              D[i,   j-1] + 1,                 ''// insertion dans chaine2 du nouveau caractère de chaine1''
              D[i-1, j-1] + coûtSubstitution   ''// substitution''
           )
  
    '''renvoyer''' D[longueurChaine1, longueurChaine2]

L’[[invariant]] est qu’on peut transformer le segment initial <code>chaine1[1..i]</code> en <code>chaine2[1..j]</code> en utilisant un nombre minimal de <code>D[i, j]</code> opérations. L’algorithme achevé, la solution est contenue dans la dernière position à droite de la rangée du bas de la matrice.

=== Améliorations possibles ===
L’algorithme présenté a une [[Complexité en temps|complexité temporelle]] et [[Complexité en espace|spatiale]] de <math>(m+1)\times(n+1)</math>. En effet, il faut stocker et remplir la matrice en [[Mémoire vive|mémoire]]. Cependant, il est possible d'effectuer le calcul en ne gardant que la ligne précédente et la ligne actuelle en mémoire, ce qui réduit la quantité de mémoire utilisée à <math>O(m)</math> [[Comparaison asymptotique#La famille de notations de Landau O, o, Ω, ω, Θ, ~|asymptotiquement]].

D’autre part, il est aussi possible d’expliciter les suites d'opérations permettant de réellement passer d’une chaîne à l'autre. Une fois le calcul effectué, on peut obtenir ces suites en partant de la cellule en bas à droite et en remontant de cellule en cellule en prenant à chaque fois la ou les cellules à l’origine de la valeur minimum. Plusieurs cellules pouvant être à l’origine de cette valeur minimum, aussi plusieurs chemins peuvent être déduits, ils sont tous de longueur minimum. Ce processus permet par exemple d’apparier les caractères de <math>a</math> avec ceux de <math>b</math>.

Des [[Mise en œuvre|implémentations]] plus complexes mais plus performantes existent<ref>[http://angusj.com/delphi/textdiff.html Implémentation en O(NP) sous Delphi] Angus Johnson.</ref>. Par exemple celle de Myers<ref>[http://www.springerlink.com/content/l32685xq65223882/ An O(ND) Difference Algorithm and its Variations] E Myers - ''[[Algorithmica]]'' Vol. 1 No. 2, 1986, {{p.|251-266}}.</ref> dont le coût est en <math>O(nD)</math> avec <math>D</math> la distance trouvée ; et surtout celle de Wu, Manber et Myers<ref>[http://portal.acm.org/citation.cfm?id=96223 An O(NP) Sequence Comparison Algorithm] Sun Wu, Udi Manber & Gene Myers.</ref> en <math>O(nP)</math> avec <math>P=D/2-(n-m)/2</math>.

== Exemple de déroulement de l'algorithme ==
Pour comprendre le fonctionnement de l'[[Algorithmique|algorithme]] Wagner et Fischer, prenons un exemple :

Soit chaine1 = « NICHE ».<br />Soit chaine2 = « CHIENS ».

On veut transformer « NICHE » en « CHIENS » avec un coût minimal.

=== Intuition ===
Intuitivement, on voit que l'on peut transformer chaine1 en chaine2 en 5 étapes :
* Suppression de N et I → CHE ;
* Insertion de I, N et S → CHIENS.

{|class="wikitable"
|-
| style="background: orange; color: black;"|  N
| style="background: orange; color: black;"|  I
| style="background: gray; color: black;"|C 
| style="background: gray; color: black;"|H 
!
| style="background: gray; color: black;"|E 
! !!
|-
!  !!    
| style="background: gray; color: black;"| C 
| style="background: gray; color: black;"|H 
| style="background: lightgreen; color: black;"| I 
| style="background: gray; color: black;"|E 
| style="background: lightgreen; color: black;"| N 
| style="background: lightgreen; color: black;"| S
|}

* {{Carré couleur|orange}} effacement
* {{Carré couleur|lightgreen}} insertion
* {{Carré couleur|gray}} substitution


La distance de Levenshtein entre les chaînes de caractères « NICHE » et « CHIENS » est donc d'au plus 5. On peut se convaincre par l'expérience que 5 est effectivement la distance entre les deux chaînes (l'algorithme de la distance de Levenshtein ne s'occupe pas de déplacement, il ne sait détecter que la suppression ou l'insertion d'une lettre, ainsi que le remplacement d'une lettre par une autre). Pour le vérifier formellement, on peut appliquer l'algorithme (ou tout essayer manuellement).

=== Fonctionnement ===

Soit n = 5, la longueur de la chaîne1 « NICHE ». Soit m = 6, la longueur de la chaîne2 « CHIENS ». On construit une matrice D de n+1 lignes et m+1 colonnes. On initialise la première ligne par la matrice ligne [0, 1, …, m - 1, m] et la première colonne par la matrice colonne [0, 1, ..., n - 1, n].
{|class="wikitable"
|+ Matrice D initiale
!   !!   !! C !! H !! I !! E !! N !! S
|- style="background: yellow; color: black;"
|   || 0 || 1 || 2 || 3 || 4 || 5 || 6
|-
! N
| style="background: yellow; color: black;" |1 || 0 || 0 || 0 || 0 || 0 || 0
|-
! I
| style="background: yellow; color: black;" |2 || 0 || 0 || 0 || 0 || 0 || 0
|-
! C
| style="background: yellow; color: black;" |3 || 0 || 0 || 0 || 0 || 0 || 0
|-
! H
| style="background: yellow; color: black;" |4 || 0 || 0 || 0 || 0 || 0 || 0
|-
! E
| style="background: yellow; color: black;" |5 || 0 || 0 || 0 || 0 || 0 || 0
|}

Soit <code>Cout[i, j] = 0</code> si <code>a[i] = b[j]</code> et <code>Cout[i, j] = 1</code> si <code>a[i] != b[j]</code>. C'est le coût de substitution. On a donc ici la matrice Cout :
{|class="wikitable"
|+ Matrice Cout
!   !!  style="background: pink; color: black;"| C 
! style="background: lightblue; color: black;"| H 
! style="background: wheat; color: black;"| I
! style="background: yellow; color: black;"|E 
! style="background: RosyBrown; color: black;"|N 
! S
|-
! style="background: RosyBrown; color: black;"|N
| 1 || 1 || 1 || 1 || style="background: RosyBrown; color: black;"|0 || 1
|-
! style="background: wheat; color: black;"|I
| 1 || 1 || style="background: wheat; color: black;"|0 || 1 || 1 || 1
|-
! style="background: pink; color: black;"|C
| style="background: pink; color: black;"|0 || 1 || 1 || 1 || 1 || 1
|-
! style="background: lightblue; color: black;"|H
| 1 || style="background: lightblue; color: black;"|0 || 1 || 1 || 1 || 1
|-
! style="background: yellow; color: black;"|E
| 1 || 1 || 1 || style="background: yellow; color: black;"|0 || 1 || 1
|}

On remplit ensuite la matrice D en utilisant la règle suivante&nbsp;
<code>D[i, j]</code> est égale au minimum entre les éléments suivants :
* {{Carré couleur|orange}} L’élément directement au-dessus et on ajoute 1 (effacement) : <code>D[i-1, j] + 1</code>.
* {{Carré couleur|lightgreen}} L’élément directement avant et on ajoute 1 (insertion) : <code>D[i, j-1] + 1</code>.
*  {{Carré couleur|gray}} L’élément diagonal précédent et on ajoute le coût (substitution) : <code>D[i-1, j-1] + Cout[i-1, j-1]</code>.

Attention ! Il s'agit de <code>Cout[i-1, j-1]</code> et non de <code>Cout[i, j]</code> car la matrice Cout est moins grande que la matrice D, ce qui entraîne un décalage.

Dans notre cas, le remplissage de la première ligne donne alors :
{|class="wikitable"
|+ Matrice D
!   !!   !! C !! H !! I !! E !! N !! S
|-
|   || 0 || 1 || 2 || 3 || 4 || 5 || 6
|- style="background: yellow; color: black;"
! N
| 1 || 1 || 2 || 3 || 4 || 4 || 5
|-
! I
| 2 || 0 || 0 || 0 || 0 || 0 || 0
|-
! C
| 3 || 0 || 0 || 0 || 0 || 0 || 0
|-
! H
| 4 || 0 || 0 || 0 || 0 || 0 || 0
|-
! E
| 5 || 0 || 0 || 0 || 0 || 0 || 0
|}

Nous réitérons cette opération jusqu'à remplir la matrice :
{|class="wikitable"
|+ Matrice D
! colspan="1" rowspan="2" style="border: none; background: none;"|[[File:Pfeil_SO.svg|none|link=|20px]]
!      !! C !! H 
! style="background: lightgreen; color: black;"| I 
! E 
! style="background: lightgreen; color: black;"| N 
! style="background: lightgreen; color: black;"| S
|-
|    0 || 1 || 2 || 3 || 4 || 5 || 6
|-
! style="background: orange; color: black;"|  N
| style="background: orange; color: black;"| ''' {{info|1|supprimer 'N'}}''' || 1 || 2 || 3 || 4 || 4 || 5
|- style="background: yellow; color: black;"
! style="background: orange; color: black;"|  I
| style="background: orange; color: black;"| ''' {{info|2|supprimer 'I'}}''' || 2 || 2 || 2 || 3 || 4 || 5
|- style="background: yellow; color: black;"
! C
| 3 || style="background: gray; color: black;"|  ''' {{info|2|'C' égal 'C'}}'''  || 3 || 3 || 3 || 4 || 5
|- style="background: yellow; color: black;"
! H
| 4 || 3 || style="background: gray; color: black;"| '''{{info|2|'H' égal 'H'}}''' 
| style="background: lightgreen; color: black;"| '''{{info|3|ajouter 'I'}}''' || 4 || 4 || 5
|- style="background: yellow; color: black;"
! E
| 5 || 4 || 3 || 3 || style="background: gray; color: black;"| '''{{info|3|'E' égal 'E'}}'''  
| style="background: lightgreen; color: black;"| '''{{info|4|ajouter 'N'}}''' 
| style="background: lightgreen; color: black;"| '''{{info|5|ajouter 'S'}}'''
|}

La distance de Levenshtein entre les 2 chaînes est en <code>D[n, m]</code>, c'est-à-dire en bas à droite. On retrouve bien les 5 opérations trouvées de manière intuitive.

La matrice D fournit aussi explicitement les suites d'opérations possibles permettant de passer d'une chaîne de caractères à l'autre (Il existe ici 6 suites possibles). On part du 5 en bas à droite et on examine les trois cases du quartier supérieur gauche ; (4,4,5) dans le sens d'une montre. On suit la ou les valeurs minimums. Ici on a deux 4 qui donnent donc deux chemins (une bifurcation), et ainsi de suite on crée un arbre par récurrence. Aller au-dessus s’interprète comme ''détruire la lettre de la ligne'';  aller en diagonale est ''substituer la lettre de la ligne par la lettre de la colonne'' (ou pas si elles sont égales) ; aller à gauche est ''ajouter la lettre de la colonne''. Bien sûr à la fin, il faut lire les étapes à l'envers.

== Généralisation et autres distances ==
En remplaçant chaîne de caractères par séquence de symboles, les symboles étant comparables par un opérateur d'égalité, on peut définir une distance d'édition fonctionnant sur d'autres types que des chaînes de caractères.

On peut citer d'autres distances similaires : la [[distance de Damerau-Levenshtein]], la [[distance de Hamming]], la [[distance d'édition sur les arbres]], la [[distance de Jaro-Winkler]] et la [[Indice et distance de Jaccard|distance de Jaccard]].

== Notes et références ==
{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[diff]]
* [[TF-IDF]]
* [[Algorithme de Wagner-Fischer]]
*[[Distance de Damerau-Levenshtein]]

=== Liens externes ===
* [http://sourceforge.net/projects/levenshtein/ Levenshtein project on sourceforge] : une implémentation des distances de Levenshtein et Damerau
* {{Note autre projet|wikibooks|Algorithm Implementation/Strings/Levenshtein distance|langue=en|rôle=lien externe}} : implémentation en plusieurs langages de programmation

{{Palette Algorithmes de manipulation de texte}}
{{Portail|informatique théorique|mathématiques}}

[[Catégorie:Distance remarquable|Levenshtein]]
[[Catégorie:Théorie des codes]]