Genauer Zeilenvergleich zweier Textdateien - wie ?

[OregonGhost]

Ich weiß nicht, ob dir klar ist, worum es bei Diffs geht. Es werden immer und ausdrücklich zwei Dateien miteinander verglichen, typischerweise eine ältere und eine neuere. Zeilen, die in der älteren existieren und in der neueren nicht, werden in der neueren als gelöscht markiert. Zeilen, die in der älteren nicht existieren, jedoch in der neueren, werden als hinzugekommen markiert. Und Zeilen, die in beiden existieren, sich jedoch voneinander unterscheiden, werden als geändert markiert. Wer eine solche Änderung wann gemacht hat, spielt hierbei keine Rolle. Wenn man so etwas wissen will, braucht man in der Tat eine Historie, aber das ist dann die Aufgabe einer Versionsverwaltung (Blame lässt grüßen).

[taaktaak]

Hallo Florian!

Ahhhh, ja - da hatte ich echt ein "Brett vor dem Kopf". Erst deine letzte Erläuterung hat dieses Stückchen Holz entfernen können. Natürlich, jetzt verstehe ich's - da ist meine ergänzende Bemerkung natürlich unsinnig.

Danke!
Gruß Ralph

[grenzgaenger]

Zitat von omata:

Kennst du solche Tools nicht?
Mein angegebener Link auf KDiff3 ist, wie ich finde, ein sehr schönes Beispiel. Das Tool einfach nur genial.

Und das hat rein gar nichts mit Wahrscheinlichkeiten zu tun...

klar kenne ich solche progys, gabs schon vor 20 jahren auf unix, mittlerweile hat es auch delphi gelernt. aber die progies raten nur mehr oder weniger gut.

aber es kommt auf den anwendungsfall an, was er wirklich braucht,... eine exakte darstellung oder reicht eine schätzung? ausserdem ist das datenformat interessant, handelt es sich um eine text datei, datenbank oder irgend etwas anderes... auch die frage, ob er selbst einfluss drauf hat (z. B. nur sein progy die änderung macht) oder ob auch fremdprogamme ändern ...

aber wie es aussieht, genügt ihn eine grobe schätzung einer textdatei ...

[tomsson74]

Bei dem Beispiel geht es um reine Textdateien mit Zeilenumbrüchen. Wenn ich also zwei am Anfang identische (!) Dateien habe von denen die "Datei 2" verändert wird, so kann ich durch einen Vergleich der beiden Files GENAU feststellen, wie sich Datei 2 gegenüber der Datei 1 verändert hat - was dazugekommen ist und was gelöscht wurde. Die Programme raten nicht, sie ermitteln die Unterschiede durch einen mehr oder weniger komplizierten Algorithmus. Dabei spielt es keine Rolle wer die Datei 2 verändert hat.

Schau Dir das nochmal an:

Datei 1 ist die Ausgangsdatei und Datei 2 ist die veränderte Datei

Code:

Datei 1:      Datei 2:

Zeile 1       Zeile 1
Zeile 2       Neue Zeile eingefügt
Zeile 3       Zeile 2
Zeile 4       Zeilee 3
Zeile 5       Zeile 6
Zeile 6

Man kann alleine durchs Hinschauen mit 100% Genauigkeit sagen was in der Datei 2 verändert wurde.

Bist Du sicher das wir über die gleiche Problematik sprechen ?



/Thomas

[Medium]

Auf dieses Ergebniss kann ich auch kommen, indem ich eine Löschung und 4 Inhaltsänderungen durchführe. Darauf will er hinaus, und er hat Recht. Es ist lediglich eine Vermutung, dass Zeile2 durch eine Einfügung nach unten verschoben wurde, und ist für das menschliche Hirn auch sofort schlüssig. Naiv betrachtet kann aber genau so gut jemand die "3" gegen eine "2" ersetzt haben, und damit wirds eine Inhaltsänderung.

Ohne semantische Analyse oder Changelog wird es wirklich verdammt schwierig das sicher zu entscheiden. Wenn ich in einer Datei eine Zeile mitten drin einfüge, kann ich an und für sich auch einfach ab dieser Zeile alle weiteren geändert haben, und am Ende eine hinzugefügt in die der Inhalt der vormals letzten kommt. Dass das kein Mensch tun würde ist dem Menschen klar, einem Algo zunächst einmal nicht so wirklich.

[alzaimar]

Das wird mit Mustererkennung und maximalen Abständen gehen.

Eine Zeile wurde eingefügt, wenn das folgende Muster in der anderen Datei wiedererkannt wird. Dabei kann man Zeichen- oder Zeilenweise vorgehen.

Hier mal eine Möglichkeit, das zeilenweise zu machen.
Die Algorithmen versuchen jeweils, durch fiktive Einfüge- und Löschoperationen D1 und D2 grob zu synchronisieren. Es spielt zunächst auch keine Rolle, ob die 'synchronen' Zeilen identisch sind, es reicht, wenn sie ähnlich sind (Levenshtein).

