Genauer Zeilenvergleich zweier Textdateien - wie ?

[tomsson74]

Hallo,

ich suche einen schnellen Algorithmus (falls es überhaupt einen gibt) mit dem man Unterschiede in zwei Dateien farblich markieren kann - im Prinzip ein FileCompare für Textdateien.

Habe schon die Suche hier bemüht, bin aber nicht wirklich erfolgreich gewesen.

Zur Veranschaulichung meines Anliegens ein kleines Beispiel. Ich gehe von 2 Dateien aus. Beide sind am Anfang identisch - Datei 2 ist eine Kopie von Datei 1.

Code:

Datei 1:      Datei 2:

Zeile 1       Zeile 1
Zeile 2       Zeile 2
Zeile 3       Zeile 3
Zeile 4       Zeile 4
Zeile 5       Zeile 5
Zeile 6       Zeile 6

Nun werden an der Datei 2 folgende Änderungen vorgenommen:

1. Hinter "Zeile 1" wurde eine neue Zeile hinzugefügt
2. "Zeile 3" wurde in "Zeilee 3" geändert
3. Zeilen 4 und 5 wurden gelöscht

Das Ergebnis sieht dann so aus

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

Jetzt möchte ich diese beiden Dateien miteinander vergleichen um zu sehen was ich in der Datei 2 gegenüber der Datei 1 verändert hat. Was ich nun als Ergebnis bräuchte wäre in etwas sowas:

Code:

Datei 1:      Datei 2:

Zeile 1       Zeile 1
              Neue Zeile eingefügt (in grün - steht für "neu hinzugekommen")
Zeile 2       Zeile 2
Zeile 3       Zeilee 3 (in blau - steht für "modifiziert")
Zeile 4       Zeile 4  (in rot - steht für "gelöscht")
Zeile 5       Zeile 5  (in rot - steht für "gelöscht")
Zeile 6       Zeile 6

Hat jemand evtl. sowas schon gemacht und kann mir ein paar Tipps geben ?

Grüße
Thomas

[omata]

Schau doch mal hier.

Aber vermutlich willst du das selber programmieren, dann sorry für meine Antwort.

Edit: Das kommt dir vermutlich besser entgegen.

Gruss
Thorsten

[Flocke]

Ich hab' mal eine Diff-Unit zu einem Thread von Sharky geschrieben, den Sourcecode findest du auf meiner Seite (mit "Zurück zur Übersicht" auch einen ZIP-Download mit einem Testprogramm).

[grenzgaenger]

sorry, mal eine unbedeutende frage, wie willst du wissen ob eine zeile eingefügt wurde oder ob die selbe zeile neu geschrieben wurde? hier kannst du nur mit wahrscheinlichkeiten mit einem blick in die kristallkugel hantieren. sicher kannst du das nie sagen. du kannst höchstens versuchen voraus- und zurückschauend zu analysieren und dann über bestimmete wahrscheinlichkeiten ausagen treffen... aber das ist nix halbes und nix ganzes ... als einfaches hilfsmittel könnte das noch genügen... aber zuverlässig ist das nicht...

... für was brauchste das?

[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...

[tomsson74]

Hallo,

danke für die bisherigen Antworten - das hilft mir schon weiter. Ich werde mir die Beschreibungen zu Gemüte ziehen. Das ist zwar schwere Kost aber ich möchte das auch verstehen und nicht nur anwenden :D

Zitat:

Zitat von grenzgaenger

sorry, mal eine unbedeutende frage, wie willst du wissen ob eine zeile eingefügt wurde oder ob die selbe zeile neu geschrieben wurde? hier kannst du nur mit wahrscheinlichkeiten mit einem blick in die kristallkugel hantieren.

Das hat nichts mit Wahrscheinlichkeiten zu tun, diese Tools funktionieren wirklich - und das sehr zuverlässig :)

Grüße
Thomas

[OregonGhost]

Zitat:

Zitat von tomsson74

Zitat:

Zitat von grenzgaenger

sorry, mal eine unbedeutende frage, wie willst du wissen ob eine zeile eingefügt wurde oder ob die selbe zeile neu geschrieben wurde? hier kannst du nur mit wahrscheinlichkeiten mit einem blick in die kristallkugel hantieren.

Das hat nichts mit Wahrscheinlichkeiten zu tun, diese Tools funktionieren wirklich - und das sehr zuverlässig :)

Das ist nicht ganz richtig, ein Tool kann nicht wissen, ob eine Zeile eingefügt oder neu geschrieben wurde. Aber die Frage an sich ist schon falsch. Es macht keinen Unterschied, ob eine Zeile neu geschrieben oder eingefügt wurde. Sie war vorher nicht da und jetzt ist sie da.
Hach, wie schön, wenn man den Tag mit etwas Haarspalterei beginnen kann.

