Programmation en binôme : diff
Nous allons continuer notre expérience de programmation à
plusieurs en nous attaquant à un autre problème qui peut
être aisément décomposé. Il s'agira ici de
réécrire (une version simplifiée de) l'utilitaire Unix qui
s'appelle diff
.
Le problème
Il s'agit de comparer deux fichiers A et B et d'afficher les
différences : cette opération est bien pratique pour garder
une trace des modifications sur des fichiers, pour transmettre seulement les
modifications (patches) quand on change de version des sources, pour
garder de façon compacte l'ensemble des différentes versions d'un
document (voyez la page de manuel de rcs
par exemple), etc.
Les différences peuvent être affichées de
différentes façons, mais la plus utile est sous la forme d'un
"edit script", i.e. une séquence de commandes d'éditions ayant
la forme suivante :
- nai,k
- indique qu'à la ligne
n du fichier A, il faut ajouter les lignes i à
k du fichier B.
- n,mci,k
- indique qu'il faut changer
les lignes n à m du fichier A en les remplacant par les
lignes i à k du fichier B.
- n,mdi
- indique qu'il faut supprimer
les lignes n à m du fichier A pour se retrouver aligné
avec la ligne i du fichier B.
Dans tous les cas, les intervalles de longueur 1 sont décrits par un seul
nombre (on écrit i au lieu de i,k si i=k).
Afin d'aider le lecteur humain à comprendre cette suite d'instructions,
on ajoute après chaque commande une description de son effet :
- < x
- indique qu'on vient d'enlever la suite de
caractère x
- > x
- indique qu'on vient d'ajouter la suite de
caractère x
Et pour le changement, on commence par indiquer ce qu'on enlève, puis on
écrit ---
, puis on indique ce qu'on met à la place.
Une propriété intéressante de ces suites de commandes est
qu'il est très facile de déduire les commandes pour passer de B
à A à partir des commande faisant passer de A à B. Il
suffit d'inverser les arguments et d'échanger les d et les a.
Exemple
diff
pourra rendre la séquence d'instructions
suivante :
1c1
< A
---
> C
3d2
< C
5d3
< B
7a6
> C
D'autres exemples d'edit script pour les
mêmes suites.
Plus longue sous-séquence commune
Le problème de produire un plus court "edit script" (SES) est
isomorphe au problème de calculer une plus longue sous-séquence
commune (LCS) : si vous calculez la plus longue sous-séquence
commune en prenant soin de garder trace des indices dans les deux
séquences à comparer, il est facile de produire le script.
(preuve)
Mais dans les cas d'un fichier, les éléments d'une
séquence sont des lignes entières, et il serait peu pratique (et
bien coûteux) de calculer la LCS sur des vecteurs contenant les fichiers
ligne par ligne : cela nécessiterait d'utiliser une fonction de
comparaison de ligne, dont le coût n'est pas constant.
On peut simplifier la tâche de la façon suivante :
- -
- On construit à partir des deux vecteurs de lignes (obtenus en
lisant chaque fichier) un dictionnaire associant une clé entière
différente à chaque ligne différente (et le même
entier à toutes les lignes égales). Pour cela, on peut utiliser
une fonction de hachage.
- -
- En même temps, on construit deux vecteurs d'entiers contenant
les clés et non pas les lignes.
- -
- On appelle SES sur les vecteurs des clés.
- -
- On transforme l'"edit script" sur les clés rendu par SES en
"edit script" sur les lignes.
L'interface
Nous supposons que la fonction SES rendra le script sous la forme d'un vecteur
de commandes d'édition simplifiées, sans les lignes à
rajouter ou changer, i.e. dans l'exemple précédent :
1c1
3d2
5d3
7a6
Et nous séparons maintenant le programme en deux modules : un qui
calcule la SES,et l'autre qui gère la lecture des fichiers, la
génération des vecteurs de clés et l'impression du script
d'édition complet.
Comme interface, on pourra utiliser par exemple le fichier
ses.h.
Tâches du programmeur A
- A-1
- Programmation de
diff
Écrivez une fonction int diff(char *fn1, char *fn2)
qui
utilise la fonction SES
pour calculer la différence entre
deux fichiers. (indications)
- A-2
- Améliorations
Modifier votre fonction pour permettre de ne pas tenir compte des
différences produites par des séquences d'espaces de longueurs
différentes.
Tâches du programmeur B
- B-1
- Programmation de SES
Programmez la fonction SES (il peut être utile, pour la tester, de
prévoir aussi l'impression de la sous-séquence commune). Quelle
est sa complexité, en espace et en temps ?
(indications)
- B-2
- Améliorations
Cherchez "An O(ND) Difference Algorithm and its
Variations", par Eugene Myers, qui se trouve dans Algorithmica Vol. 1
No. 2, 1986, pp. 251-266 (il est à la bibliothèque).
Implémentez la variante qui utilise un espace linéaire pour
calculer le résultat. (indication)
Tâches communes à A et B
- AB
- Compilez ensemble vos deux modules et... comparez avec
diff
.