Université des Sciences et Technologies de Lille
Licence Miage - Programmation 1 - TP


Initiation à la programmation dynamique :
la distance d'édition




On définit sur les mots trois opérations élémentaires : Par exemple, sur le mot carie, si on substitue c en d, a en u et si on insère t après le i, on obtient durite. La distance d'édition entre deux mots U et V est le nombre minimal d'opérations pour passer de U à V. Ainsi, la distance de carie à durite est 3: deux subsitutions et une insertion. La distance de aluminium à albumine est 4: une insertion, b, une substitution, i en e et deux suppressions, u et m.

Une formule de récurrence pour calculer la distance d'édition est
d(., v) = |v| (on fait |v| insertions)
d(u,. ) = |u| (on fait |u| suppressions)
d(ua,va) = d(u,v)
d(ua,vb) = 1+ min(d(u,v),d(ua,v),d(u,vb))
    (la dernière opération est une substitution de a en b,
    ou une insertion de b, ou une suppression de a)

Le symbole . dénote le mot vide.

Question 1   Écrire une fonction récursive Distance qui calcule la distance d'édition de deux chaînes de caractères. Testez-la sur carie et durite, aluminium et albumine, puis sur un couple de mots un peu plus longs.

Le problème de la fonction Distance est qu'elle effectue de nombreux appels récursifs redondants. Cela conduit à une complexité exponentielle. La solution est de stocker les appels récursifs dans une table D de dimension 2, telle que D(i,j) soit la distance de U(U'first..i) à V(V'first..j). On ajoute une colonne et une ligne pour traiter le mot vide. Cela donne finalement une table indexée par U'first-1..U'last et V'first-1..V'last. Le résultat est D(U'last, V'last). Par exemple, en supposant que les chaînes de caractères sont indexées à partir de 1, la table pour carie et durite est

      c a r i e
    0 1 2 3 4 5
  0 0 1 2 3 4 5
d 1 1 1 2 3 4 5
u 2 2 2 2 3 4 5
r 3 3 3 3 2 3 4
i 4 4 4 4 3 2 3
t 5 5 5 5 4 3 3
e 6 6 6 6 5 4 3




Question 2   Écrire une fonction Distance_dynamique qui calcule la distance de deux chaînes de caractères sans appels récursifs, en construisant la table D.

On veut maintenant connaitre la suite d'opérations qui mène de U à V. Pour cela, on peut visualiser les transformations par un petit schéma:
c a r i   e        a l   u m i n i u m
    | |   |   | |   | | | |
d u r i t e   a l b u m i n e  
Deux lettres identiques sont signalées par |. Un espace dans le mot de départ correspond à une insertion, un espace dans le mot d'arrivée correspond à une suppression, et une substitution est représentée par les deux lettres face à face, sans |.

Question 3  *** Écrire une procédure qui prend en arguments deux chaînes de caractères et affiche la suite d'opérations sous la forme décrite ci-dessus. Pour cela, vous devez utiliser la table D et construire l'historique des transformations en remontant dans la table à partir de (U'last,V'last).