Algorithme Diff? [fermé]

164

J'ai eu l'air fou pour une explication d'un algorithme de diff qui fonctionne et est efficace.

Le plus proche que j'ai obtenu est ce lien vers la RFC 3284 (provenant de plusieurs articles de blog d'Eric Sink), qui décrit en termes parfaitement compréhensibles le format de données dans lequel les résultats de diff sont stockés. Cependant, il ne fait aucune mention de la manière dont un programme atteindrait ces résultats tout en effectuant une différence.

J'essaie de rechercher cela par curiosité personnelle, car je suis sûr qu'il doit y avoir des compromis lors de la mise en œuvre d'un algorithme de diff, qui sont parfois assez clairs lorsque vous regardez les diffs et que vous vous demandez "pourquoi le programme diff a-t-il choisi cela comme un changement au lieu de?"...

Où puis-je trouver une description d'un algorithme efficace qui finirait par produire du VCDIFF?
Au fait, si vous trouvez une description de l'algorithme utilisé par DiffMerge de SourceGear, ce serait encore mieux.

REMARQUE: la sous-séquence commune la plus longue ne semble pas être l'algorithme utilisé par VCDIFF, il semble qu'ils font quelque chose de plus intelligent, étant donné le format de données qu'ils utilisent.

Daniel Magliola
la source
Rien sur wikipedia? Vous pouvez peut-être essayer de trouver une autre implémentation dans un langage de haut niveau comme python, qui pourrait être plus facile à comprendre qu'une implémentation en C. Python est réputé 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 algorithmes de diff. svn.python.org/view/python/trunk/Lib/…
bsergean
4
Les RFC ne sont pas censées décrire des algorithmes. Ils sont destinés à décrire les interfaces (/ protocoles).
2
En fait, le cœur de l'algorithme diff, le plus long problème de sous-séquence courant, peut être trouvé sur Wikipedia. Cette page donne un aperçu de l'algorithme et de l'exemple de code que j'ai trouvé utile lorsque j'ai eu besoin d'écrire un diff personnalisé: en.wikipedia.org/wiki/Longest_common_subsequence_problem
Corwin Joy
3
Cela aidera peut-être: paulbutler.org/archives/a-simple-diff-algorithm-in-php C'est vraiment génial, et c'est si petit (seulement 29 lignes au total ; il a 2 fonctions). C'est similaire à la comparaison des révisions de Stack Overflow.
Nathan
VCDIFF n'est pas pour les diffs lisibles par l'homme. Il utilise des instructions d'ajout, de copie et d'exécution par opposition aux instructions de suppression et d'insertion plus lisibles par l'homme émises par la plupart des algorithmes de diff en texte brut. Pour VCDIFF, vous avez besoin de quelque chose comme l'algortihm xdelta décrit ici xmailserver.org/xdfs.pdf
asgerhallas

Réponses:

175

Un algorithme de différence O (ND) et ses variations est un article fantastique et vous voudrez peut-être commencer par là. Il comprend un pseudo-code et une belle visualisation des traversées de graphe impliquées dans la réalisation du diff.

La section 4 de l'article présente quelques améliorations à l'algorithme qui le rendent très efficace.

Une mise en œuvre réussie de cela vous laissera un outil très utile dans votre boîte à outils (et probablement une excellente expérience également).

La génération du format de sortie dont vous avez besoin peut parfois être délicate, mais si vous comprenez les éléments internes de l'algorithme, vous devriez être en mesure de produire tout ce dont vous avez besoin. Vous pouvez également introduire des heuristiques pour affecter la sortie et effectuer certains compromis.

Voici une page qui comprend un peu de documentation, le code source complet et des exemples d'un algorithme de diff utilisant les techniques de l'algorithme susmentionné.

Le code source semble suivre de près l'algorithme de base et est facile à lire.

Il y a aussi un peu de préparation de l'entrée, que vous trouverez peut-être utile. Il y a une énorme différence dans la sortie lorsque vous différez par caractère ou jeton (mot).

Bonne chance!

jscharf
la source
1
Au cas où le lien tourne mal, il s'agit de Myers 1986; voir par exemple citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.4.6927 - il comprend en outre un lien vers l' diffarticle Unix de Hunt et McIlroy.
tripleee
34

Je commencerais par regarder le code source réel de diff, que GNU met à disposition .

Pour comprendre comment ce code source fonctionne réellement, les documents de ce package font référence aux articles qui l'ont inspiré:

