wie arbeitet diff und co.?

roli · Beitrag von **roli** » 29.03.2006 14:05:06

Hi,

kann mir jemad Quellen nennen wo ich nachlesen kann wie diff und co. arbeiten? Wenn moeglich bitte keinen Verweis auf die Sourcen, dazu gibt's doch bestimmt auch Konzepte, u.U. sogar auf deutsch.
Vor allem interessiert mich, woran erkennt diff das es die gleiche Zeile ist, aber ein Unterschied besteht, bzw. wie die syncronisation zwischen zwei Dateien erfolgt?

meandtheshell · Beitrag von **meandtheshell** » 29.03.2006 14:20:08

diff ist im grunde einfach aufgebaut - im Wesentlichen macht es nichts anderes als Strings Zeilenweise oder in sog. Chunks zu vergleichen
http://www.gnu.org/software/diffutils/m ... /diff.html

markus

roli · Beitrag von **roli** » 29.03.2006 14:30:17

Hi Markus,

"Is ja 'n moerder Link", bis ich das alles durch habe wird wohl noch was Zeit vergehen, trotzdem schon mal danke. Mein Suchen hat naemlich nix brauchbares zu Tage gebracht.
Die wichtigste Frage die ich habe ist, wie wird festgestellt, das es die gleichen Zeilen sind, aber irgendwo eine kleine Aenderung drinnen ist, bzw. es sind zwei komplett verschiedene Zeilen.
Die Syncronisation, ist auch noch spannend, aber das ist fuer mich erstmal Prio 2.

meandtheshell · Beitrag von **meandtheshell** » 29.03.2006 14:48:47

hallo roli,

wie genau es umgesetzt ist kann ich nicht sagen - müsste man einmal in den source code gucken - habe ich noch nicht - möglich wäre
- ein trivialer String vergleich
- hash value bilden und vergleichen
- sonst spassiges

markus

roli · Beitrag von **roli** » 29.03.2006 15:06:28

Hi,

meandtheshell hat geschrieben:müsste man einmal in den source code gucken

genau das moechte ich, wenn moeglich, vermeiden. In jedem "anstaendigen" SW-Entwicklungsprojekt gibt's doch Konzepte

. Wobei, ich bis heute noch nicht oft das Glueck hatte in "anstaendigen" SW-Entwicklungsprojekten zu arbeiten, Konzepte gibts meist gar nicht, werden nach Abschluss der Entwicklung geschrieben, oder "wir haben doch den Quellcode kommentiert".

meandtheshell hat geschrieben:- ein trivialer String vergleich
- hash value bilden und vergleichen
- sonst spassiges

Die Moeglichkeiten sind schon alle richtig, nur ab wann sind's zwei unterschiedliche Zeilen, bzw. zwei mal die gleiche, aber mit einem Unterschied? Muessen z.B. 90 Prozent (oder wieviel auch immer) gleich sein, damit es als gleiche Zeile mit unterschieden erkannt wird?
Oder gibt's da andere magische Kriterien, die mir partou nicht einfallen wollen?

nil · Beitrag von **nil** » 29.03.2006 15:12:21

Die Moeglichkeiten sind schon alle richtig, nur ab wann sind's zwei unterschiedliche Zeilen, bzw. zwei mal die gleiche, aber mit einem Unterschied? Muessen z.B. 90 Prozent (oder wieviel auch immer) gleich sein, damit es als gleiche Zeile mit unterschieden erkannt wird?
Oder gibt's da andere magische Kriterien, die mir partou nicht einfallen wollen?

Einfach Quellcode ziehen und debuggen.

roli · Beitrag von **roli** » 29.03.2006 15:24:49

Hi nil,

nil hat geschrieben:Einfach Quellcode ziehen und debuggen.

genau das ist's ja was ich mit dem eroeffnen des Threads hier vermeiden wollte, ich aber warscheinlich dann doch mal machen muss.
Diff ist doch sicher in C geschrieben, oder? Man ist mein letztes C-Programm lange her, das wird lustig werden ...

Der Link von Markus geht auf eine sehr umfangreiche Seite, aber nach einem ersten ueberfliegen, konnte ich da leider noch nicht finden was jetzt genau das Kriterium (die Kriterien ?) dafuer sind, wann's die selbe Zeile ist, und wann nicht.

meandtheshell · Beitrag von **meandtheshell** » 29.03.2006 15:56:42

roli hat geschrieben: Die Moeglichkeiten sind schon alle richtig, nur ab wann sind's zwei unterschiedliche Zeilen, bzw. zwei mal die gleiche, aber mit einem Unterschied?

Alle drei folgenden sind für diff verschieden

