Algorithme Diff? [fermé]

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.

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!

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.

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 "

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]

Sur la base du lien donné par Emmelaich, il y a aussi un excellent aperçu de Diff Strategies sur le 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 progresse vers l'algorithme de Myer et une certaine théorie des graphes.