Algorithme de diffusion ?

Question

J'ai cherché comme un fou l'explication d'un algorithme de comparaison qui fonctionne et qui soit efficace.

Le plus proche que j'ai obtenu est ce lien vers le RFC 3284 (tiré de plusieurs articles du blog d'Eric Sink), qui décrit en termes parfaitement compréhensibles la format de données dans lequel les résultats de la comparaison sont stockés. Cependant, il n'y a aucune mention de la manière dont un programme pourrait atteindre ces résultats lors d'une comparaison.

J'essaie de faire des recherches sur ce sujet par curiosité personnelle, parce que je suis sûr qu'il doit y avoir des compromis lors de l'implémentation d'un algorithme de diff, qui sont assez clairs parfois quand on regarde les diffs et qu'on se demande "pourquoi le programme diff a choisi ceci comme changement au lieu de cela ?"...

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

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

Answer 1

Un algorithme de différence O(ND) et ses variations est un document fantastique et vous pouvez commencer par là. Il comprend un pseudo-code et une belle visualisation des traversées de graphes impliquées dans la comparaison.

Section 4 de l'article présente quelques raffinements de l'algorithme qui le rendent très efficace.

Si vous réussissez à mettre en œuvre cette méthode, vous disposerez d'un outil très utile dans votre boîte à outils (et probablement aussi d'une excellente expérience).

Générer le format de sortie dont vous avez besoin peut parfois être délicat, mais si vous comprenez les mécanismes 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 faire certains compromis.

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

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

Il y a aussi une partie sur la préparation de l'entrée, qui peut vous être utile. Il y a une énorme différence dans le résultat lorsque vous différez par caractère ou par token (mot).

Bonne chance !

Answer 2

Je commencerais par examiner les données réelles code source pour diff, que GNU rend disponible sur .

Pour un comprendre de la façon dont ce code source fonctionne réellement, les documents de ce paquet 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 No. 2, 1986, pp. 251-266 ; et dans "A File Comparison Program", Webb Miller et Eugene W. Myers, "Software--Practice and Experience" Vol. 15 No. 11, 1985, pp. 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, pp. 100-118.

La lecture des articles puis l'examen du code source d'une mise en œuvre devraient suffire à comprendre le fonctionnement.

Answer 3

Ver 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 du texte brut. ... Actuellement disponibles en Java, JavaScript, C++, C# et Python "

Voir aussi le wikipedia.org Page Diff et - " Bram Cohen : Le problème du diff a été résolu "

Answer 4

Je suis venu ici pour chercher l'algorithme diff et j'ai ensuite fait ma propre implémentation. Désolé, je ne connais pas vcdiff.

Wikipedia : À partir d'une sous-séquence commune la plus longue, il n'y a qu'un petit pas à faire 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 a dû être ajouté. (Les marques "+".)

Belle animation de la Algorithme LCS ici .

Lien vers un rapide Implémentation de LCS ruby ici .

Mon adaptation lente et simple en ruby 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]

Answer 5

Sur la base du lien donné par Emmelaich, il y a également une excellente présentation des stratégies de diffusion sur Site web de Neil Fraser (l'un des auteurs de la bibliothèque) .

Il couvre les stratégies de base et, vers la fin de l'article, il aborde l'algorithme de Myer et la théorie des graphes.