Code: Alles auswählen

The bunny likes green grass.

Code: Alles auswählen

The fat bunny likes green grass.

Code: Alles auswählen

The bunny likes green grass

Zweimal die gleiche mit einem Unteschied gibt es nicht - das ist ein Wiederspurch in sich selbst.
- entweder ident oder
- voneinander verschieden

mehr hier im Link - du vergleichst nur Text - keine binär Daten
http://www.gnu.org/software/diffutils/m ... Comparison

markus

roli · Beitrag von **roli** » 29.03.2006 16:04:37

Hi,

das hatte ich vorhin schon mal ueberflogen, und die "Hunks" auch, nur hat's mir im ersten lesen meine Frage nicht beantwortet.

Zweimal die gleiche mit einem Unteschied gibt es nicht - das ist ein Wiederspurch in sich selbst.
- entweder ident oder
- voneinander verschieden

Vielleicht habe ich's undeutlich ausgedrueckt, was sind denn dann die Zeilen die diff meint, wenn ich einen Output wie "2c2" bekomme. Fuer mich sind das Zeilen, die "prinzipiel" gleich sind, aber irgendwo einen Unterschied haben.
Vergleich mal folgendes:

Code: Alles auswählen

Diese Zeile ich gleich
200101400;200101401;1;;;;Kaesekuchen;;;2;2005-12-23;97

mit

Code: Alles auswählen

Diese Zeile ist gleich
200101400;200101401;1;;;;Kaesekuchen;;;2;2005-12-29;97

Dann sieh'st du was ich meine.
<edit>Joh, mir geht's um reinen Textvergleich, nix binaeres</edit>

seep · Beitrag von **seep** » 29.03.2006 17:16:21

Ähm, bei Deinem Beispiel gibt es aber folgendes, da die beiden Zeilen ja unterschiedlich sind:

Code: Alles auswählen

1,2c1,2
< Diese Zeile ich gleich
< 200101400;200101401;1;;;;Kaesekuchen;;;2;2005-12-23;97
---
> Diese Zeile ist gleich
> 200101400;200101401;1;;;;Kaesekuchen;;;2;2005-12-29;97

Typo beim Beispiel oder habe ich jetzt als interessierter Beobachter einen Knick im Hirn?

meandtheshell · Beitrag von **meandtheshell** » 29.03.2006 17:55:56

@roli
hä?
Keine Ahnung wovon du sprichst - IMO steht alles sehr gut im manual - nein?

/nursery school mode on

fct
Replace the lines in range f of the first file with lines in range t of the second file. This is like a combined add and delete, but more compact. For example, 5,7c8,10 means change lines 5-7 of file 1 to read as lines 8-10 of file 2; or, if changing file 2 into file 1, change lines 8-10 of file 2 to read as lines 5-7 of file 1.

/nursery school mode off

markus

roli · Beitrag von **roli** » 29.03.2006 19:31:28

Hi Ihr 2,

ich vermute mal das das Problem ist, das ich's nicht rueberbringen kann

Vielleicht habe aber auch nur ich 'nen Knoten im Hirn und begreiff nicht was jedem anderen vielleicht logisch erscheint.
In der zweiten Zeile aus meinem Beispiel habe ich das Datum verdreht von "2005-12-23" zu "2005-12-29", richtig.
Das ist jetzt genau das worum's mir geht, woher weiss diff jetzt, das diese zwei Zeilen was miteinander zu tun haben? Warum werden diese Zeilen miteinander verglichen, und nicht die ggf. 999 anderen in einer Datei? Man koennte sich ja auch auf den Standpunkt stellen die Zeile mit dem "2005-12-23" fehlt in der anderen Datei. Fuer die zweite Datei mit "2005-12-29" dito.
Warum sagt mir diff diese Zeilen unterscheiden sich, und nicht jede der beiden Dateien enthaelt eine "zusaetzliche" Zeile, die in der anderen Datei nicht enthalten ist?

meandtheshell · Beitrag von **meandtheshell** » 29.03.2006 20:06:16

@roli
wenn du so weiter machst schaffst du es noch das ich am Ende auch nichts mehr weiß - irritiert bin ich schon

diff vergleicht zwei oder mehr files oder directories in welchen diese vorkommen rekursiv Zeilenweise.

Wenn auch nur ein einziger character von File A in Zeile n nicht derselbe ist wie jene in Zeile n in File B dann ist das ein Unterschied denn diff darstellt. Auch ein blank usw. zählen da ...

evtl. hilft dir wenn du siehst wie das funkt

Code: Alles auswählen

apt-get install meld

markus

