Wie ein Diff funktioniert: die Technik hinter dem Textvergleich

Wenn ein Textvergleich Ihnen in Sekunden zeigt, was sich geändert hat, steckt dahinter ein erstaunlich elegantes Stück Informatik. In diesem Artikel schauen wir gemeinsam unter die Oberfläche: Wie findet ein Diff heraus, welche Teile gleich geblieben sind, und warum markiert er manchmal mehr, als Sie erwarten würden. Sie brauchen dafür kein Mathematikstudium, nur etwas Neugier.

Die Grundidee: Gemeinsames behalten, Rest markieren

Ein Diff dreht das Problem um. Statt mühsam zu suchen, was sich geändert hat, sucht er zuerst, was gleich geblieben ist. Er findet also die größtmögliche Menge an Textbausteinen, die in beiden Fassungen in derselben Reihenfolge vorkommen. Alles, was zu diesem gemeinsamen Gerüst nicht passt, muss zwangsläufig entweder neu hinzugekommen oder verschwunden sein.

Stellen Sie sich zwei Sätze vor. Im linken steht eine Reihe von Wörtern, im rechten eine leicht veränderte Reihe. Der Diff legt beide übereinander und sucht den längsten roten Faden, der sich durch beide zieht, ohne die Reihenfolge zu brechen. Diesen Faden lässt er unangetastet. Wörter, die nur links liegen, bekommen die Markierung gelöscht, Wörter, die nur rechts liegen, die Markierung hinzugefügt.

Die längste gemeinsame Teilsequenz

Dieses gemeinsame Gerüst hat einen Namen: die längste gemeinsame Teilsequenz, abgekürzt LCS für den englischen Begriff longest common subsequence. Eine Teilsequenz besteht aus Elementen, die in beiden Texten in gleicher Reihenfolge auftauchen, aber nicht unbedingt direkt nebeneinander stehen müssen.

Ein einfaches Beispiel mit Buchstaben macht es klar. Nehmen Sie die Folgen A B C D F und A C D E F. Die längste gemeinsame Teilsequenz ist A C D F, denn diese vier Buchstaben kommen in beiden Folgen in dieser Reihenfolge vor. Das B existiert nur links, also gelöscht, das E nur rechts, also hinzugefügt. Genau so denkt ein Diff, nur dass die Elemente bei echten Texten Zeilen oder Wörter statt einzelner Buchstaben sind.

Wie ein Computer einzelne Zeichen überhaupt als gleich oder verschieden einstuft, regelt die Zeichenkodierung Unicode. Und die Vergleichsregeln für Zeichenketten in der Browser-Sprache JavaScript beschreibt die MDN-Dokumentation zu String. Auf dieser Grundlage entscheidet der Diff, was zur gemeinsamen Sequenz gehört.

Drei Ebenen: Zeile, Wort, Zeichen

Die Elemente, aus denen der Diff seine gemeinsame Sequenz baut, können unterschiedlich groß sein. Diese Wahl der Granularität entscheidet darüber, wie fein das Ergebnis ausfällt.

Beim Zeilen-Diff ist jede Zeile ein Element. Das ist schnell und übersichtlich, eignet sich aber nur dort, wo Zeilen sinnvolle Einheiten sind, etwa bei Listen oder Programmcode. Beim Wort-Diff wird jeder Text in Wörter zerlegt, was bei Fließtext deutlich präziser wirkt. Beim Zeichen-Diff ist sogar jeder einzelne Buchstabe ein Element, was selbst kleinste Tippfehler sichtbar macht, bei längeren Texten aber schnell unübersichtlich wird.

Die folgende Übersicht fasst zusammen, welche Ebene welchen Vorteil bietet und wo sie typischerweise eingesetzt wird.

Diff-Ebene	Vorteil	Typischer Einsatz
Zeile	schnell, sehr übersichtlich	Listen, Code, Tabellenzeilen
Wort	präzise im Fließtext, ruhige Darstellung	Verträge, Artikel, E-Mails
Zeichen	findet kleinste Abweichungen	einzelne Tippfehler, kurze Codes

Welche Ebene für Ihren konkreten Fall passt, habe ich aus praktischer Sicht im Artikel Textvergleich Grundlagen beschrieben. Dort finden Sie auch eine Entscheidungstabelle für den Alltag.

In der Praxis kombinieren gute Werkzeuge die Ebenen sogar. Ein verbreitetes Muster ist der zweistufige Vergleich: Zuerst läuft ein Zeilen-Diff, um schnell die betroffenen Abschnitte zu finden. Innerhalb der als geändert erkannten Zeilen läuft anschließend ein Wort-Diff, der genau zeigt, welche Begriffe ausgetauscht wurden. So bleibt die Darstellung übersichtlich, ohne an Genauigkeit zu verlieren. Sie sehen auf einen Blick, wo etwas passiert ist, und im Detail, was passiert ist. Beim Vergleich zweier Listen wählen Sie dagegen bewusst nur die Zeilenebene, wie es die Anleitung zwei Texte für den Einstieg zeigt.

