Un programme qui compare deux textes ne lit pas « ce qui a changé » comme le ferait un humain. Il cherche plutôt la façon de transformer une liste en l'autre avec le moins possible de suppressions et d'ajouts. Cet article explique comment diff calcule cette réponse, et pourquoi le résultat diffère parfois de ce qu'on attendait.
L'unité de comparaison : ligne, mot, caractère
diff commence par découper le texte en une liste de jetons (tokens). Le diff traditionnel et git considèrent chaque ligne comme un jeton. C'est pourquoi un seul caractère modifié dans une ligne fait apparaître toute la ligne comme « 1 ligne supprimée + 1 ligne ajoutée ».
La comparaison par ligne est rapide et convient bien à la revue de code, mais dans un document où un long paragraphe tient sur une seule ligne, il devient difficile de repérer ce qui a changé. Beaucoup d'outils comparent donc en deux temps :
- Comparer ligne par ligne pour trouver les lignes modifiées.
- Apparier les lignes modifiées et comparer de nouveau leur contenu par mot ou par caractère.
Ce site procède de la même façon. Pour le détail dans la ligne, vous pouvez choisir le mot, le bloc (séparé par des espaces) ou le caractère.
La plus longue sous-séquence commune (LCS)
Le cœur mathématique de diff est la plus longue sous-séquence commune (Longest Common Subsequence, LCS). Une sous-séquence s'obtient en prenant certains éléments d'une liste sans changer leur ordre. Par exemple, la plus longue sous-séquence commune de ABCABBA et CBABAC est de longueur 4 : CABA ou BABA en sont des exemples.
Les éléments de la LCS sont « ce qui est resté », les autres sont « supprimés » (présents seulement à gauche) ou « ajoutés » (présents seulement à droite). Plus la LCS est longue, moins il y a de suppressions et d'ajouts. Si les deux listes ont pour longueurs N et M et que la LCS a pour longueur L, le nombre total D de suppressions et d'ajouts nécessaires vaut :
D = (N - L) + (M - L)Dans l'exemple ci-dessus, N=7, M=6 et L=4, donc D = 3 + 2 = 5. Ce D s'appelle la distance d'édition (quand seules l'insertion et la suppression sont permises), et la liste des suppressions et ajouts s'appelle le script d'édition.
Le graphe d'édition et l'algorithme de Myers
Calculer la LCS avec la méthode des manuels (programmation dynamique) exige un tableau de N×M cases. Comparer deux fichiers de 10 000 lignes représente 100 millions de cases : c'est lent et gourmand en mémoire. En 1986, Eugene W. Myers a proposé une méthode plus rapide dans l'article « An O(ND) Difference Algorithm and Its Variations », qui est à la base des algorithmes par défaut de GNU diff et de git aujourd'hui.
Myers transforme la comparaison en recherche du plus court chemin sur une grille :
- On part du coin supérieur gauche (0,0) pour arriver au coin inférieur droit (N,M).
- Un pas vers la droite = supprimer un élément du texte de gauche ; un pas vers le bas = ajouter un élément du texte de droite. Chaque pas coûte 1.
- Là où les deux éléments sont identiques, on peut avancer gratuitement en diagonale. Une suite de diagonales ainsi enchaînées s'appelle un snake.
Le chemin le moins coûteux correspond au script d'édition le plus court. L'algorithme de Myers élargit pas à pas « le point le plus éloigné atteignable pour un coût 0 », puis « pour un coût 1 »… et s'arrête dès qu'il atteint l'arrivée. À chaque étape, il suffit de retenir, pour chaque diagonale, la position la plus avancée : le temps de calcul est donc à peu près proportionnel à (N+M)×D. Quand les deux textes sont presque identiques, D est petit et le calcul est très rapide ; quand ils sont complètement différents, il ralentit.
Mémoire linéaire et middle snake
Pour reconstituer le chemin, il faut garder une trace de chaque étape, ce qui peut faire croître la mémoire proportionnellement à D². Dans le même article, Myers propose une variante qui mène simultanément une recherche depuis le début et une recherche à rebours depuis la fin, jusqu'à trouver la portion diagonale où elles se rejoignent (le middle snake). En coupant le problème en deux sous-problèmes plus petits à cet endroit, et en répétant l'opération, la mémoire utilisée reste proportionnelle à la taille de l'entrée.
Quand c'est trop coûteux : l'heuristique d'approximation
Si les deux entrées font des dizaines de milliers de lignes et diffèrent beaucoup, D devient grand et (N+M)×D peut atteindre plusieurs milliards. Pour ce cas, GNU diff dispose d'une heuristique : quand le nombre d'étapes dépasse une certaine limite, il coupe le problème sur la diagonale la plus avancée jusque-là. Le résultat reste un script d'édition correct, mais rien ne garantit qu'il soit le plus court. L'option --minimal de GNU diff, comme celle de git, force la recherche du résultat minimal, au prix d'un temps de calcul plus long.
Minimal ne veut pas toujours dire lisible
Plusieurs chemins peuvent avoir la même distance d'édition. Par exemple, quand on ajoute une fonction dans du code, les accolades fermantes } et les lignes vides apparaissent à plusieurs endroits : l'algorithme peut alors apparier le } de la nouvelle fonction avec celui d'une fonction existante. Le résultat est minimal, mais peu naturel à lire. C'est pourquoi git utilise par défaut une heuristique qui déplace les limites en tenant compte de l'indentation, et propose d'autres algorithmes comme patience ou histogram. La comparaison détaillée se trouve dans Comparaison des algorithmes diff.
Dans cet outil
Le moteur de comparaison de ce site implémente en JavaScript la variante à mémoire linéaire de l'algorithme de Myers et, pour les grandes entrées, bascule vers un découpage approché à la manière de GNU diff. Le calcul s'exécute dans un Web Worker : l'affichage ne se fige pas, même avec de gros fichiers. Une fois le résultat par ligne obtenu, les lignes modifiées au contenu proche sont appariées et marquées « modifiées », puis comparées de nouveau selon l'unité choisie (mot, bloc ou caractère) pour surligner le détail.
Collez deux textes dans le comparateur de texte et changez l'unité de détail dans la ligne pour voir comment le résultat évolue. Pour lire le résultat au format git, consultez Lire un diff unifié.