seep · Beitrag von **seep** » 29.03.2006 20:16:30

@roli:

Ich denke, zwei zentrale Sätze in der Doku sind diese hier:

Code: Alles auswählen

What comparison means
...
diff compares two files line by line, finds groups of lines that differ, and reports each group of differing lines.

und

Code: Alles auswählen

Hunks
...
diff tries to minimize the total hunk size by finding large sequences of common lines interspersed with small hunks of differing lines.

diff sucht also in erster Linie nach Gemeinsamkeiten, und wenn es diese gefunden hat, dann schaut es, was sich zwischen den Gemeinsamkeiten tut. Alles, was zwischen den Gemeinsamkeiten befindet, sind Unterschiede (logisch). Und bei denen schaut es halt, ob für eine Zeile hier eine Zeile dort rausmuß (change) oder nicht (insert). Das "wie" steckt dann wohl im Algorithmus sprich im Sourcecode verborgen.

diff ist oft schlau, ich habe aber auch schon Fälle gehabt, bei denen es mir bei zwei Zehntausendzeilern mit nur zwei Zeilen Unterschied kilobyteweise Ausgaben erzeugt hat - 8.000 mal "tausche diese Zeile aus" - eventuell war ich aber auch nicht schlau genu, die passende diff-Option zu verwenden.

roli · Beitrag von **roli** » 29.03.2006 20:56:33

Hi,

das ist mein letztes Posting fuer heute, versprochen.
@markus: wenn man irritiert ist denkt man nochmal drueber nach, das ist mir also schon mal gelungen.
@seep: das Problem das du beschreibst kenne ich nur zu gut, leider. Daher will ich jetzt mal verstehen wie (bei diff) der Hase laeuft, um es ggf. selber besser zu machen.

Vielleicht traue ich diff einfach zuviel zu, vielleicht muss ich wirklich in den Quellcode. Was ich halt (noch) nicht begreiffe, wie unterscheidet das ding, ob eine Zeile hinzugekommen, bzw. geloescht wurde oder ob sie veraendert ist/werden muss?

seep · Beitrag von **seep** » 30.03.2006 07:59:58

Moin allerseits,

ich habe mal zwei Dateien konstruiert, an denen man die Vorgehensweise wohl einigermaßen veranschaulichen kann (so denke ich jedenfalls):

Code: Alles auswählen

Diese Zeile nur in 1
Diese Zeile in beiden Dateien
Diese Zeile auch in beiden Dateien
Diese Zeile auch nur in 1
Diese Zeile wieder in beiden Dateien
Diese Zeile auch wieder nur in 1
Diese Zeile in beiden Dateien am Ende

... und ...

Code: Alles auswählen

Diese Zeile in beiden Dateien
Diese Zeile auch in beiden Dateien
Diese Zeile nur in 2
Diese Zeile wieder in beiden Dateien
Diese Zeile wieder nur in 2
Diese Zeile in beiden Dateien am Ende

Ergebnis von diff:

Code: Alles auswählen

1d0
< Diese Zeile nur in 1
4c3
< Diese Zeile auch nur in 1
---
> Diese Zeile nur in 2
6c5
< Diese Zeile auch wieder nur in 1
---
> Diese Zeile wieder nur in 2

Ohne in die Sourcen von diff geschaut zu haben vermute ich mal, daß es ansatzweise so vorgeht:

1. Aus beiden Dateien eine Zeile lesen und vergleichen. Ergebnis: Unterschied. Daher: Zeilen puffern.
2. Aus beiden Dateien eine Zeile lesen. Direkter Vergleich: Unterschied. Zeile1 mit Zeilen aus Puffer2 vergleichen: noch nicht drin. Zeile2 mit Zeilen aus Puffer1 vergleichen: Treffer ("Diese Zeile in beiden Dateien"). Ergo: Alle Zeilen aus Puffer1 müssen eingefügt worden sein.
3. Puffer leeren, weitermachen.

So geht das dann prinzipiell weiter. Beim Erkennen einer Gemeinsamkeit wird in den gepufferten Zeilen geschaut, was sich getan hat. Ist ein Puffer leer, wird ein Insert oder Delete daraus, je nachdem, aus welcher Richtung man schaut. Sind beide Puffer gefüllt - sprich: zwischen den gefundenen Gemeinsamkeiten stehen in beiden Dateien Zeilen - wird ein change daraus.

roli · Beitrag von **roli** » 30.03.2006 09:35:27

Moin,

hoert sich plausiebel an, was du schreib'st. Leider habe ich heute Morgen nicht die Zeit mich intensiv damit zu beschaeftigen, muss ich spaeter machen. Jedenfalls schon mal danke.