Algorithme Diff? [fermé]

Question

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

Mon adresse la plus proche est ce lien vers le document RFC 3284 (tiré de plusieurs blogs d'Eric Sink). posts), qui décrit en termes parfaitement compréhensibles le format de données dans lequel les résultats diff sont stockés. Cependant, il n’a aucune mention de la manière dont un programme atteindrait ces résultats tout en faisant une différence.

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

Où puis-je trouver la description d'un algorithme efficace qui aboutirait à la sortie de VCDIFF?
En passant, si vous trouviez une description de l’algorithme utilisé par DiffMerge de SourceGear, ce serait encore mieux.

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

Answer 1

L'algorithme de différence O (ND) et ses variantes est un document fantastique que vous voudrez peut-être pour commencer par là. Il inclut un pseudo-code et une belle visualisation des traversées de graphes impliquées dans la réalisation du diff.

La section 4 du document introduit des améliorations dans l'algorithme qui le rendent très efficace.

Si vous mettez cela en œuvre avec succès, vous disposerez d'un outil très utile dans votre boîte à outils (et probablement d'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 capable de générer tout ce dont vous avez besoin. Vous pouvez également introduire des heuristiques pour affecter la sortie et faire certains compromis.

Voici une page qui inclut un peu de documentation, code source complet , ainsi que des exemples d’un algorithme diff utilisant les techniques de cet algorithme.

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 pourriez trouver utile. Il y a une différence énorme en sortie lorsque vous différez par caractère ou par jeton (mot).

Bonne chance!

Answer 2

Je commencerai par examiner le code source actuel pour diff, que GNU crée disponible .

Pour comprendre le fonctionnement réel de ce code source, les documents de ce package font référence aux articles qui l'ont inspiré:

  

L’algorithme de base est décrit dans "Algorithme de différence An O (ND) et ses variations", Eugene W. Myers, «Algorithmica», vol. 1 N ° 2, 1986, pages 251-266; et dans " Un fichier   Programme de comparaison ", Webb Miller et Eugene W. Myers," Logiciels - Pratique et expérience ", vol. 15 N ° 11, 1985, pages 1025-1040. L'algorithme a été découvert de manière indépendante, comme décrit dans "Algorithmes pour une correspondance approximative de chaînes", E. Ukkonen, "Information and Control" Vol. 64, 1985, pages 100-118.

Lire les articles puis consulter le code source d’une implémentation devrait être plus que suffisant pour comprendre son fonctionnement.

Answer 3

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

  

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

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

Answer 4

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

Wikipedia : la sous-séquence la plus longue et courante n'est qu'un petit pas pour obtenir des diff like output: 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 dans 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 LCS ruby ??ici .

Ma lente et simple adaptation au rubis 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 existe également un excellent compte rendu de Diff Strategies sur le site Web de Neil Fraser (un des auteurs de la bibliothèque) .

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