Suche nach algo für Text diff erkennt und Dosengruppe ähnliche Linien

Question

Ich bin in den Prozess ein Diff Textwerkzeug des Schreibens zwei ähnliche Quellcodedateien vergleichen.

Es gibt viele solche „diff“ Werkzeuge um, aber ich wird ein wenig sein verbessert:

Wenn es eine Reihe von Linien findet auf beiden Seiten nicht übereinstimmen (dh. In beiden Dateien), so hat er nicht nur die Linien markieren, sondern auch die einzelnen Änderungen in diesen Zeilen markieren (Ich nenne diese inter-line Vergleich hier).

Ein Beispiel für meine etwas Arbeitslösung:

alt text http://files.tempel.org/tmp/diff_example.png

Was es derzeit tut, ist eine Reihe von nicht übereinstimmen Linien zu nehmen und ihre einzelnen Zeichen durch das diff laufen algo noch einmal, die rosa Markierung zu erzeugen.

der zweite Satz von Mismatches jedoch „Original 2“ enthält, erfordert mehr Arbeit: Hier sind die ersten beiden geraden Linien ( „hinzugefügt Linie a / b“) zugegeben, während die dritte Linie eine veränderte Version des ist linke Seite. Ich mag meine Software diesen Unterschied zwischen einer wahrscheinlichen Änderung und einer wahrscheinlichen neuen Linie zu erkennen.

Wenn bei diesem einfachen Beispiel suchen, kann ich ziemlich leicht, diesen Fall erkennen:

Mit einem algo wie Levenshtein ich, dass alle geraden Linien in der Menge von 3 bis 5 finden konnte, Linie 5 Spiele linke Linie 3 am besten, so konnte ich die Linien 3 und 4 auf der rechten Seite abziehen gegeben und führen die Zwischenzeilen Vergleich auf der linken Linie und der rechten Linie 3 5.

So weit, so gut. Aber ich bin immer noch stecken mit, wie für diesen Zweck dieses in einen allgemeineren Algorithmus zu machen.

In einer komplexeren Situation, eine Reihe von verschiedenen Linien konnte Linien auf beiden Seiten hinzugefügt, mit einigen eng passenden Linien dazwischen. Dies wird ziemlich kompliziert:

zu den besten auf der rechten Seite, aber umgekehrt auch, und so weiter mit allen anderen Linien

ich müsste auf der linken Seite nicht nur die erste Zeile entsprechen. Grundsätzlich muss ich auf der linken Seite gegen jeden auf der rechten Seite jeder Zeile entsprechen. Im schlimmsten Fall könnte dies sogar Kreuzungen erstellen, so dass es nicht leicht löschen ist nicht mehr, welche Linien wurden neu eingeführt und die wurden nur verändert (Anmerkung: Ich möchte nicht mit möglichen verschobene Linien in einem solchen Block behandeln, es sei denn, das wäre eigentlich simplify der Algorithmus).

Sicher, das wird nie perfekt sein, aber ich versuche, es besser zu bekommen, als es jetzt ist. Alle Vorschläge, die nicht zu theoerical sondern praktisch (Ich bin nicht gut verstehen abstrakte algos) geschätzt werden.

Update

Ich muss zugeben, dass ich nicht einmal verstehen, wie die LCS Werke Algo. Ich füttere sie einfach zwei Arrays von Strings und aus einer Liste kommt, von denen Sequenzen nicht übereinstimmen. Ich bin im Grunde den Code von hier mit: http://www.incava.org/projects / java / java-diff

Mit Blick auf den Code, den ich eine Funktion gleich () zu finden, die für das Erklären des Algorithmus verantwortlich ist, ob zwei Linien übereinstimmen oder nicht. Nach dem, was Pavel vorgeschlagen, frage ich mich, ob das der Ort ist, wo ich die Änderungen vornehmen würde. Aber wie? Diese Funktion gibt nur einen boolean - nicht einen relativen Wert, der die Qualität des Spiels identifizieren konnte. Und ich kann einfach nicht eine feste Levenshtein Ration verwendet, die darüber entscheiden würde, ob eine ähnliche Linie noch als gleich betrachtet wird oder nicht. - Ich werde etwas brauchen, dass das Selbst Annahme auf den gesamten Satz von Linien in Frage

