Algorithme De Comparaison?

J'ai été à la recherche comme un fou pour l'explication d'un algorithme de comparaison qui fonctionne et est efficace.

Le plus proche que j'ai est ce lien à la RFC 3284 (à partir de plusieurs Eric Évier billets de blog), qui décrit parfaitement compréhensible termes de la format de données dans lequel la diff résultats sont stockés. Cependant, il n'a pas de mentionner que ce soit sur la façon dont un programme permettrait d'atteindre ces résultats lors d'une diff.

J'essaie de recherche de la curiosité personnelle, parce que je suis sûre qu'il doit être compromis lors de l'implémentation d'un algorithme de comparaison, qui sont assez clairs, parfois, quand vous regardez des diffs et me demande "pourquoi les diff programme choisi ce qu'un changement à la place de qui?"...

Où puis-je trouver une description d'un algorithme efficace qui aurait une sortie VCDIFF?

Par ailleurs, si vous trouvez une description de l'algorithme réel utilisé par SourceGear de DiffMerge, ce serait encore mieux.

REMARQUE: la plus longue sous-suite commune ne semble pas être l'algorithme utilisé par VCDIFF, on dirait qu'ils vont faire quelque chose de plus intelligent, étant donné le format de données qu'ils utilisent.

  • Rien sur wikipédia ? Vous pouvez peut-être essayer de trouver une autre mise en œuvre de haut niveau de langage comme python, qui pourrait être plus facile à comprendre qu'un C mise en œuvre. Python est célèbre pour être facilement lisible ? Il y a un difflib en python. Voici l'url de la source. La source a des tonnes de commentaires sur les diff algorithmes. svn.python.org/view/python/trunk/Lib/...
  • Les rfc ne sont pas destinés à décrire des algorithmes. Ils sont destinés à décrire des interfaces/protocoles).
  • En fait, le noyau de l'algorithme de comparaison, la plus longue de la commune de la sous-séquence problème, peut être trouvé sur Wikipédia. Cette page donne une vue d'ensemble de l'algorithme et des exemples de code que j'ai trouvé utile quand j'ai besoin d'écrire une coutume diff: en.wikipedia.org/wiki/Longest_common_subsequence_problem
  • Peut-être cela va aider: paulbutler.org/archives/a-simple-diff-algorithm-in-php c'est sûr qu'Il est génial, et c'est tellement petit (29 lignes au total, et dispose de 2 fonctions). Il est semblable à un Débordement de Pile de modifier révision de comparer chose.
  • VCDIFF n'est pas lisible par l'homme pour des diffs. Il emploie ajouter, copier et exécuter des instructions par opposition à la plus lisible supprimer et insérer des instructions émises par la plupart des en texte brut diff algorithmes. Pour VCDIFF vous besoin de quelque chose comme la xdelta algortihm décrit ici xmailserver.org/xdfs.pdf