Où puis-je trouver une explication et une implémentation de l'algorithme diff? Tout d'abord, je dois reconnaître que je ne suis pas sûr si c'est le nom correct de l'algorithme. Par exemple, comment Stack Overflow marque-t-il les différences entre deux éditions de la même question? PS: Je connais les langages de programmation C et PHP.Où puis-je trouver l'algorithme diff?
Il n'existe vraiment pas d'algorithme de diff. Il existe de nombreux algorithmes diff différents, et en fait les algorithmes de diff particuliers utilisés sont dans certains cas considérés comme un avantage commercial de l'outil de comparaison particulier.
En général, de nombreux algorithmes diff sont basés sur le problème de la plus longue sous-séquence commune (LCS).
Le programme original Unix diff des années 1970 a été écrit par Doug McIllroy et utilise ce qu'on appelle l'algorithme de Hunt-McIllroy. Près de 40 ans plus tard, les extensions et les dérivées de cet algorithme sont encore très courantes. Il y a quelques années, Bram Cohen (créateur du programme de partage de fichiers le plus performant et du système de contrôle de version le moins efficace) a créé le Patience Diff algorithm conçu pour donner des résultats plus lisibles que les LCS. Il a été implémenté à l'origine dans le VCS Bazaar et a également été ajouté à Git en option. Cependant, à moins que vous ne soyez intéressé par la recherche sur les algorithmes de diff, votre meilleur pari serait probablement d'utiliser une bibliothèque de diff existante comme Davide Libenzi's LibXDiff, qui est par exemple ce que Git utilise. Je ne serais pas trop surpris s'il y avait déjà une extension PHP l'enveloppant. Une bonne alternative est Google's Diff-Match-Patch library, qui est utilisée dans Bespin ou WhiteRoom, par exemple et qui est disponible pour de nombreuses langues. Il utilise l'algorithme de Meyers Diff plus quelques pré et post-traitement pour des accélérations supplémentaires.
Une approche complètement différente, si vous êtes plus intéressé par la fusion que par la différenciation, est appelée Transformations Opérationnelles. L'idée de l'OT est qu'au lieu de déterminer les différences entre deux documents, vous essayez de «désosser» les opérations qui ont conduit à ces différences. Cela permet une meilleure fusion, car vous pouvez ensuite "rejouer" ces opérations. Ils sont particulièrement utiles pour les éditeurs collaboratifs en temps réel tels que EtherPad, Google Wave ou SubEthaEdit.
Quel est le problème avec wikipedia où il est Hunt-McIlroy algorithm?
Il existe OCR'd paper décrivant l'algorithme (explication) et vous pouvez inspecter source (implémentation).
Les si des questions connexes aussi la liste (entre autres):
'Best' Diff Algorithm
How do document diff algorithms work?
Diff Algorithm
qui semblent tous être utiles.
La liaison papier est morte. – Matsemann
beaucoup de thx pour votre réponse. Malheureusement je n'ai qu'un seul vote et cette fois je vais adorer le classer avec plus –
+1 très agréable :) – Unreason
+1 pour informer sur l'existence de Transformations Opérationnelles – EoghanM