Also, was ich im Grunde ich sage ist, dass ich immer noch nicht verstehen, wo ich die Fuzzy-Wert gelten würde, die auf der relativen Ähnlichkeit der Linien betrifft, die nicht (genau) übereinstimmen.

Answer 1

  

Mit einem algo wie Levenshtein ich, dass alle geraden Linien in der Menge von 3 bis 5 finden konnte, Linie 5 Spiele linke Linie 3 am besten, so konnte ich die Linien 3 und 4 auf der rechten Seite abziehen gegeben und führen die Zwischenzeilen Vergleich auf der linken Linie und der rechten Linie 3 5.

Nachdem Sie bestimmt haben, verwenden Sie den gleichen Algorithmus zu bestimmen, welche Zeilen in diesen beiden Spalten zueinander passen. Aber Sie müssen leichten modificaiton machen. Wenn Sie den Algorithmus verwendet, gleiche Linien zu entsprechen, könnten die Linien entweder übereinstimmen oder nicht übereinstimmen, so dass entweder 0 oder 1 in die Zelle der Tabelle hinzugefügt Sie verwendet haben.

Wenn Strings in einem Klumpen zu vergleichen einige von ihnen sind „gleicher“ als andere (ack. Orwell). So dass sie eine reelle Zahl von 0 bis 1 zu der Zelle hinzufügen können, wenn was Streichhölzer Reihenfolge unter Berücksichtigung bisher best.

Diese Metriken berechnen (von 0 bis 1), können Sie auf jedes Paar von Strings gelten Sie ... richtig begegnen, wieder der gleiche Algorithmus (eigentlich Sie dies bereits getan, wenn Sie die taten erste von Levenstein-Algorithmus übergeben). Dadurch wird die Länge von LCS berechnen, dessen Verhältnis zu der durchschnittlichen Länge von zwei Strings würden die der Metrik Wert sein.

Alternativ können Sie den Algorithmus von einem diff Tools leihen. Zum Beispiel kann vimdiff die Spiele markieren Sie benötigen.

Answer 2

Levenshtein Abstand basiert auf der Idee eines „Skript bearbeiten“, die eine Zeichenfolge in eine andere umwandelt. Es ist sehr eng mit dem Needleman-Wunsch-Algorithmus zum Ausrichten verwendet DNA Sequenzen von Zeichen Spalt eingeführt wird, in dem wir für die Ausrichtung suchen, das eine Punktzahl in O ( nm ) Zeit unter Verwendung von dynamischer Programmierung maximiert. Genaue Übereinstimmungen zwischen den Zeichen erhöhen die Punktzahl, während Mismatches oder eingefügt Lücke Zeichen die Partitur zu reduzieren. Ein Beispiel Ausrichtung von AACTTGCCA und AATGCGAT:

AACTTGCCA-
AA-T-GCGAT
(6 matches, 1 mismatch, 3 gap characters, 3 gap regions)

Wir denken an der Top-Zeichenfolge, die den „Start“ -Sequenz ist, dass wir auf dem Boden in die „endgültige“ Sequenz verwandeln. Jede Spalte ein - Lücke Zeichen auf dem Boden enthält, ist eine Deletion, jede Spalte mit einem - auf der Oberseite ist eine Insertion, und jede Spalte mit verschiedenen (nicht-gap) Zeichen ist eine Substitution. Es gibt 2 Deletionen, Insertion und 1 1-Substitution in der obigen Ausrichtung, so dass der Abstand Levenshtein 4 ist.

Hier ist eine andere Ausrichtung der gleichen Saiten mit der gleichen Levenshtein Entfernung:

AACTTGCCA-
AA--TGCGAT
(6 matches, 1 mismatch, 3 gap characters, 2 gap regions)

