Ein Programm, das zwei Texte vergleicht, liest nicht wie ein Mensch und urteilt nicht darüber, „was sich geändert hat“. Stattdessen sucht es den Weg, eine Liste mit möglichst wenigen Löschungen und Einfügungen in die andere umzuwandeln. Dieser Artikel erklärt, wie diff diese Antwort berechnet und warum das Ergebnis manchmal anders ausfällt, als man erwarten würde.
Die Vergleichseinheit: Zeile, Wort, Zeichen
diff zerlegt den Text zuerst in eine Liste von Token. Das klassische diff und git behandeln jede Zeile als ein Token. Ändert sich innerhalb einer Zeile nur ein einziges Zeichen, erscheint deshalb die ganze Zeile als „1 Zeile gelöscht + 1 Zeile hinzugefügt“.
Der zeilenweise Vergleich ist schnell und passt gut zu Code-Reviews. In Dokumenten, in denen ein langer Absatz in einer einzigen Zeile steht, ist die geänderte Stelle damit aber schwer zu finden. Viele Werkzeuge vergleichen daher in zwei Schritten:
- Zeilenweise vergleichen und die geänderten Zeilen finden.
- Die geänderten Zeilen paarweise zuordnen und ihren Inhalt noch einmal wort- oder zeichenweise vergleichen.
Diese Seite geht genauso vor. Als Einheit für den Vergleich innerhalb der Zeile stehen Wörter, Leerzeichen-Blöcke (durch Leerzeichen getrennte Abschnitte) und Zeichen zur Wahl.
Längste gemeinsame Teilfolge (LCS)
Der mathematische Kern von diff ist die längste gemeinsame Teilfolge (Longest Common Subsequence, LCS). Eine Teilfolge entsteht, wenn man unter Beibehaltung der Reihenfolge einige Elemente auswählt. Die längsten gemeinsamen Teilfolgen von ABCABBA und CBABAC haben zum Beispiel die Länge 4; CABA und BABA sind zwei davon.
Elemente in der LCS sind „unverändert geblieben“, alle übrigen sind „gelöscht“ (nur links vorhanden) oder „hinzugefügt“ (nur rechts vorhanden). Je länger die LCS, desto weniger Löschungen und Einfügungen. Sind N und M die Längen der beiden Listen und L die Länge der LCS, dann gilt für die Summe D der nötigen Löschungen und Einfügungen:
D = (N - L) + (M - L)Im Beispiel ist N=7, M=6, L=4, also D = 3 + 2 = 5. Dieses D heißt Editierdistanz (wenn nur Einfügen und Löschen erlaubt sind), die Liste der Löschungen und Einfügungen heißt Editierskript.
Editiergraph und Myers-Algorithmus
Berechnet man die LCS auf dem Lehrbuchweg (dynamische Programmierung), braucht man eine Tabelle der Größe N×M. Bei zwei Dateien mit je 10.000 Zeilen sind das 100 Millionen Felder — langsam und speicherhungrig. 1986 stellte Eugene W. Myers im Artikel „An O(ND) Difference Algorithm and Its Variations“ ein schnelleres Verfahren vor, das bis heute die Grundlage der Standardalgorithmen von GNU diff und git bildet.
Myers formuliert den Vergleich als Suche nach dem kürzesten Weg in einem Gitter:
- Man geht von oben links (0,0) nach unten rechts (N,M).
- Ein Schritt nach rechts = ein Element des linken Textes löschen, ein Schritt nach unten = ein Element des rechten Textes einfügen. Jeder dieser Schritte kostet 1.
- Wo zwei Elemente gleich sind, darf man kostenlos diagonal gehen. Eine solche zusammenhängende Diagonalstrecke heißt Snake.
Der günstigste Weg entspricht dem kürzesten Editierskript. Der Myers-Algorithmus erweitert schrittweise „den weitesten Punkt, der mit Kosten 0 erreichbar ist“, „den weitesten Punkt mit Kosten 1“ … und stoppt, sobald er den Endpunkt erreicht. Da er in jedem Schritt pro Diagonale nur die am weitesten vorgedrungene Position speichern muss, ist die Laufzeit ungefähr proportional zu (N+M)×D. Sind die Texte fast gleich, ist D klein und der Algorithmus sehr schnell; sind sie völlig verschieden, wird er langsam.
Linearer Speicher und die Middle Snake
Um den Weg zurückverfolgen zu können, muss man bei jedem Schritt Aufzeichnungen behalten, sodass der Speicherbedarf proportional zu D² wachsen kann. Im selben Artikel beschreibt Myers deshalb eine Variante, die gleichzeitig von vorne und von hinten sucht und die Diagonalstrecke findet, auf der sich beide Suchen treffen (Middle Snake). Teilt man das Problem an dieser Stelle rekursiv in zwei kleinere Probleme, braucht man nur Speicher proportional zur Eingabegröße.
Wenn es zu teuer wird: Näherungsheuristik
Haben beide Eingaben Zehntausende Zeilen und unterscheiden sich stark, wird auch D groß, und (N+M)×D kann in die Milliarden gehen. Für diesen Fall hat GNU diff eine Heuristik: Überschreitet die Suche eine bestimmte Schrittzahl, wird das Problem an der bis dahin am weitesten vorgedrungenen Diagonale einfach geteilt. Das Ergebnis ist weiterhin ein korrektes Editierskript, aber nicht garantiert das kürzeste. Die Option --minimal von GNU diff bzw. --minimal von git erzwingt das minimale Ergebnis, auch wenn es länger dauert.
Minimal heißt nicht immer gut lesbar
Es kann mehrere Wege mit derselben Editierdistanz geben. Fügt man zum Beispiel eine Funktion in Code ein, gibt es schließende geschweifte Klammern } und Leerzeilen an vielen Stellen, und der Algorithmus kann die } der neuen Funktion der } einer bestehenden Funktion zuordnen. Das Ergebnis ist minimal, wirkt für Menschen aber seltsam. Deshalb verschiebt git Blockgrenzen standardmäßig anhand der Einrückung und bietet alternative Algorithmen wie patience und histogram an. Einen ausführlichen Vergleich finden Sie unter diff-Algorithmen im Vergleich.
In diesem Werkzeug
Die Vergleichs-Engine dieser Seite implementiert die Variante des Myers-Algorithmus mit linearem Speicher in JavaScript und wechselt bei großen Eingaben wie GNU diff zur näherungsweisen Aufteilung. Die Berechnung läuft in einem Web Worker, sodass die Oberfläche auch bei großen Dateien nicht einfriert. Liegt das zeilenweise Ergebnis vor, werden inhaltlich ähnliche geänderte Zeilen als „geändert“ gepaart und ihr Inhalt noch einmal in der gewählten Einheit (Wörter, Leerzeichen-Blöcke, Zeichen) verglichen und hervorgehoben.
Fügen Sie im Textvergleich selbst zwei Texte ein und sehen Sie, wie sich das Ergebnis mit der Einheit für den Vergleich innerhalb der Zeile ändert. Wie man das Ergebnis im git-Format liest, erklärt Unified Diff lesen.