Jedenfalls wollte ich nochmal Kompare und das Diff-Tool von TortoiseSVN in den Raum werfen. Ersteres ist definitiv eins der hübschesten, beide sind im Quellcode erhältlich und das zweite ist für Windows. Ich halte es zwar nur für begrenzt sinnvoll, sich ein neues Tool dafür zu bauen, wenn es schon genug gibt, aber diese zwei sind sicherlich ein guter Anlaufpunkt, um sich die Algorithmen mal näher anzuschauen. Kompare markiert auch einzelne Änderungen innerhalb einer Zeile, so dass man die Änderung leichter findet.

Und zur Frage, wozu man so etwas braucht - für professionelle Quellcode-Versionsverwaltung sind solche Tools absolut unverzichtbar.

[taaktaak]

Moin, Moin.
Um die Haarspalterei weiter zu führen: Es ist ja nicht nur die Frage, ob eine Zeile in der einen Datei neu eingefügt oder eine bestehende Zeile verändert wurde. Es kann ja auch in der "anderen" Datei eine Zeile gelöscht worden sein, dann wurde in der betrachteten Datei weder etwas eingefügt, noch verändert. Trotzdem sind die Dateien dann unterschiedlich. Um diese Veränderung korrekt zu verfolgen - und zu benennen - müsste m.E. eine Historie der Vergleiche gespeichert werden.
Gruß Ralph

[OregonGhost]

Wenn in der zweiten Datei eine Zeile gelöscht wurde, wird sie in der ersten Datei als gelöscht markiert. Dazu braucht man noch keine Historie.

[taaktaak]

Ähhh, habe ich da jetzt was übersehen? Wenn ich mit einem beliebigen Programm in einer beliebigen Datei eine Zeile lösche, wie kann dann in einer zweiten (unbekannten) Datei eine Löschmarkierung gesetzt werden?
Gruß Ralph

[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. :oops:

Danke!
Gruß Ralph

[grenzgaenger]

Zitat:

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 ... :mrgreen: ;-)

[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:

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:

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:

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:

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:

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:

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.

[shmia]

Die Mutter aller Vergleichstools ist wohl diff aus der Unix Welt.
Es gibt 3 prinzipielle Operationen, um Datei A nach B zu überführen:
a=append
c=change
d=delete
Aus zwei Dateien entsteht dann das sogenannte "Normalformat".
Wenn ich nur die Datei A habe, dann kann ich mit Hilfe des Normalformat die Datei B rekonstruieren.
(und umgekehrt)
Hier wird das Prinzip gezeigt: http://www.gnu.org/software/diffutil...ailed%20Normal

Viele Vergleichstools gehen so vor, dass sie Gnu diff als Preprozessor verwenden und dessen Output visualisieren.
Für Hobbyprogrammierer ist dies das ideale Verfahren (zumindest im 1. Schritt)

Andere Tools haben sich aus dem Sourcecode Gnu diff (in dem viel Erfahrung und Mann/Frau-jahre stecken) bedient und nehmen den Vergleich selbst vor.

Der "Trick" von Gnu diff ist nun, möglichst wenige Zeilen im Normalformat zu erzeugen.

[omata]

Zitat:

Zitat von tomsson74

ich suche einen schnellen Algorithmus (falls es überhaupt einen gibt) mit dem man Unterschiede in zwei Dateien farblich markieren kann ...

Code:

Datei 1:      Datei 2:

Zeile 1       Zeile 1
Zeile 2       Zeile 2
Zeile 3       Zeile 3
Zeile 4       Zeile 4
Zeile 5       Zeile 5
Zeile 6       Zeile 6

Hat jemand evtl. sowas schon gemacht und kann mir ein paar Tipps geben ?

Diese Ausgangslage war eigentlich gut zu verstehen. Es ging hier um konkrete Lösungsvorschläge und nicht darum, dass man lieber im Bett bleiben und es gleich lassen sollte.
Wie auch immer, der angegebene Link (siehe #2) enthält ein Beispiel mit allen Sourcen. Als Ergebnis zur Wunschvorstellung aus dem Ausgangspost liefert dieser Code folgende Ausgabe... (siehe Anhang).

Ich weiss nicht, was es daran nun noch rumphilosophieren gibt. Das ist eine Aufgabe, die nicht ganz einfach ist, aber dennoch lösbar. Und natürlich kann man hier gerne diskutieren, aber bitte mit konstruktiven, sinnvollen, durchdachten, positiven, konkreten Beispielen, die den Fragenden auch weiterbringen und nicht nur diesen Thread mit heißer Luft länger werden lässt.

Und nun steinigt mich...

Gruss
Thorsten

[Medium]

Ihr wollt nicht verstehen worauf ich hinaus will, also lassen wir es einfach. Mein konstruktiver Vorschlag ging zudem auch darin unter, also Feierabend hier für mich. Dennoch schön, dass generell geholfen werden konnte.