Beachten Sie aber, dass, obwohl es die gleiche Anzahl von Lücken ist, gibt es eine weniger Lücke Region . Da biologische Prozesse eher zu breiten Spalten als mehrere getrennte Lücken zu schaffen, bevorzugen Biologen diese Ausrichtung - und so werden die Benutzer des Programms . Dies wird durch erreicht auch die Anzahl der Lückenbereiche zu benachteiligen in den Partituren, dass wir berechnen. Ein O ( nm ) -Algorithmus dies für Zeichenkette der Längen zu erreichen n und M wurde in einem Papier 1982 von Gotoh gegeben genannten „Ein verbesserten Algorithmus zur Anpassung der biologischen Sequenzen“. Leider kann ich keine Links zu kostenlosen Volltext des Papiers finden -. Aber es gibt viele nützliche Tutorien, dass Sie durch googeln „Sequenzabgleich“ finden und „affine gap penalty“

In der Regel verschiedene Möglichkeiten von Spiel, Mismatch, Lücke und Spaltbereich Gewichten unterschiedliche Ausrichtungen geben, aber jede negative Punktzahl für Spaltbereiche wird die untere Ausrichtung oben an die Spitze einen bevorzugen.

Was hat das alles mit Ihrem Problem zu tun? Wenn Sie Gotoh-Algorithmus auf einzelne Zeichen mit einem geeigneten gap penalty verwenden (kam um mit einigen empirischen Tests), sollten Sie eine deutliche Abnahme finden in der die Zahl der schrecklichen aussehende Ausrichtungen wie das Beispiel erhalten haben.

Effizienzüberlegungen

Im Idealfall könnte man nur diese auf Zeichen tun und Linien gänzlich ignorieren, da die affine Strafe zu Cluster Änderungen in Blöcke arbeiten viele Linien, wo Spanning kann es. Aber wegen der höheren Laufzeit kann es realistischer sein, einen ersten Durchgang auf den Leitungen zu tun und dann den Algorithmus auf Zeichen erneut ausführen, als Eingabe alle Zeilen, die nicht identisch sind. Im Rahmen dieser Regelung kann jeder gemeinsamer Block von identischen Linien indem sie sie mit aufgeblasenem passendem Gewicht in einen einzigen „Charakter“ Komprimieren behandelt werden, die keine „Kreuzungen“ erscheinen hilft sicherzustellen.

Answer 3

Hier ist eine mögliche Lösung jemand anderes gerade machte mir klar:

war meine ursprüngliche Ansatz wie folgt aus:

1. Split der Text in einzelne Linien und die Verwendung LCS Algo, um zu bestimmen, wo es Blöcke von Linien Nonmatching.
2. Verwenden Sie einige intelligente algo (die diese Frage zu ist), um herauszufinden, welche dieser Linien eng übereinstimmen, das heißt zu sagen, dass diese Linien zwischen Versionen geändert wurden.
3. Vergleichen diejenigen eng passenden Linien line-by-line LCS mit wieder, während die Markierung der nicht passenden Zeilen als völlig neu.

Während dies für eine bessere visuelle Darstellung der Änderungen erlauben würde, wenn Quellcode Revisionen zu vergleichen, fand ich nun, dass ein wesentlich einfacherer Ansatz in der Regel ausreichend ist. Es funktioniert wie folgt:

1. Wie oben.
2. Nehmen Sie den rechten und linken Block von Nonmatching Linien, verketten diese Zeilen, und tokenize sie (entweder in sprachspezifischen Token / Wörter oder nur in einzelne Zeichen)
3. Tragen Sie die LCS algo auf den beiden Anordnungen von Token.

Vielleicht diejenigen, die antworteten auf meine ursprüngliche Frage ausgegangen, dass ich das alles die Zeit zu tun wusste, aber ich hatte meinen Fokus so stark auf einer Pro-line Vergleich, dass es nicht zu mir kam LCS auf dem Satz von Linien anwenden von ihnen verketten, statt deren Verarbeitung line-by-line.

Also, während dieser Ansatz als detaillierte Änderungsinformationen nicht zur Verfügung stellen, wie meine ursprüngliche Absicht war, es immer noch die Ergebnisse über verbessern, was begann ich gestern mit, wenn ich diese Frage geschrieben hat.

Ich werde diese Frage offen für eine verlassen, während länger - vielleicht jemand anderes, dies alles zu lesen, noch eine vollständige Antwort liefern kann (Pavel und random_hacker angeboten einige Vorschläge, aber es ist keine vollständige Lösung noch - wie auch immer, wir danken Ihnen für die hilfreichen Kommentare).