TD 8 et TP 7

Universit´e d’Aix-Marseille
Algorithmique
L2 Informatique et Math´ematiques - 2014/2015
TD 8 et TP 7
Ce TP est consacr´e au calcul de la distance d’´edition entre deux chaˆınes de caract`eres.
´
Etant
donn´ee une chaˆıne de caract`ere s comprenant l caract`eres, on consid`ere les trois op´erations
suivantes :
– Sup(s,i) qui supprime le i-`eme caract`ere de s (on doit avoir 1 ≤ i ≤ l),
– Ins(s,i,c) qui ins`ere le caract`ere c `a la position i (on doit avoir 1 ≤ i ≤ l+1) ; les caract`eres
suivants, s’il y en a, sont d´ecal´es d’un cran,
– Mut(s,i,c) qui transforme le i-`eme caract`ere de s en c (on doit avoir 1 ≤ i ≤ l).
Exemples :
s
chat
chat
chat
chat
Op´
eration
Sup(s,2)
Ins(s,1,’a’)
Ins(s,5,’s’)
Mut(s,4,’r’)
R´esultat
cat
achat
chats
char
La distance d’´edition d(s1 , s2 ) entre deux chaˆınes s1 et s2 est le plus petit nombre d’op´erations
permettant de transformer s1 en s2 . Puisqu’on peut d’abord supprimer tous les caract`eres de s1
puis ins´erer tous les caract`eres de s2 , on a d(s1 , s2 ) ≤ |s1 | + |s2 | o`
u |s| d´esigne la longueur d’une
chaˆıne s.
Par exemple, on a
Ins(1,r)
Ins(2,i)
M ut(5,e)
Sup(6)
chat −→ rchat −→ richat −→ richet −→ riche
On peut d´emontrer que cette suite d’op´erations est minimale : la distance entre chat et riche est
donc ´egale `
a 4.
Pour calculer la distance d’´edition entre deux chaˆınes de caract`eres s1 et s2 , on consid`ere la
fonction d(i, j) `
a valeurs enti`eres et d´efinie pour 0 ≤ i ≤ |s1 | et 0 ≤ j ≤ |s2 | par
1. d(0, j) = j pour tout j,
2. d(i, 0) = i pour tout i,
3. d(i, j) = M in{d(i − 1, j) + 1, d(i, j − 1) + 1, d(i − 1, j − 1) + e} si i, j ≥ 1,
1 si s1 [i] 6= s2 [j]
o`
ue=
0 sinon.
On peut montrer que d(i, j) calcule la distance d’´edition entre le mot compos´e des i premiers
caract`eres de s1 et le mot compos´e des j premiers caract`eres de s2 :
– le cas 1. correspond `
a j insertions dans une chaˆıne vide,
– le cas 2. correspond `
a i suppressions,
– le cas 3. recherche si la derni`ere op´eration ´el´ementaire doit plutˆot ˆetre une insertion, une
suppression ou une mutation.
Pour calculer la distance d’´edition entre s1 et s2 , il suffit donc de calculer la valeur de d pour
i = |s1 | et j = |s2 |.
Si l’on programme la fonction d en suivant sa d´efinition r´ecursive, des calculs identiques seront
ex´ecut´es plusieurs fois. On pr´ef`ere cr´eer un tableau de dimension (|s1 | + 1) × (|s2 | + 1) et le remplir
syst´ematiquement `
a partir des relations r´ecursives d´efinissant d. En C, on supposera pour simplifier
que les chaˆınes trait´ees ont une longueur inf´erieure `a la constante LMAX et l’on d´efinira une variable
globale int d[LMAX][LMAX] dont seules les cases (i, j) v´erifiant 0 ≤ i ≤ |s1 | et 0 ≤ j ≤ |s2 | seront
remplies. On rappelle que la longueur d’une chaˆıne s est calcul´ee par la fonction strlen(s).
1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* les cha^
ınes trait´
ees ont une longueur < LMAX */
#define LMAX 50
/* tableau des distances entre pr´
efixes de s1 et s2 */
int d[LMAX][LMAX];
/* remplit les cases (i,j) v´
erifiant 0<=i<= strlen(s1) et 0<=j<= strlen(s2) */
void remplir(char s1[], char s2[]){
...
}
/* calcule la distance d’´
edition entre la cha^
ıne s1 et la cha^
ıne s2 */
int distance(char s1[], char s2[]){
...
}
/* affiche les cases (i,j) v´
erifiant 0<=i<= n1 et 0<=j<= n2 */
void afficherTableau(int n1, int n2){
...
}
int main(void){
char s1[LMAX],s2[LMAX];
printf("Cha^
ıne 1 :");
scanf("%s",s1);
printf("Cha^
ıne 2 :");
scanf("%s",s2);
remplir(s1,s2);
afficherTableau(strlen(s1),strlen(s2));
printf("%d \n",distance(s1,s2));
}
´
1. Ecrivez
les fonctions remplir et afficherTableau.
2. Affichez le tableau pour les mots durite et carie. Entourez les cases correspondant `a une
suite d’op´erations minimale.
3. Utilisez la fonction remplir pour ´ecrire la fonction distance
4. Quelle est la distance entre Constantinople et Cotentin ?
5. On suppose maintenant que les op´erations ont des coˆ
uts distincts : 1 pour une suppression, 2
pour une mutation et 3 pour une insertion. Les coˆ
uts des op´erations ´el´ementaires s’ajoutent
et la distance entre deux chaˆınes est le coˆ
ut minimal d’une suite d’op´erations permettant de
passer de la premi`ere `
a la seconde. Ecrivez les variantes des fonctions remplir et distance
qui tiennent compte de ces coˆ
uts.
´
6. Ecrivez la fonction cheminMinimal(char s1[], char s2[]) qui affiche une suite d’op´erations
de coˆ
ut minimal permettant de passer de s1 `a s2.
2

Download Report