Open Source im professionellen Einsatz
Linux-Magazin 01/2007
© Martine Affre Eisenlohr/Fotolia

© Martine Affre Eisenlohr/Fotolia

Algorithmen hinter Diff

Der feine Unterschied

Diff findet Veränderungen zwischen unterschiedlichen Versionen einer Datei. Was auf den ersten Blick trivial wirkt, wird bei großen Dateien schnell zum Ressourcenproblem, wenn eingefügte oder gelöschte Zeichen die unveränderten Stellen gegeneinander verschieben.

1752

Änderungen zwischen zwei Textdateien herauszufinden ist in der Praxis nicht schwer: Ein Aufruf von »diff Version_1.txt Version_2.txt« genügt. Zunächst scheint es so, dass auch Diff selbst keine Wunder vollbringen muss, um veränderte Stellen zu markieren. Bei großen Dateien ist jedoch viel Speicherplatz nötig, um herauszufinden, wo sich der Datei-Inhalt wirklich verändert hat oder wo sich der Inhalt durch Einfügungen oder Streichungen gegenüber der ursprünglichen Version nur verschoben hat. Dieser Artikel erläutert, wie Diff es bei Dateien von vielen MByte Größe schafft, Veränderungen und Übereinstimmungen zu finden, ohne die Rechnerressourcen zu sehr in Anspruch zu nehmen.

Editierdistanz

Jede Zeichenkette lässt sich durch Einfügen, Löschen oder Ersetzen einzelner Zeichen in jede beliebige andere verändern. Eine Möglichkeit, aus dem Wort Tier das Wort Tor zu machen, wären die Änderungsoperationen Tier -> Ter -> Tr -> Tor. Es gibt jedoch eine Alternative mit weniger Zwischenschritten, nämlich Tier -> Ter -> Tor. Diese geringste mögliche Anzahl an Änderungsschritten ist ein Maß für die Ähnlichkeit zweier Zeichenketten. Sie heißt Levenshtein- oder Editierdistanz und bildet die Grundlage für die effiziente Auszeichnung der Veränderungen in Diff.

Bei den meisten Vergleichen in der Praxis ist der größte Teil der Dateien unverändert. Erster Schritt ist daher, alle identischen Stellen auszuschließen. Um diese zu finden, auch wenn sie sich gegenüber dem Original verschoben haben, hilft es, den Text in einer Matrix wie in Abbildung 1 anzuordnen. Die Zahlen in der Tabelle bezeichnen die Differenz der Bytewerte der einzelnen Zeichen, eine Null kennzeichnet folglich einen unveränderten Buchstaben. Die längste dieser Übereinstimmungen heißt Longest Common Subsequence oder LCS. Die Editierdistanz ergibt sich über die Formel »d(X, Y) = n + m – 2 * |LCS (X, Y )|« mit »X = x_1 ... x_n« und »Y = y_1 ... y_m« direkt aus der Länge der LCS.

Abbildung 1: Die Matrix-Darstellung macht Übereinstimmungen (Nullwerte) auch sichtbar, wenn sich die Position der Zeichen zwischen den Dateiversionen verschoben hat.

In einer solchen Matrix ist es leicht, Verschiebungen zu erkennen: Im Vergleich von »otter« und »lotto« (Abbildung 2) liegen die Nullen, also die Übereinstimmungen, auf einer absteigenden Linie, die parallel zur Hauptdiagonalen der Matrix (der Diagonalen von links oben nach rechts unten) verläuft. Vertauschungen (»teir« zu »tier«, Abbildung 3) sind in der Matrix als Bruchstellen zu erkennen, durch deren Zentrum Nullen senkrecht zur Hauptdiagonalen verlaufen.

Abbildung 2: Übereinstimmende Teilsequenzen sind in der Matrix als Diagonale aus Nullwerten zu erkennen, die parallel zur Hauptdiagonalen verläuft.

