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{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \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}

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 \R^+ la fonction coût définie comme suit :

(1)#\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 :

(2)#\begin{eqnarray} \begin{array}{crcl} d : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \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 :

(4)#\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} dpa{m_1,m_3} infegal dpa{m_1,m_2} + d pa{m_2,m_3} label{edit_demo_eq_3} end{eqnarray}

Les assertions 1, 2, 3 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 :

(5)#\begin{eqnarray*} \begin{array}{crcl} d' : & \mathcal{S}_\mathcal{C} \times \mathcal{S}_\mathcal{C} & \longrightarrow & \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 :

\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)

Par :

\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.

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.

Cette factorisation des calculs est illustrée par les tableaux de cette figure. 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.