Diff-Algorithmus? [geschlossen]

Question

Ich habe wie verrückt für eine Erklärung eines diff-Algorithmus sucht das funktioniert und ist effizient.

Die nächstgelegene ich bekam diesen Link zu RFC 3284 (von mehrere Eric Sink Blog Beiträge), die gespeichert in vollkommen verständlicher Weise das Datenformat in denen die diff Ergebnisse beschreibt. Es hat jedoch keinerlei Erwähnung, wie ein Programm würde diese Ergebnisse zu erreichen, während ein Diff zu tun.

Ich versuche, dies aus persönlicher Neugier zu erforschen, weil ich dort sicher bin, muss Kompromissen sein, wenn ein Diff-Algorithmus Implementierung, die manchmal ziemlich klar, wenn man sich diffs schauen und sich fragen, „warum das Diff-Programm haben wählte diese als eine Änderung statt das?“...

Wo finde ich eine Beschreibung eines effizienten Algorithmus finden, die VCDIFF Ausgeben würde am Ende?
By the way, wenn Sie eine Beschreibung des Ist-Algorithmus, der von SourceGear des DiffMerge verwendet passieren zu finden, das wäre noch besser.

Hinweis: längste gemeinsame Teilfolge scheint nicht der Algorithmus von VCDIFF verwendet werden, sieht es aus wie sie etwas schlauer, da das Datenformat verwenden sie tun

.

Answer 1

Ein O (ND) Differenz-Algorithmus und seine Variationen ein fantastisches Papier ist, und Sie möchten beginnen dort. Es enthält Pseudo-Code und eine schöne Visualisierung des beteiligten Graph Querungen in dem Diff zu tun.

4 das Papier einiger Verfeinerungen des Algorithmus führt, dass es sehr effektiv.

Erfolgreich Umsetzung dieser Ihnen ein sehr nützliches Werkzeug in der Toolbox verlassen wird (und wahrscheinlich einige ausgezeichnete Erfahrung als auch).

Die Erzeugung des Ausgabeformat Sie müssen manchmal schwierig sein kann, aber wenn man das Verständnis der Algorithmus Interna haben, dann sollten Sie die Ausgabe etwas fähig sein die Sie benötigen. Sie können auch Heuristiken einführen, um die Ausgabe zu beeinflussen und bestimmte Abwägungen machen.

Hier ist eine Seite , die ein bisschen Dokumentation enthält, Quellcode erscheint dem grundlegenden Algorithmus genau zu verfolgen und ist leicht zu lesen.

Es ist auch ein bisschen die Eingabe auf die Vorbereitung, die Sie nützlich finden können. Es gibt einen großen Unterschied in der Ausgabe, wenn Sie durch Zeichen oder Token (Wort) sind diffing.

Viel Glück!

Answer 2

würde ich durch einen Blick auf die tatsächliche Quellcode für diff beginnen, die GNU macht

Beim Lesen der Papiere dann auf den Quellcode der Suche nach einer Implementierung sollte mehr als genug sein, um zu verstehen, wie es funktioniert.

Answer 3

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

  

"Das Diff Spiel und Patch-Bibliotheken   bieten robuste Algorithmen die zur Durchführung   Operationen, die erforderlich für die Synchronisierung   Klartext. ... Gegenwärtig verfügbar   in Java, JavaScript, C ++, C # und   Python "

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

Answer 4

Ich kam hier für den Diff-Algorithmus sucht und danach meine eigene Implementierung gemacht. Leider weiß ich nicht über VCDIFF.

Wikipedia : Vom längsten gemeinsamen Teilfolge ist es nur ein kleiner Schritt zu bekommen DIFF- wie Ausgang: wenn ein Element in der Teilfolge aber in den ursprünglichen fehlt, muss sie gelöscht wurde. . (Die ‚-‘. Marken, unten) Wenn es in der Teilfolge fehlt aber in der zweiten Folge, muss es in hinzugefügt wurden (. Das ‚+‘ markiert)

Nizza Animation des LCS Algorithmus hier .

Link zu einem schnellen LCS Ruby-Implementierung hier .

Meine langsam und einfache Ruby-Anpassung 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]

Answer 5

Basierend auf den Link Emmelaich gab, gibt es auch einen großen Nase nach unten von Diff-Strategien auf Neil Fraser Webseite (einer der Autoren der Bibliothek) .

deckt er grundlegende Strategien und gegen Ende des Artikels schreitet zu Myer-Algorithmus und einige Graphentheorie.