Abbildung 3: Vertauschungen erscheinen in der Matrix als unterbrochene Diagonale von Nullen. Die vertauschten Zeichen liegen auf einer zur Diagonalen senkrecht stehenden Linie.

So genannte Palindrome (Umkehrungen der Buchstabenreihenfolge) spiegeln sich in einer Abfolge von Nullwerten von rechts unten nach rechts oben (der Nebendiagonalen) in der Matrix wieder (Abbildung 4).

Rechenzeitoptimierung

Die Größe der Matrix hängt von der Länge der zu vergleichenden Texte ab. Bei zwei Dateien der Größe 10 KByte ergibt das immerhin 10 000 * 10 000= 100 000 000 Vergleiche und damit einen RAM-Bedarf von 100 MByte allein für die Matrix. Die Suche nach Übereinstimmungen belegt weiteren Speicher. Doch wenn ein Rechenprozess Werte mehrfach berechnet, lässt er sich optimieren. Das so genannte dynamische Programmieren (siehe Kasten „Dynamisches Programmieren“) verringert Speicherbedarf und Rechenzeit.

Dynamisches Programmieren

Dynamisches Programmieren ist ein wichtiges Prinzip in der Informatik und wird oft für die Lösung von Optimierungsproblemen eingesetzt: In vielen Fällen ist es effizienter, ein Problem zu zerlegen, die Teillösungen zu ermitteln und diese für den weiteren Rechenweg erneut zu nutzen.

Ein einfaches Beispiel aus der Zeit, als Rechnerressourcen noch knapp waren, ist die Potenzrechnung: Soll die achte Potenz einer Zahl gebildet werden, lässt sich »n*n*n*n * n*n*n*n« in die Zwischenschritte »((n*n) * (n*n)) * ((n*n) * (n*n))« aufteilen. Wird das Ergebnis von »(n*n)« und »((n*n)*(n*n))« zwischengespeichert, dann sind statt sieben nur noch drei Multiplikationen nötig.

Dynamisches Programmieren hält die Zahl der Vergleiche auch beim Gegenüberstellen von Textversionen in einer Matrix niedrig: Statt der bitweisen Differenz zwischen einzelnen Zeichen enthält die Matrix in Abbildung 4 die Länge der übereinstimmenden Teilsequenz, die an dieser Stelle zusammen mit den vorausgehenden Zeichen besteht. Listing 1 zeigt Perl-Code, der das Verfahren implementiert.

Abbildung 4: Palindrome (Umkehrungen der Buchstabenreihenfolge) sind in der Matrix als Diagonale von links unten nach recht oben zu erkennen.

Listing 1: Suche nach der LCS

01 sub lcs {
02    my $refmatrix=shift;
03    my $refxlst=shift;
04    my $refylst=shift;
05    my $m=scalar @$refxlst-1;
06    my $n=scalar @$refylst-1;
07    foreach my $i (1 .. $m) {
08       foreach my $j (1 .. $n) {
09          if ($refxlst->[$i] eq $refylst->[$j]) {
10             $refmatrix->[$i]->[$j] = $refmatrix->[$i-1]->[$j-1]+1;
11          } elsif ($refmatrix->[$i-1]->[$j] >= $refmatrix->[$i]->[$j-1]) {
12             $refmatrix->[$i]->[$j] = $refmatrix->[$i-1]->[$j];
13          }
14          else {
15             $refmatrix->[$i]->[$j] = $refmatrix->[$i]->[$j-1];
16          }
17       }
18    }
19    return $refmatrix;
20 }

Aus den Werten in Abbildung 5 kann ein Backtracking-Algorithmus [6] schnell die längste gemeinsame Teilsequenz der Zeichenfolge bestimmten:

  • Wähle den größten Eintrag, der entweder im Feld links oberhalb, links oder oberhalb des aktuellen Feldes steht.
  • Wenn es mehrere Eintrage mit gleichem größtem Wert gibt, bevorzuge den Weg links oberhalb.
  • Die LCS ergibt sich auf der Wanderung, wenn es mehrere Einträge mit dem gleichen Maximalwert gibt.