Der Algorithmus versucht, bei Ungleichkeit zweier Zeilen den Folgetext in der jeweils anderen Datei an einer späteren Stelle wiederzufinden.
Im Beispiel ist es so:
In Datei 2 wurde 'Neue Zeile eingefügt' sowie 'Zeile 4' und 'Zeile 5' gelöscht, eben weil 'Neue Zeile...' in D1 nicht, aber 'Zeile 6' (kommt nach der Z4 und Z5) in D2 sehr wohl.


Nun kann man die beiden dateien schon etwas besser vergleichen

Code:

Datei 1:      Datei 2:

Zeile 1       Zeile 1
-----         Neue Zeile eingefügt
Zeile 2       Zeile 2
Zeile 3       Zeilee 3
Zeile 4       ---
Zeile 5       ---
Zeile 6       Zeile 6

Die 3.Zeilen sind zwar nicht identisch, aber ähnlich. Der o.g. Algorithmus auf Zeichen statt Zeilen angewandt zeigt, das das 'e' eingefügt wurde.


Es ist doch völlig wurscht, ob D2 durch die o.g. Operationen (Einfügen, Löschen, Ändern) oder durch ein völliges Neuschreiben entstanden sind. Es sollen die UNTERSCHIEDE gezeigt werden, und nicht, was der Bearbeiter vielleicht alles eingetippt hat.

[Medium]

Nun, wenn es nur um die Unterschiede geht, reicht ja ne xor-Verknüpfung der 2 Dateien

Das Problem, dass wir hier nun haben ist, dass es gilt "Unterschiede" mal genau zu definieren, und u.U. in Klassen von Unterschieden aufzugliedern. Der TE schrieb nämlich sehr genau, dass er tatsächlich in die vorgenommenen Operationen aufschlüsseln möchte. Eine wie von dir genannte Heuristik kann sowas sicherlich näherungsweise herleiten, ist aber auch schon komplex genug um in den Bereich der künstlichen Intelligenz zu ragen wenn mans gut und konsequent machen mag. Aber wirkliche Auskunft über das was von A zu B geführt hat, wird ohne weitere Informationen schlicht und ergreifend nicht gesichert möglich sein.

\\Edit: Das Matching, dass du oben durchführt hast ist meiner Meinung nach schon das höchste der Gefühle. Bei einer Änderung einer Zeile kommt aber dann die Unschärfe: Wenn mehrere Zeilen in Frage kommen (Zeile 3, 4 und 5 hier), muss man entscheiden welche derer geändert wurde. Die Distanz ist eine gute Schätzung, aber wie weit geht es? Ab wann ist es eine Löschung+Einfügung? Ich könnte auch "Zeile 4" in "Zeilee 3" geändert haben usw.

[tomsson74]

Zitat von Medium:

Ich könnte auch "Zeile 4" in "Zeilee 3" geändert haben usw.

Ich würde sagen, dass es nicht der Fall sein kann. Denn durch die vorangegangenen Vergleiche ist die Zeile 4 der Ursprungsdatei schon unterhalb der "Zeilee 3" der Datei 2 und damit kein Kandidat für eine erfolgte Änderung.

Tatsache ist, zwischen Zeile 2 und Zeile 6 gibt es Änderungen in der Datei 2. Es gilt also die drei dazwischenliegenden Zeilen zu vergleichen. Und der Vergleich ergibt nun mal, dass Zeile 3 geändert wurde und Zeile 4 und 5 weggefallen sein müssen. Bei diesen drei Zeilen kann es m.E. gar keine Konstellation geben.

Das was ich wissen will, bekomme ich auch: 1 Änderung, 2 Löschung.

Zudem ist die Datei 1 immer die Basisdatei mit der verglichen wird. Es geht immer nur um Änderungen der Datei 2.

/Thomas

[OregonGhost]

Vielleicht ist einigen nicht ganz klar, was der Zweck eines solchen Tools ist. Es geht darum, Änderungen zu erkennen. Wie, wann oder warum diese Änderungen durchgeführt wurden, spielt keine Rolle. Natürlich kann es dabei vorkommen, dass die "erkannte" Änderung nicht genau mit der tatsächlichen übereinstimmt - aber das ist vollkommen egal. Entscheidend ist, dass man auf Anhieb erkennt, was geändert wurde. Und die meisten der genannten Diff-Tools leisten genau das und sie raten dabei nicht. Jeder, der eine Versionsverwaltung verwendet (und das sollte ja wohl jeder professionelle Entwickler sein), benutzt diese Tools und sie erfüllen diesen Zweck wunderbar. Da muss man nicht die ganze Zeit drüber reden, dass ein Tool nicht erkennen kann, wenn man ein Zeichen gelöscht und dann wieder eingetippt hat. Es gibt nichts zu definieren, der Topic-Eröffner möchte ein Tool (schreiben), das genau das macht, was die anderen Diff-Tools auch machen. Wem also nicht ganz klar ist, was hier gesucht wird, sollte sich ein solches Diff-Tool einfach mal näher anschauen.

