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.

distance d’édition

mot 1	mot 2	opération	coût
i	d	comparaison entre i et d	1
d	i	comparaison entre d et i	1
s	s	comparaison entre s et s	0
t	t	comparaison entre t et t	0
z		suppression de z	1
a	a	comparaison entre a et a	0
n	n	comparaison entre n et n	0
c	c	comparaison entre c et c	0
e	e	comparaison entre e et e	0
	s	insertion de s	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 \(\mathcal{C}\) l’espace des caractères ou des symboles. Un mot ou une séquence est une suite finie de \(\mathcal{C}\). On note \(\mathcal{S}_\mathcal{C} = \cup_{k=1}^{\infty} C^k\) l’espace des mots formés de caractères appartenant à \(\mathcal{C}\).

On peut définir la distance d’édition :

Définition D2 : distance d’édition

La distance d’édition \(d\) sur \(\mathcal{S}_\mathcal{C}\) est définie par :

\[\begin{split}\begin{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & \underset{ \begin{subarray} OO \text{ séquence} \\ \text{d'opérations} \end{subarray}}{ \min} \, d\pa{m_1,m_2,O} \end{array}\end{split}\]

La distance est le coût de la transformation du mot \(m_1\) en \(m_2\) 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 \(\mathcal{C}' = \mathcal{C} \bigcup \acc{.}\) l’ensemble des caractères ajouté au caractère vide .. On note \(c : \pa{\mathcal{C}'}^2 \longrightarrow \mathbb{R}^+\) la fonction coût définie comme suit :

\begin{eqnarray*} \forall \pa{x,y} \in \pa{\mathcal{C}'}^2, \; c\pa{x,y} \text{ est le coût } \left\{ \begin{array}{ll} \text { d'une comparaison} & \text{si } \pa{x,y} \in \pa{\mathcal{C}}^2\\ \text { d'une insertion} & \text{si } \pa{x,y} \in \pa{\mathcal{C}} \times \acc{.}\\ \text { d'une suppression} & \text{si } \pa{x,y} \in \acc {.} \times \pa{\mathcal{C}} \\ 0 & \text{si } \pa{x,y} = \pa{\acc{.},\acc{.}} \end{array} \right. \end{eqnarray*}

On note \(\mathcal{S}_\mathcal{C'}^2 = \cup_{n=1}^{\infty} \pa{\mathcal{C'}^2}^n\) l’ensemble des suites finies de \(\mathcal{C'}\).

Pour modéliser les transformations d’un mot vers un autre, on définit pour un mot \(m\) un mot acceptable :

Définition D4 : mot acceptable

Soit \(m = \vecteur{m_1}{m_n}\) un mot tel qu’il est défini précédemment. Soit \(M=\pa{M_i}_{i \supegal 1}\) une suite infinie de caractères, on dit que \(M\) est un mot acceptable pour \(m\) si et seulement si la sous-suite extraite de \(M\) contenant tous les caractères différents de \(\acc{.}\) est égal au mot \(m\). On note \(acc\pa{m}\) l’ensemble des mots acceptables pour le mot \(m\).

Par conséquent, tout mot acceptable \(m'\) pour le mot \(m\) est égal à \(m\) si on supprime les caractères \(\acc{.}\) du mot \(m'\). En particulier, à partir d’un certain indice, \(m'\) est une suite infinie de caractères \(\acc{.}\). Il reste alors à exprimer la définition de la distance d’édition en utilisant les mots acceptables :

Définition D5 : distance d’édition

Soit \(c\) la distance d’édition, \(d\) définie sur \(\mathcal{S}_\mathcal{C}\) est définie par :

\begin{eqnarray} \begin{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & \min \acc{ \sum_{i=1}^{+\infty} c\pa{M_1^i, M_2^i} | \pa{M_1,M_2} \in acc\pa{m_1} \times acc\pa{m_2}} \end{array} \end{eqnarray}

Il est évident que la série \(\sum_{i=1}^{+\infty} c\pa{M_1^i, M_2^i}\) 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 \(c\) et \(d\) les fonctions définies respectivement par (1) et (2), alors :

\(c\) est une distance sur \(\mathcal{C} \Longleftrightarrow d\) est une distance sur \(\mathcal{S}_\mathcal{C}\)

On cherche d’abord à démontrer que

\(c\) est une distance sur \(\mathcal{C}' \Longleftarrow d\) est une distance sur \(\mathcal{S}_\mathcal{C}\)

Cette assertion est évidente car, si \(\pa{m_1,m_2}\) sont deux mots de un caractère, la distance \(d\) sur \(\mathcal{S}_\mathcal{C}\) définit alors la distance \(c\) sur \(\mathcal{C}'\).

On démontre ensuite que :

\(c\) est une distance sur \(\mathcal{C}' \Longrightarrow d\) est une distance sur \(\mathcal{S}_\mathcal{C}\)

Soient deux mots \(\pa{m_1,m_2}\), soit \(\pa{M_1,M_2} \in acc\pa{m_1} \times acc\pa{m_2}\), comme \(c\) est une distance sur \(\mathcal{C}'\) alors \(d\pa{M_1,M_2} = d\pa{M_2,M_1}\).

D’où, d’après la définition 2 :

(3)\[d\pa{m_1,m_2} = d\pa{m_2,m_1}\]

Soit \(\pa{N_1,N_2} \in acc\pa{m_1} \times acc\pa{m_2}\) tels que \(d\pa{m_1,m_2} = d\pa{N_2,N_1}\) alors :

\begin{eqnarray*} d\pa{m_1,m_2} = 0 & \Longrightarrow & d\pa{N_1,N_2} = 0 \\ & \Longrightarrow & \sum_{i=1}^{+\infty} c\pa{N_1^i, N_2^i} = 0 \\ & \Longrightarrow & \forall i \supegal 1, \; N_1^i = N_2^i \\ & \Longrightarrow & N_1 = N_2 \\ d\pa{m_1,m_2} = 0 & \Longrightarrow & m_1 = m_2 \end{eqnarray*}

Il reste à démontrer l’inégalité triangulaire. Soient trois mots \(\pa{m_1,m_2,m_3}\), on veut démontrer que \(d\pa{m_1,m_3} \infegal d\pa{m_1,m_2} + d \pa{m_2,m_3}\). On définit :

\begin{eqnarray*} \pa{N_1,N_2} \in acc\pa{m_1} \times acc\pa{m_2} & \text{ tels que } & d\pa{m_1,m_2} = d\pa{N_1,N_2} \\ \pa{P_2,P_3} \in acc\pa{m_2} \times acc\pa{m_3} & \text{ tels que } & d\pa{m_2,m_3} = d\pa{P_2,P_3} \\ \pa{O_1,O_3} \in acc\pa{m_1} \times acc\pa{m_3} & \text{ tels que } & d\pa{m_1,m_3} = d\pa{O_1,O_3} \end{eqnarray*}

Mais il est possible, d’après la définition d’un mot acceptable d’insérer des caractères \(\acc{.}\) dans les mots \(N_1,N_2,P_2,P_3,O_1,O_3\) de telle sorte qu’il existe \(\pa{M_1,M_2,M_3} \in acc\pa{m_1} \times \in acc\pa{m_2} \times \in acc\pa{m_3}\) tels que :

\begin{eqnarray*} d\pa{m_1,m_2} = d\pa{M_1,M_2} \\ d\pa{m_2,m_3} = d\pa{M_2,M_3} \\ d\pa{m_1,m_3} = d\pa{M_1,M_3} \end{eqnarray*}

Or comme la fonction \(c\) est une distance sur \(\mathcal{C}'\), on peut affirmer que : \(d\pa{M_1,M_3} \infegal d\pa{M_1,M_2} + d \pa{M_2,M_3}\). D’où :

\begin{eqnarray*} d\pa{m_1,m_3} \infegal d\pa{m_1,m_2} + d \pa{m_2,m_3} \end{eqnarray*}

Les assertions (3), (4), (5) montrent que \(d\) est bien une distance. Le tableau suivant illustre la démonstration pour les suites \(M_1,M_2,M_3\) pour les mots et les mots idtzance, tonce, distances.

\(M_1\)	i	d		t	z	a	n	c	e
\(M_2\)				t		o	n	c	e
\(M_3\)	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 \(d'\) sur \(\mathcal{S}_\mathcal{C}\) est définie par :

\begin{eqnarray*} \begin{array}{crcl} d' : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \mathbb{R}^+\\ & \pa{m_1,m_2} & \longrightarrow & d'\pa{m_1,m_2} = \dfrac{d^*\pa{m_1,m_2}}{ \max \acc {l\pa{m_1}, l\pa{m_2}}} \\ \\ & & & \text{où } l\pa{m} \text{ est la longueur du mot } m \end{array} \end{eqnarray*}

Le tableau suivant donne un exemple pour lequel l’inégalité triangulaire n’est pas vérifiée. La fonction \(d^*\) n’est donc pas une distance.

mot 1	mot 2	distance : \(d^*\)	distance \(d'\)
APPOLLINE	APPOLINE	1	1 / 9
APPOLLINE	APOLLINE	1	1 / 9
APOLLINE	APPOLINE	2	2 / 8

Par conséquent : \(d\pa{APOLLINE,APPOLINE} > d\pa{APOLLINE,APPOLLINE} + d\pa{APPOLLINE,APPOLINE}\) et la la fonction \(d^*\) 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 \(\pa{m_1,m_2}\), on définit la suite :

\[\begin{split}\left( d_{i,j}^{m_{1},m_{2}}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\left( =\left(d_{i,j}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\text{ pour ne pas alourdir les notations}\right)\end{split}\]

Par :

\[\begin{split}\left\{ \begin{array}[c]{l}% d_{0,0}=0\\ d_{i,j}=\min\left\{ \begin{array}{lll} d_{i-1,j-1} & + & \text{comparaison} \left( m_1^i,m_2^j\right), \\ d_{i,j-1} & + & \text{insertion} \left( m_2^j\right), \\ d_{i-1,j} & + & \text{suppression} \left( m_1^i\right) \end{array} \right\}% \end{array} \right.\end{split}\]

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 \(d\left( m_{1},m_{2}\right) =d_{n_{1},n_{2}}\) où \(d\) 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 \(\pa{m_1,m_2}\) de longueur \(\pa{l_1,l_2}\) vérifiant \(l_1 \infegal i\) et l_2 infegal j avec au plus une égalité. Soit \(m\) un mot, on note \(n\) le nombre de lettres qu’il contient. On note \(m\left( l\right)\) le mot formé des \(l\) premières lettres de \(m\). Alors :

\begin{eqnarray*} d_{i,j}^{m_{1},m_{2}} &=& d\left( m_{1}\left( i\right) ,m_{2}\left( j\right) \right)\\ d\left( m_{1}\left( i\right) ,m_{2}\left( j\right) \right) &=& \min\left\{ \begin{array}{lll}% d\left( m_{1}\left( i-1\right) ,m_{2}\left( j-1\right) \right) & + & \text{comparaison}\left( m_{1,i},m_{2,j}\right), \\ d\left( m_{1}\left( i\right) ,m_{2}\left( j-1\right) \right) & + & \text{insertion}\left( m_{2,j}\right), \\ d\left( m_{1}\left( i-1\right) ,m_{2}\left( j\right) \right) & + & \text{suppression}\left( m_{1,i}\right) \end{array} \right\} \end{eqnarray*}

Le calcul factorisé de la distance d’édition entre deux mots de longueur \(l_1\) et \(l_2\) a un coût de l’ordre \(O\pa{l_1 l_2}\). 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.

\[\begin{split}\begin{array}{c} \begin{array}{ccc}% \begin{array}{cc}% \searrow & \\ \text{dans ce sens,} \\ \text{c'est une } \\ \text{comparaison}% \end{array} & \begin{array}{c}% \longrightarrow j\\ \text{dans ce sens, c'est une insertion}% \end{array} & \\% \begin{array}{ll}% & \text{dans ce sens,}\\ \downarrow & \text{c'est une}\\ i & \text{suppression}% \end{array} & \begin{array}{ccccccccccc}% & & d & i & s & t & a & n & c & e & s\\ & 0 & & & & & & & & & \\ i & & 1 & & & & & & & & \\ d & & & 2 & & & & & & & \\ s & & & & 2 & & & & & & \\ t & & & & & 2 & & & & & \\ z & & & & & 3 & & & & & \\ a & & & & & & 3 & & & & \\ n & & & & & & & 3 & & & \\ c & & & & & & & & 3 & & \\ e & & & & & & & & & 3 & 4 \end{array} & \begin{array}{ccccccccccc}% & & d & i & s & t & a & n & c & e & s\\ & 0 & & & & & & & & & \\ i & 1 & & & & & & & & & \\ d & 2 & 3 & 4 & & & & & & & \\ s & & & & 4 & & & & & & \\ t & & & & & 4 & & & & & \\ z & & & & & 5 & & & & & \\ a & & & & & & 5 & 6 & 7 & & \\ n & & & & & & & & 8 & & \\ c & & & & & & & & 9 & & \\ e & & & & & & & & & 9 & 10 \end{array} \end{array} \end{array}\end{split}\]

Chaque case \(\pa{i,j}\) contient la distance qui sépare les \(i\) premières lettres du mot \(1\) des \(j\) premières lettres du mot \(2\) 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 \(\pa{m_1,m_2}\), on définit la suite :

\[\begin{split}\left( d_{i,j}^{m_{1},m_{2}}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\left( =\left(d_{i,j}\right) _{\substack{0\leqslant i\leqslant n_{1}\\0\leqslant j\leqslant n_{2}}}\text{ pour ne pas alourdir les notations}\right)\end{split}\]

par :

\[\begin{split}\left\{ \begin{array}[c]{l}% d_{0,0}=0\\ d_{i,j}=\min\left\{ \begin{array}{lll} d_{i-1,j-1} & + & \text{comparaison} \pa{m_1^i,m_2^j}, \\ d_{i,j-1} & + & \text{insertion} \pa{m_2^j,i}, \\ d_{i-1,j} & + & \text{suppression} \pa{m_1^i,j}, \\ d_{i-2,j-2} & + & \text{permutation} \pa{ \pa{m_1^{i-1}, m_1^i},\pa{m_2^{j-1}, m_2^j}} \end{array} \right\}% \end{array} \right.\end{split}\]

La distance d’édition cherchée est toujours \(d\pa{m_1,m_2} = d_{n_1,n_2}\) mais la démonstration du fait que \(d\) 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 \(\Theta = \vecteur{\theta_1}{\theta_n}\). On considère deux mots \(X\) et \(Y\), la distance d’édition \(d\pa{X,Y}\) est une fonction linéaire des coûts. Soit \(D = \vecteur{\pa{X_1,Y_1}}{\pa{X_N,Y_N}}\) une liste de couple de mots pour lesquels le résultat de la distance d’édition est connu et noté \(\vecteur{c_1}{c_N}\), il est alors possible de calculer une erreur s’exprimant sous la forme :

\begin{eqnarray*} E = \sum_{i=1}^{N} \; \pa{d\pa{X_i,Y_i} - c_i}^2 =\sum_{i=1}^{N} \; \pa{ \sum_{k=1}^{n} \alpha_{ik}\pa{\Theta} \, \theta_k - c_i}^2 \\ \end{eqnarray*}

Les coefficients \(\alpha_{ik}\pa{\Theta}\) dépendent des paramètres \(\Theta\) 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>`, \(\alpha_{ik}\pa{\Theta}\) correspond au nombre de fois que le paramètre \(\theta_k\) intervient dans la transformation de moindre coût entre \(X_i\) et \(Y_i\). Cette expression doit être minimale afin d’optenir les coûts \(\Theta\) optimaux. Toutefois, les coûts \(\theta_k\) 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 :

\begin{eqnarray*} E = \sum_{i=1}^{N} \; \pa{ \sum_{k=1}^{n} \, \alpha_{ik}\pa{\Omega} \, \frac{1}{1 + e^{-\omega_k}} - c_i}^2 \end{eqnarray*}

Les fonctions \(\alpha_{ik}\pa{\Omega}\) ne sont pas dérivable par rapport \(\Omega\) 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 \(\Omega\) sont tirés aléatoirement.

estimation

Les coefficients \(\alpha_{ik}\pa{\Omega}\) sont calculées.

calcul du gradient

Dans cette étape, les coefficients \(\alpha_{ik}\pa{\Omega}\) restent constants. Il suffit alors de minimiser la fonction dérivable \(E\pa{\Omega}\) sur \(\mathbb{R}^n\), 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 \(E\pa{\Omega}\) ne converge pas, on continue. L’erreur E diminue jusqu’à converger puisque l’étape qui réestime les coefficients \(\alpha_{ik}\pa{\Omega}\), les minimise à \(\Omega = \vecteur{\omega_1}{\omega_n}\) constant.

Bibliographie

[Damerau1964]

A technique for computer detection and correction of spelling errors (1964), F. J. Damerau, Commun. ACM, volume 7(3), pages 171-176

[Kripasundar1996]

Generating edit distance to incorporate domain information (1996), V. Kripasunder, G. Seni, R. K. Srihari, CEDAR/SUNY

[Levenstein1966]

Binary codes capables of correctiong deletions, insertions, and reversals (1966), V. I. Levenstein, Soviet Physics Doklady, volume 10(8), pages 707-710

[Seni1996]

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

[Waard1995]

An optimised minimal edit distance for hand-written word recognition (1995), W. P. de Waard, Pattern Recognition Letters volume 1995, pages 1091-1096

[Wagner1974] (1,2)

The string-to-string correction problem (1974), R. A. Wagner, M. Fisher, Journal of the ACM, volume 21, pages 168-178