La distance d'édition

 

La distance séparant deux chaînes de caractères peut être vue comme le nombre minimum de transformations élémentaires à appliquer à une chaîne pour obtenir la deuxième (cf. [Wagner et Fisher1974], et algorithme 2). Chaque transformation se voit affecter un coût, et on cherche la suite de transformations qui donne le coût le plus faible. Ces transformations élémentaires sont :

• la suppression (S) ;
• l'insertion (I);
• le changement (C).

 Algorithme: 2 distance d'édition de la chaîne X à la chaine Y (WAGNER et FISCHER).
Pré-requis : D (0,0)=0
Pré-requis : n = longueur de la chaîne X
Pré-requis : m = longueur de la chaîne Y
Pré-requis : C(a,b) = coût de la transformation pour passer de a à b
Pré-requis : lambda = vide
Assure : D (m,n) = distance d'édition de X à Y   Pour i = 0...n Faire
    Pour j = 0...m Faire
      Si i != j != 0 Alors
        D (i,j) = Min (D (i-1, j-1) + C (X_i, Y_j), D (X_i, lambda), D (i, j-1) + C (lambda, Y_i))
      Fin Si
    Fin Pour
  Fin Pour

Milgram [Milgram1993] donne comme exemple la transformation de aabcb en ababd. La figure 4.15 donne quelques-uns des chemins permettant de passer de aabcb à ababd. En prenant un coût de 1 pour chacune des transformations, la distance d'édition de aabcb à ababd est de trois. Elle serait différente si le coût d'une suppression était de 0,5, celui d'une insertion de 0,75 et celui d'un changement de 0,25. Sa valeur serait alors de 1,5.

  

Figure: Quelques-uns des chemins les plus courts permettant de passer de aabcb à ababd.

Nous avons choisi, pour notre application, de donner un coût de 0,6 à chacune de ces transformations, sauf dans certains cas de changement (C). Quand une majuscule doit être changée en sa minuscule, ou l'inverse, le coût de la transformation est de 0,1. Nous considérons alors que ce sont presque les mêmes caractères. En effet, il arrive qu'un symbole commençant par une majuscule dans la base de références soit traduit en un symbole commençant par une minuscule, c'est pour éviter les problèmes de ce genre que nous avons introduit ce coût. Quand on doit changer une lettre en une autre lettre (et pas en un caractère de ponctuation, ou autre), ce coût est fixé à 0.9. Lorsque l'on doit changer un chiffre a en un autre chiffre b, le coût est de 6 x |a-b| / 100. Ainsi, ce coût varie entre 0 (quand a = b) et 0,54 en fonction de la distance mathématique des deux chiffres. C'est utile lorsqu'un opérateur a fait une faute de frappe, mais surtout lorsqu'un agent recherche un nombre de même longueur, mais pas exactement de même valeur. Un exemple typique est la recherche d'une année : il est possible que l'année de la référence n'existe pas dans le Réseau de Concepts, mais il est tout-de-même utile que celle-ci soit reconnue comme une année, c'est-à-dire comme une proche voisine d'une année du Réseau de Concepts.

La distance d entre deux chaînes a et b permet facilement de calculer le taux de similarité s(a,b) en fonction aussi de leurs longueurs (l (a) et l (b)) : s(a,b) = (1-d(a,b)) / MAX(l(a), l(b)).