Diff-Algorithmus? [geschlossen]

Ich habe nach einer Erklärung für einen Diff-Algorithmus gesucht, der funktioniert und effizient ist.

Das nächste, was ich bekommen habe, ist dieser Link zu RFC 3284 (aus mehreren Eric Sink-Blog-Posts), der in verständlichen Begriffen das Datenformat beschreibt, in dem die Diff-Ergebnisse gespeichert sind. Es wird jedoch überhaupt nicht erwähnt, wie ein Programm diese Ergebnisse erzielen würde, wenn es einen Unterschied macht.

Ich versuche dies aus persönlicher Neugier zu untersuchen, weil ich sicher bin, dass es bei der Implementierung eines Diff-Algorithmus Kompromisse geben muss, die manchmal ziemlich klar sind, wenn man sich Unterschiede ansieht und sich fragt, warum das Diff-Programm dies als Änderung gewählt hat stattdessen?"...

Wo finde ich eine Beschreibung eines effizienten Algorithmus, der am Ende VCDIFF ausgeben würde?
Übrigens, wenn Sie zufällig eine Beschreibung des tatsächlichen Algorithmus finden, der von SourceGears DiffMerge verwendet wird, wäre das sogar noch besser.

HINWEIS: Die längste gemeinsame Teilsequenz scheint nicht der von VCDIFF verwendete Algorithmus zu sein. Angesichts des von ihnen verwendeten Datenformats scheinen sie etwas Klügeres zu tun.

Ein O (ND) -Differenzalgorithmus und seine Variationen sind eine fantastische Arbeit, und Sie können dort beginnen. Es enthält Pseudocode und eine schöne Visualisierung der Graphendurchläufe, die beim Ausführen des Diff beteiligt sind.

In Abschnitt 4 des Papiers werden einige Verfeinerungen des Algorithmus vorgestellt, die ihn sehr effektiv machen.

Wenn Sie dies erfolgreich implementieren, erhalten Sie ein sehr nützliches Tool in Ihrer Toolbox (und wahrscheinlich auch einige hervorragende Erfahrungen).

Das Generieren des von Ihnen benötigten Ausgabeformats kann manchmal schwierig sein. Wenn Sie jedoch die Interna des Algorithmus verstehen, sollten Sie in der Lage sein, alles auszugeben, was Sie benötigen. Sie können auch Heuristiken einführen, um die Ausgabe zu beeinflussen und bestimmte Kompromisse einzugehen.

Hier ist eine Seite , die ein wenig Dokumentation, vollständigen Quellcode und Beispiele eines Diff-Algorithmus enthält, der die Techniken des oben genannten Algorithmus verwendet.

Der Quellcode scheint dem grundlegenden Algorithmus genau zu folgen und ist leicht zu lesen.

Es gibt auch ein bisschen über die Vorbereitung der Eingabe, was Sie vielleicht nützlich finden. Es gibt einen großen Unterschied in der Ausgabe, wenn Sie sich nach Zeichen oder Token (Wort) unterscheiden.

Viel Glück!

Ich würde zunächst den tatsächlichen Quellcode für diff betrachten, den GNU zur Verfügung stellt .

Um zu verstehen, wie dieser Quellcode tatsächlich funktioniert, verweisen die Dokumente in diesem Paket auf die Papiere, die ihn inspiriert haben:

Der grundlegende Algorithmus ist in "Ein O (ND) -Differenzalgorithmus und seine Variationen", Eugene W. Myers, 'Algorithmica' Vol. 3, No. 1 Nr. 2, 1986, S. 251-266; und in "A File Comparison Program", Webb Miller und Eugene W. Myers, "Software - Practice and Experience" Vol. 15 Nr. 11, 1985, S. 1025-1040. Der Algorithmus wurde unabhängig entdeckt, wie in "Algorithmen für die ungefähre Zeichenfolgenübereinstimmung", E. Ukkonen, "Information and Control", Band 3, beschrieben. 64, 1985, S. 100-118.

Das Lesen der Papiere und das Betrachten des Quellcodes für eine Implementierung sollte mehr als genug sein, um zu verstehen, wie es funktioniert.

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

"Die Diff Match- und Patch-Bibliotheken bieten robuste Algorithmen zur Ausführung der für die Synchronisierung von einfachem Text erforderlichen Vorgänge. ... Derzeit in Java, JavaScript, C ++, C # und Python verfügbar."

Siehe auch die Diff-Seite von wikipedia.org und - " Bram Cohen: Das Diff-Problem wurde gelöst "

Ich bin hierher gekommen, um nach dem Diff-Algorithmus zu suchen, und habe danach meine eigene Implementierung vorgenommen. Entschuldigung, ich weiß nichts über vcdiff.

Wikipedia : Von einer längsten gemeinsamen Teilsequenz ist es nur ein kleiner Schritt, eine diff-ähnliche Ausgabe zu erhalten: Wenn ein Element in der Teilsequenz fehlt, aber im Original vorhanden ist, muss es gelöscht worden sein. (Die '-' Markierungen unten.) Wenn es in der Teilsequenz fehlt, aber in der zweiten Sequenz vorhanden ist, muss es hinzugefügt worden sein. (Die '+' Markierungen.)

Schöne Animation des LCS-Algorithmus hier .

Link zu einer schnellen LCS Ruby-Implementierung hier .

Meine langsame und einfache Rubinanpassung ist unten.

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]

Basierend auf dem Link, den Emmelaich gegeben hat, gibt es auch eine große Anzahl von Diff-Strategien auf Neil Frasers Website (einer der Autoren der Bibliothek). .

Er behandelt grundlegende Strategien und geht gegen Ende des Artikels zu Myers Algorithmus und einer Graphentheorie über.