Warum eine ganze Zeile als geändert gilt

Eine häufige Frage lautet: Warum leuchtet eine komplette Zeile rot, obwohl sich nur ein einziges Wort geändert hat? Die Antwort liegt in der Granularität. Beim Zeilen-Diff ist die Zeile die kleinste Einheit, die der Algorithmus kennt. Er vergleicht nicht den Inhalt innerhalb einer Zeile, sondern fragt nur: Ist diese Zeile als Ganzes identisch oder nicht?

Sobald sich ein einziges Zeichen ändert, lautet die Antwort nein. Damit gehört die alte Zeile nicht mehr zur gemeinsamen Sequenz und wird gelöscht, während die neue Zeile als hinzugefügt erscheint. Aus Sicht des Algorithmus ist das eine Löschung plus eine Einfügung, was zusammen wie eine geänderte Zeile aussieht.

Die Grenzen eines Diffs

So nützlich ein Diff ist, er hat klare Grenzen, die man kennen sollte, um seine Ergebnisse richtig zu deuten. Die wichtigste betrifft die Reihenfolge.

Ein klassischer Diff achtet streng auf die Reihenfolge der Elemente. Verschieben Sie einen Absatz an eine andere Stelle, erkennt der Algorithmus das nicht als Verschiebung. Stattdessen meldet er den Absatz an der alten Stelle als gelöscht und an der neuen Stelle als eingefügt. Inhaltlich ist das korrekt, aber es sieht nach mehr Änderung aus, als tatsächlich stattgefunden hat.

Ähnliches gilt für Umsortierungen. Wenn Sie eine Liste alphabetisch neu ordnen, kann ein Diff sehr viele Markierungen erzeugen, obwohl kein einziger Eintrag inhaltlich verändert wurde. Hier hilft es, die Liste vor dem Vergleich auf beiden Seiten gleich zu sortieren, damit nur echte inhaltliche Unterschiede übrig bleiben.

Ein Diff sagt Ihnen zuverlässig, was anders ist, aber nicht immer, warum es anders ist. Den Kontext liefern Sie.

Eine weitere Feinheit: Das Ergebnis ist nicht immer eindeutig. Oft gibt es mehrere gleich lange gemeinsame Teilsequenzen, sodass derselbe Vergleich auf verschiedene, aber gleichwertige Weisen markiert werden kann. Das ist kein Fehler, sondern eine Eigenschaft des Problems. Beide Darstellungen sind korrekt, sie teilen die Änderungen nur unterschiedlich auf Einfügen und Löschen auf.

Wie der Algorithmus rechnet, ohne Mathematik

Sie müssen die Formeln nicht kennen, um zu verstehen, wie ein Diff systematisch vorgeht. Stellen Sie sich ein Gitter vor, bei dem der linke Text die Zeilen und der rechte Text die Spalten bildet. Jede Position im Gitter beantwortet eine kleine Teilfrage: Wie lang ist die gemeinsame Sequenz bis genau hierher? Der Algorithmus füllt dieses Gitter Feld für Feld, baut also die Lösung aus vielen winzigen Teillösungen zusammen.

Treffen an einer Position das gleiche Element aufeinander, wächst die gemeinsame Sequenz um eins. Stimmen sie nicht überein, übernimmt das Feld den besseren der beiden Nachbarwerte. Am Ende liest der Algorithmus rückwärts durch das Gitter und rekonstruiert daraus, welche Elemente zur gemeinsamen Sequenz gehören und welche nicht. Dieses schrittweise Vorgehen heißt dynamische Programmierung und sorgt dafür, dass das Ergebnis garantiert die längste mögliche Übereinstimmung ist.

Genau dieses Zusammenspiel erklärt auch, warum ein Wechsel der Vergleichsebene das Ergebnis so stark verändert. Auf Zeilenebene hat das Gitter wenige, große Felder, auf Zeichenebene sehr viele, kleine. Mehr Felder bedeuten ein feineres, aber auch unruhigeres Ergebnis. Die praktische Konsequenz daraus habe ich in den Grundlagen zum Textvergleich zusammengefasst.

Vom Verstehen zur Anwendung

Hinter jedem farbigen Textvergleich steht dieselbe klare Idee: das größte gemeinsame Gerüst finden und den Rest als Einfügung oder Löschung kennzeichnen. Ob auf Zeilen-, Wort- oder Zeichenebene gearbeitet wird, bestimmt, wie fein das Ergebnis ausfällt, und die Grenzen bei Verschiebungen und Umsortierungen erklären, warum ein Diff manchmal mehr markiert, als Sie intuitiv erwarten. Mit diesem Wissen lesen Sie jedes Vergleichsergebnis sicherer. Probieren Sie es direkt mit dem Textvergleich-Tool aus, und wenn Sie zwei Listen abgleichen wollen, hilft Ihnen die Anleitung zwei Listen sowie die Anleitung Zeilen vergleichen weiter.