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

Exemple de comparaison
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.