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
Vous devez vous connecter pour publier un commentaire.
Un O(ND) Différence de l'Algorithme et de ses Variations est un fantastique papier et vous pouvez commencer par là. Il comprend un pseudo-code et une belle visualisation du graphe traversals impliqué dans faire la diff.
Section 4 du papier introduit quelques améliorations apportées à l'algorithme qui le rendent très efficace.
Avec succès la mise en œuvre de ce qui vous laisse avec un outil très utile dans votre boîte à outils (et probablement une excellente expérience en tant que bien).
Générer le format de sortie que vous avez besoin peut parfois être difficile, mais si vous avez la compréhension de l'algorithme interne, alors vous devriez être en mesure de produire tout ce dont vous avez besoin. Vous pouvez également introduire des méthodes heuristiques pour affecter le résultat et de faire certains compromis.
Voici une page qui comprend un peu de documentation, l'intégralité du code source, et des exemples d'un algorithme de comparaison en utilisant les techniques dans l'algorithme ci-dessus.
La le code source semble suivre l'algorithme de base de près et est facile à lire.
Il y a aussi un peu sur la préparation de l'entrée, qui peuvent vous être utiles. Il y a une énorme différence en sortie lorsque vous êtes de comparaison par caractère ou un jeton (word).
Bonne chance!
diff
papier par la Chasse et de McIlroy.Je voudrais commencer par regarder le réel code source pour les diff, qui GNU rend disponible.
Pour un compréhension de la façon dont le code source fonctionne, la documentation de ce package de référence les documents qui l'a inspiré:
La lecture de la presse, puis en regardant le code source d'une mise en œuvre devrait être plus que suffisant pour comprendre comment il fonctionne.
Voir https://github.com/google/diff-match-patch
Également voir le wikipedia.org Diff page et "Bram Cohen: La diff problème a été résolu"
Je suis venu ici à la recherche de l'algorithme de comparaison et par la suite fait ma propre mise en œuvre. Désolé, je ne sais pas à propos de vcdiff.
Wikipédia: À partir d'une plus longue sous-suite commune c'est qu'une petite étape pour obtenir de type diff de sortie: si un élément est absent dans la sous-suite, mais présents dans l'original, il doit avoir été supprimé. (Le '–' les marques ci-dessous). Si elle est absente de la sous-suite mais présent dans la deuxième séquence, il doit avoir été ajouté. (Le " + " des marques.)
Belle animation de la LCS algorithme ici.
Lien à un rapide LCS ruby mise en œuvre ici.
Mon lent et simple ruby adaptation est ci-dessous.
Basée sur le lien Emmelaich a donné, il y a aussi une très belle course vers le bas de Diff Stratégies sur Neil Fraser sur le site de l'un des auteurs de la bibliothèque).
Il couvre les stratégies de base, et vers la fin de l'article, qui progresse Myer de l'algorithme et de certains de théorie des graphes.