Distance d’édition¶
Les distances d’édition permettent de comparer deux mots entre eux ou plus généralement deux séquences de symboles entre elles. L’usage le plus simple est de trouver, pour un mot mal orthographié, le mot le plus proche dans un dictionnaire, c’est une option proposée dans la plupart des traitements de texte. La distance présentée est la distance de Levenshtein (voir [Levenstein1966]) Elle est parfois appelée Damerau Levenstein Matching (DLM) (voir également [Damerau1964]). Cette distance fait intervenir trois opérations élémentaires :
comparaison entre deux caractères
insertion d’un caractère
suppression d’un caractère
Pour comparer deux mots, il faut construire une méthode associant
ces trois opérations afin que le premier mot se transforme en le
second mot. L’exemple suivant utilise les mots idstzance
et distances
,
il montre une méthode permettant de passer du premier au second.
La distance sera la somme des coûts associés à chacune des opérations
choisies. La comparaison entre deux lettres identiques est en général
de coût nul, toute autre opération étant de coût strictement positif.
mot 1 |
mot 2 |
opération |
coût |
---|---|---|---|
i |
d |
comparaison entre |
1 |
d |
i |
comparaison entre |
1 |
s |
s |
comparaison entre |
0 |
t |
t |
comparaison entre |
0 |
z |
suppression de |
1 |
|
a |
a |
comparaison entre |
0 |
n |
n |
comparaison entre |
0 |
c |
c |
comparaison entre |
0 |
e |
e |
comparaison entre |
0 |
s |
insertion de |
1 |
|
somme |
4 |
Pour cette distance d’édition entre les mots idstzance
et distances
.
La succession d’opérations proposée n’est pas la seule qui permettent
de construire le second mot à partir du premier mais c’est la moins coûteuse.
Définition et propriétés¶
Définition¶
Tout d’abord, il faut définir ce qu’est un mot ou une séquence :
Définition D1 : mot
On note l’espace des caractères ou des symboles. Un mot ou une séquence est
une suite finie de
. On note
l’espace des mots formés
de caractères appartenant à
.
On peut définir la distance d’édition :
Définition D2 : distance d’édition
La distance d’édition sur
est définie par :
La distance est le coût de la transformation du mot en
la moins coûteuse.
Il reste à démontrer que cette distance en est bien une
puis à proposer une méthode de calcul plus rapide que celle suggérée par cette définition.
Propriétés¶
Ce paragraphe a pour objectif de démontrer que la distance en est bien une.
Définition D3 : distance entre caractères
Soit
l’ensemble des caractères ajouté au caractère vide
.
.
On note
la fonction coût définie comme suit :
(1)¶
On note
l’ensemble des suites finies de
.
Pour modéliser les transformations d’un mot vers un autre, on définit pour un mot un
mot acceptable :
Définition D4 : mot acceptable
Soit un mot tel qu’il est défini précédemment.
Soit
une suite infinie de caractères, on dit que
est un mot acceptable pour
si et seulement si la sous-suite
extraite de
contenant tous les caractères différents de
est égal au mot
. On note
l’ensemble des mots acceptables pour le mot
.
Par conséquent, tout mot acceptable pour le mot
est égal à
si on supprime les caractères
du mot
. En particulier, à partir d’un certain indice,
est une suite infinie de caractères
. Il reste
alors à exprimer la définition de la distance d’édition
en utilisant les mots acceptables :
Il est évident que la série
est convergente. La :ref`distance de caractères <edition_distance_definition_1>` implique
que les distance d’édition définies en 1
et 2 sont identiques.
Théorème T1 : distance d’édition
Soit et
les fonctions définies respectivement par
(1) et (2), alors :
est une distance sur
est une distance sur
On cherche d’abord à démontrer que
est une distance sur
est une distance sur
Cette assertion est évidente car, si sont deux mots de un caractère,
la distance
sur
définit alors la distance
sur
.
On démontre ensuite que :
est une distance sur
est une distance sur
Soient deux mots ,
soit
,
comme
est une distance sur
alors
.
D’où, d’après la définition 2 :
(3)¶
Soit
tels que
alors :
(4)¶
Il reste à démontrer l’inégalité triangulaire.
Soient trois mots ,
on veut démontrer que
.
On définit :
Mais il est possible, d’après la définition d’un mot acceptable
d’insérer des caractères dans les mots
de telle sorte qu’il existe
tels que :
Or comme la fonction est une distance sur
, on peut affirmer que :
.
D’où :
(5)¶
Les assertions (3), (4), (5)
montrent que est bien une distance. Le tableau suivant
illustre la démonstration pour les suites
pour les mots
et les mots
idtzance
, tonce
, distances
.
i |
d |
t |
z |
a |
n |
c |
e |
|||
t |
o |
n |
c |
e |
||||||
d |
i |
s |
t |
a |
n |
c |
e |
s |
La distance d’édition 2 ne tient pas compte de la longueur des mots qu’elle compare. On serait tenté de définir une nouvelle distance d’édition inspirée de la précédente :
Définition D6 : distance d’édition étendue
Soit d^* la distance d’édition définie en 2
pour laquelle les coûts de comparaison, d’insertion et de suppression
sont tous égaux à 1.
La distance d’édition sur
est définie par :
(6)¶
Le tableau suivant donne un exemple pour lequel l’inégalité triangulaire n’est pas
vérifiée. La fonction n’est donc pas une distance.
mot 1 |
mot 2 |
distance : |
distance |
---|---|---|---|
APPOLLINE |
APPOLINE |
1 |
1 / 9 |
APPOLLINE |
APOLLINE |
1 |
1 / 9 |
APOLLINE |
APPOLINE |
2 |
2 / 8 |
Par conséquent :
et la la fonction
ne vérifie pas l’inégalité triangulaire.
Factorisation des calculs¶
La définition de la distance d’édition ne permet pas d’envisager le calcul de la distance dans un temps raisonnable. Il est possible néanmoins d’exprimer cette distance d’une autre manière afin de résoudre ce problème (voir [Wagner1974]). On définit la suite suivante :
Définition D7 : distance d’édition tronquée
Soient deux mots , on définit la suite :
Par :
Cette suite tronquée permet d’obtenir le résultat de la propriété suivante :
Propriété P1 : calcul rapide de la distance d’édition
La suite définie par 3 vérifie
où
est la distance d’édition définie en 1
ou 2.
La démonstration s’effectue par récurrence, la définition 3
est bien sûr équivalente 1
pour des mots de longueur un. On suppose donc que ce résultat est
vrai pour un couple de mots de longueur
vérifiant
et l_2 leqslant j avec au plus une égalité.
Soit
un mot, on note
le nombre de lettres qu’il contient.
On note
le mot formé des
premières lettres de
.
Alors :
Le calcul factorisé de la distance d’édition entre deux mots de longueur
et
a un coût de l’ordre
.
Il est souvent illustré par un tableau comme celui de la figure suivante
qui permet également de retrouver la meilleure séquence d’opérations permettant
de passer du premier mot au second.
Chaque case contient la distance qui sépare les
premières lettres du mot
des
premières lettres du mot
selon le chemin ou la méthode choisie.
La dernière case indique la distance qui sépare
les deux mots quel que soit le chemin choisi.
Extension de la distance d’édition¶
Jusqu’à présent, seuls trois types d’opérations ont été envisagés pour constuire la distance d’édition, tous trois portent sur des caractères et aucunement sur des paires de caractères. L’article [Kripasundar1996] (voir aussi [Seni1996] suggère d’étendre la définition 3 aux permutations de lettres :
Définition D8 : distance d’édition tronquée étendue
Soit deux mots , on définit la suite :
par :
La distance d’édition cherchée est toujours
mais la démonstration du fait que
est bien une distance ne peut pas
être copiée sur celle du théorème 1
mais sur les travaux présentés dans l’article [Wagner1974].
Apprentissage d’une distance d’édition¶
L’article [Waard1995] suggère l’apprentissage des coûts des opérations
élémentaires associées à une distance d’édition (comparaison, insertion,
suppression, permutation, …). On note l’ensemble de ces coûts ou
paramètres .
On considère deux mots
et
, la distance d’édition
est une fonction linéaire des coûts. Soit
une liste de couple de mots pour lesquels le résultat de la distance
d’édition est connu et noté
, il est alors
possible de calculer une erreur s’exprimant sous la forme :
Les coefficients dépendent des paramètres
car la distance d’édition correspond au coût de la transformation de moindre coût
d’après la définition :ref`2 <defition_distance_edition_2>`,
correspond au nombre de fois que le paramètre
intervient dans la transformation de moindre coût entre
et
. Cette expression doit être minimale afin d’optenir
les coûts
optimaux. Toutefois, les coûts
sont tous
strictement positifs et plutôt que d’effectuer une optimisation sous
contrainte, ces coûts sont modélisés de la façon suivante :
(7)¶
Les fonctions ne sont pas dérivable par rapport
mais il est possible d’effectuer une optimisation sans contrainte
par descente de gradient. Les coûts sont donc appris en deux étapes :
Algorithme A1 : Apprentissage d’une distance d’édition
Les notations sont celles utilisés pour l’équation (7).
Les coûts sont tirés aléatoirement.
estimation
Les coefficients sont calculées.
calcul du gradient
Dans cette étape, les coefficients
restent constants. Il suffit alors de minimiser la fonction
dérivable
sur
, ceci peut être
effectué au moyen d’un algorithme de descente de gradient
similaire à ceux utilisés pour les réseaux de neurones.
Tant que l’erreur ne converge pas, on continue.
L’erreur E diminue jusqu’à converger puisque l’étape qui réestime les coefficients
, les minimise à
constant.
Bibliographie¶
A technique for computer detection and correction of spelling errors (1964), F. J. Damerau, Commun. ACM, volume 7(3), pages 171-176
Generating edit distance to incorporate domain information (1996), V. Kripasunder, G. Seni, R. K. Srihari, CEDAR/SUNY
Binary codes capables of correctiong deletions, insertions, and reversals (1966), V. I. Levenstein, Soviet Physics Doklady, volume 10(8), pages 707-710
Generalizing edit distance to incorporate domain information: handwritten text recognition as a case study (1996), Giovanni Seni, V. Kripasundar, Rohini K. Srihari, Pattern Recognition volume 29, pages 405-414
An optimised minimal edit distance for hand-written word recognition (1995), W. P. de Waard, Pattern Recognition Letters volume 1995, pages 1091-1096