L'algorithme de base est décrit dans "An O (ND) Difference Algorithm and its Variations", Eugene W. Myers, 'Algorithmica' Vol. 1 N ° 2, 1986, pages 251-266; et dans «A File Comparison Program», Webb Miller et Eugene W. Myers, «Software - Practice and Experience» Vol. 15 N ° 11, 1985, pages 1025-1040. L'algorithme a été découvert indépendamment comme décrit dans "Algorithms for Approximate String Matching", E. Ukkonen, `Information and Control 'Vol. 64, 1985, pages 100-118.

Lire les articles puis regarder le code source d'une implémentation devrait être plus que suffisant pour comprendre comment cela fonctionne.

paxdiablo
la source
80
Hmmm, en bref, déterminer parfois l'algorithme sous-jacent à partir du code source réel (surtout s'il est optimisé pour être efficace) peut être assez complexe. Je serai capable de comprendre ce que fait le programme étape par étape, mais pas exactement "pourquoi", ou un aperçu de haut niveau à ce sujet ... Exemple: Vous ne comprendriez jamais comment les expressions régulières fonctionnent (ou ce qu'elles sont) en regardant l'implémentation des expressions rationnelles de Perl. Ou si vous pouviez faire cela, alors je lève mon chapeau, j'ai vraiment besoin d'un aperçu plus expliqué et de niveau supérieur pour comprendre ce qui se passe.
Daniel Magliola
3
Je ne comprends jamais comment la grande majorité de Perl fonctionne :-), mais il y a un lien dans la documentation du paquet (voir mise à jour) qui vous dirigera vers la littérature le décrivant (il s'agit de l'algorithme de diff, pas de Perl).
paxdiablo
32
Ne lisez pas le code. Lisez l'article.
Ira Baxter
31

Voir https://github.com/google/diff-match-patch

"Les bibliothèques Diff Match et Patch offrent des algorithmes robustes pour effectuer les opérations nécessaires à la synchronisation de texte brut. ... Actuellement disponible en Java, JavaScript, C ++, C # et Python"

Voir également la page Diff de wikipedia.org et - " Bram Cohen: Le problème de diff a été résolu "

Matthew Hannigan
la source
2
Je voulais juste mentionner que l'algorithme de Cohen semble également être connu sous le nom de Patience Diff. C'est l'algorithme diff (par défaut?) Dans bazaar et un algorithme facultatif dans git.
Dale Hagglund
13

Je suis venu ici à la recherche de l'algorithme diff et j'ai ensuite fait ma propre implémentation. Désolé, je ne sais pas pour vcdiff.

Wikipédia : À partir d'une sous-séquence commune la plus longue, ce n'est qu'un petit pas pour obtenir une sortie de type diff: si un élément est absent de la sous-séquence mais présent dans l'original, il doit avoir été supprimé. (Les marques «-», ci-dessous.) S'il est absent de la sous-séquence mais présent dans la deuxième séquence, il doit avoir été ajouté. (Les marques «+».)

Belle animation de l' algorithme LCS ici .

Lien vers une implémentation rapide de LCS ruby ​​ici .

Mon adaptation rubis lente et simple est ci-dessous.

def lcs(xs, ys)
  if xs.count > 0 and ys.count > 0
    xe, *xb = xs
    ye, *yb = ys
    if xe == ye
      return [xe] + lcs(xb, yb)
    end
    a = lcs(xs, yb)
    b = lcs(xb, ys)
    return (a.length > b.length) ? a : b
  end
  return []
end

def find_diffs(original, modified, subsequence)
  result = []
  while subsequence.length > 0
    sfirst, *subsequence = subsequence
    while modified.length > 0
      mfirst, *modified = modified
      break if mfirst == sfirst
      result << "+#{mfirst}"
    end
    while original.length > 0
      ofirst, *original = original
      break if ofirst == sfirst
      result << "-#{ofirst}"
    end
    result << "#{sfirst}"
  end
  while modified.length > 0
    mfirst, *modified = modified
    result << "+#{mfirst}"
  end
  while original.length > 0
    ofirst, *original = original
    result << "-#{ofirst}"
  end
  return result
end

def pretty_diff(original, modified)
  subsequence = lcs(modified, original)
  diffs = find_diffs(original, modified, subsequence)

  puts 'ORIG      [' + original.join(', ') + ']'
  puts 'MODIFIED  [' + modified.join(', ') + ']'
  puts 'LCS       [' + subsequence.join(', ') + ']'
  puts 'DIFFS     [' + diffs.join(', ') + ']'
end

pretty_diff("human".scan(/./), "chimpanzee".scan(/./))
# ORIG      [h, u, m, a, n]
# MODIFIED  [c, h, i, m, p, a, n, z, e, e]
# LCS       [h, m, a, n]
# DIFFS     [+c, h, +i, -u, m, +p, a, n, +z, +e, +e]
neoneye
la source