Es macht zum Beispiel auch keinen Unterschied, welche der drei Zeilen vielleicht die geänderte ist, und welche zwei gelöscht wurden. Entscheidend ist: "Links" (in der alten Datei) sind die drei Zeilen vorhanden, "rechts" (in der neuen Datei) ist nur noch eine Zeile vorhanden. Ob jetzt eine der drei als Änderung erkannt wird und zwei als Löschung, oder ob alle drei als gelöscht und die neue als hinzugekommen markiert sind (beides findet man in typischen Diff-Tools), spielt keine große Rolle. Der Benutzer weiß sofort, was geschehen ist und nur darum geht es.

[Medium]

Zitat von OregonGhost:

Es geht darum, Änderungen zu erkennen. Wie, wann oder warum diese Änderungen durchgeführt wurden, spielt keine Rolle. Natürlich kann es dabei vorkommen, dass die "erkannte" Änderung nicht genau mit der tatsächlichen übereinstimmt - aber das ist vollkommen egal.

Im ersten Posting war dem so, also gehe ich erstmal davon aus, dass der TE den "Werdegang" exakt nachvollziehen will. Wer weniger will als er fragt, darf sich nicht über philosophiebeladene Antworten wundern.

Zitat von OregonGhost:

Entscheidend ist, dass man auf Anhieb erkennt, was geändert wurde. Und die meisten der genannten Diff-Tools leisten genau das und sie raten dabei nicht.

Wie jetzt? Zeigen sie was geändert wurde, oder welche Operationen auch dort hin führen? Ein eklatanter Unterschied finde ich, und bislang wird das hier gerne undifferenziert betrachtet.

Zitat von OregonGhost:

Da muss man nicht die ganze Zeit drüber reden, dass ein Tool nicht erkennen kann, wenn man ein Zeichen gelöscht und dann wieder eingetippt hat.

Und in der Bibel steht...
Zum einen ist es nie falsch sich darüber im Klaren zu werden wo die Grenzen genau liegen, und zum anderen war zumindest im Eingangsposting an keiner Stelle von Diff-Tools die Rede. Es wurde später lediglich impliziert, dass die Funktionalität wohl dem nahe kommt, mehr nicht. Und wenn ich ein Programm schreiben wollte, dass eine schon vielfach abgedeckte Funktion bietet, so würde ich zumindest versuchen das besser/schlauer zu machen - z.B. indem mein Diff-Tool eine exakte Abbildung liefert. Falsche Annahme meinerseits.

Zitat von OregonGhost:

Es gibt nichts zu definieren, der Topic-Eröffner möchte ein Tool (schreiben), das genau das macht, was die anderen Diff-Tools auch machen.

Hast du so verstanden, ich nicht.

Zitat von OregonGhost:

Es macht zum Beispiel auch keinen Unterschied, welche der drei Zeilen vielleicht die geänderte ist, und welche zwei gelöscht wurden. Entscheidend ist: "Links" (in der alten Datei) sind die drei Zeilen vorhanden, "rechts" (in der neuen Datei) ist nur noch eine Zeile vorhanden. Ob jetzt eine der drei als Änderung erkannt wird und zwei als Löschung, oder ob alle drei als gelöscht und die neue als hinzugekommen markiert sind (beides findet man in typischen Diff-Tools), spielt keine große Rolle. Der Benutzer weiß sofort, was geschehen ist und nur darum geht es.

Weiss er streng genommen eben nicht! Er weiss bestenfalls was geschehen sein könnte, und einen Schritt weiter sogar wie man mit den wenigsten Zwischenschritten dort hin kommen kann, aber NICHT was im Einzelnen geändert wurde. Dass das hier wohl garnicht so sehr von Interesse ist, hat der TE nirgends explizit gesagt.

--------------------------------------------------------------

Das Schlagwort von alzaimar welches mich hierzu auf eine Idee bringt: Levenshtein-Distanz
Wendet man diese nicht Zeichenweise auf einzelne Zeilen, sondern Zeilenweise auf den gesamten Text an, entstehen auf dem Weg dahin alle Informationen die hier nun geklärterweise gewünscht sind, wobei eine Änderung als Löschung+Einfügung behandelt würde. Zudem dürfte die so extrahierte Pseudo-Historie wenn nicht ganz, zumindest nah am optimalen Weg liegen. Als Bonus bekommt man am Ende sogar noch eine Maßzahl für den Grad der Differenz der Dateien.