Abbildung 6 zeigt den Pfad einer solchen Wanderung, Listing 2 eine Umsetzung des zugehörigen Algorithmus in Perl. Damit sich das Skript korrekt beendet, muss die Zeichenkette, wie in der Abbildung zu sehen, am Anfang ein Füllzeichen mit Nullwert enthalten.

Abbildung 5: Statt die Differenzen der Zeichenwerte einzutragen, ist es effizienter, gleich im ersten Durchlauf die Länge der Teilsequenzen zu schreiben.

Abbildung 6: Ein Backtracking vom höchsten Wert in der Tabelle ist der schnellste Weg, die längste gemeinsame Teilsequenz zu bestimmen.

Listing 2: Backtracking

01 # run backtracking on lcs-matrix
02 sub backtracking_lcs {
03    my $refmatrix=shift;
04    my $ref_xlst=shift;
05    my $ref_ylst=shift;
06    my @lcs;
07    my $x=scalar @$ref_xlst -1;
08    my $y=scalar @$ref_ylst -1;
09    while ($y>0 && $x>0) {
10       my $actual_value=$refmatrix->[$x]->[$y];
11       my $actual_x=$x;
12       if (
13          ($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x-1]->[$y]) &&
14          ($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x]->[$y-1])
15       ) { # go left upper
16          $x--; $y--;
17       } elsif ($refmatrix->[$x-1]->[$y] >= $refmatrix->[$x]->[$y-1]) { # go left
18          $x--;
19       } else { # go upper
20          $y--;
21       }
22       # check if value is changed, then push to @lcs
23       if ($actual_value > $refmatrix->[$x]->[$y]) {
24          push @lcs, $actual_x;
25       }
26    }
27    @lcs=reverse @lcs; # reverse because backtracking
28    return @lcs;
29 }
30 
31 # print out lcs matrix
32 sub print_lcs {
33    my $ref_matrix=shift;
34    my $ref_xlst=shift;
35    my $ref_ylst=shift;
36    print "LCS: '";
37    foreach my $i (@{ backtracking_lcs($ref_matrix, $ref_xlst, $ref_ylst) }) {
38       print $ref_xlst->[$i];
39    }
40    print "'n";
41 }

Listing 3: Diff-Algorithmus

01 # run backtracking on lcs-matrix
02 sub backtracking_lcs {
03    my $refmatrix=shift;
04    my $ref_xlst=shift;
05    my $ref_ylst=shift;
06    my @lcs;
07    my $x=scalar @$ref_xlst -1;
08    my $y=scalar @$ref_ylst -1;
09    while ($y>0 && $x>0) {
10       my $actual_value=$refmatrix->[$x]->[$y];
11       my $actual_x=$x;
12       my $actual_y=$y;
13       my $actual_direction;
14       if (
15          ($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x-1]->[$y]) &&
16          ($refmatrix->[$x-1]->[$y-1] >= $refmatrix->[$x]->[$y-1])
17       ) { # go left upper
18          $x--; $y--;
19          $actual_direction="ul";
20 
21       } elsif ($refmatrix->[$x-1]->[$y] >= $refmatrix->[$x]->[$y-1]) { # go left
22          $x--;
23          $actual_direction="l";
24       } else { # go upper
25          $y--;
26          $actual_direction="u";
27       }
28       # check if value is changed, then push to @lcs
29       if ($actual_value > $refmatrix->[$x]->[$y]) {
30          # push @lcs, $actual_x;
31          push @lcs, "(".$ref_xlst->[$actual_x].")";
32       } else {
33          if ($actual_direction eq "u") {
34             push @lcs, "+(".$ref_ylst->[$actual_y].")";
35          } elsif ($actual_direction eq "l") {
36             push @lcs, "-(".$ref_xlst->[$actual_x].")";
37          } else {
38             push @lcs, "+(".$ref_ylst->[$actual_y].")";
39             push @lcs, "-(".$ref_xlst->[$actual_x].")";
40          }
41       }
42    }
43    while ($y > 0) { # get last stuff of ylst
44       push @lcs, "+(".$ref_ylst->[$y].")";
45       $y--;
46    }
47    while ($x > 0) { # get last stuff of xlst
48       push @lcs, "-(".$ref_xlst->[$x].")";
49       $x--;
50    }
51    @lcs=reverse @lcs; # reverse because backtracking
52    return @lcs;
53 }
54 
55 # print out lcs matrix
56 sub print_diff {
57    my $ref_matrix=shift;
58    my $ref_xlst=shift;
59    my $ref_ylst=shift;
60    print "DIFF: '";
61    foreach my $i (@{ backtracking_lcs($ref_matrix, $ref_xlst, $ref_ylst) }) {
62       print $i;
63    }
64    print "'n";
65 }

Obwohl die dynamische Programmierung bereits mehrfache Berechnungen einspart, mussten die Entwickler des Unix-Programms Diff (später Diffutils, [1]) noch tiefer in die Trickkiste greifen: Das Diff-Tool war vor allem für den Einsatz bei der Quelltext-Verwaltung geplant. Um bereits bei der Speicherausstattung der 80er Jahre mit den hier üblichen Dateigrößen zurechtzukommen, vergleicht Diff nicht Buchstabe für Buchstabe, sondern nur Zeile für Zeile. Dazu berechnet das Programm zunächst für jede Zeile einen Hashwert und erst im nächsten Schritt die Unterschiede in der Abfolge dieser Hashes. Nur bei abweichenden Hashwerten muss das Programm die Zeilen noch Buchstabe für Buchstabe vergleichen. Dass reduziert den Speicherbedarf erheblich.

Durch die Verwendung der im Kasten „Teile und herrsche“ beschriebenen Methode und unter Zuhilfenahme von Heuristiken entwickelte Eugene Myers 1986 einen schnellen Algorithmus, der die Grundlage für die bekannten Diffutils bildete [7]. Auch grafische Alternativen zum Kommandozeilenprogramm Diff wie Meld [8] oder die KDE-Anwendung Kompare [9] beruhen noch immer auf dem beschriebenen Verfahren. Kompare nutzt für die ausgefeilte grafische Darstellung in Hintergrund sogar das altbekannte Diff-Tool.

Teile und herrsche

Divide and Conquer ist wie das dynamische Programmieren eine Standardmethode. Es zerlegt Probleme rekursiv so lange in kleinere Teilprobleme, bis diese mit den zur Verfügung stehenden Rechenressourcen lösbar werden. Ein typisches Beispiel für die Teile-und-Herrsche-Methode ist der Sortieralgorithmus Mergesort. Er zerlegt eine Zeichenfolge rekursiv bis zum einzelnen Zeichen. Anschließend setzt der Algorithmus die Teile wieder zusammen und sortiert diese jeweils beim Zusammensetzen.

Aus »n=1,8,3,2« entstehen »n1=1,8« und »n2=3,2«. »n1« liegt bereits sortiert vor. »n2« zerlegt Mergesort in »n21=3« und »n22=2« weiter. Das erneute Zusammensetzen nach dem Reisverschlussverfahren aus »n1=1,8« und »n2=2,3« ergibt schließlich die sortierte Folge »n=1,2,3,8«.

Diesen Artikel als PDF kaufen

Express-Kauf als PDF

Umfang: 3,5 Heftseiten

Preis € 0,99
(inkl. 19% MwSt.)

Linux-Magazin kaufen

Einzelne Ausgabe
 
Abonnements
 
TABLET & SMARTPHONE APPS
Bald erhältlich
Get it on Google Play

Deutschland

Ähnliche Artikel

comments powered by Disqus

Ausgabe 07/2017

Digitale Ausgabe: Preis € 6,40
(inkl. 19% MwSt.)

Artikelserien und interessante Workshops aus dem Magazin können Sie hier als Bundle erwerben.