Einleitung
Beim Vergleich von Texten oder Zeichenketten ist es oft notwendig, die Differenz (Diff) zwischen zwei Strings zu ermitteln. Dies ist vor allem in Bereichen wie Versionskontrolle, Textverarbeitung, biologischer Sequenzanalyse oder Compilerbau relevant. Einer der effizientesten Algorithmen dafür ist Myers’ Algorithmus, der 1986 von Eugene W. Myers vorgestellt wurde. In diesem Artikel erläutern wir den Algorithmus, sein Funktionsprinzip sowie eine exemplarische Implementierung in Java.
Problemstellung: Edit-Distance und Diff
Gegeben sind zwei Zeichenketten A und B. Ziel ist es, die minimalen Änderungen (Einfügen, Löschen, Ersetzen) zu bestimmen, die notwendig sind, um aus A die Zeichenkette B zu erzeugen. Dies ist bekannt als Edit-Distanz oder Levenshtein-Distanz.
Myers‘ Algorithmus geht einen Schritt weiter: Er liefert nicht nur die minimale Anzahl der Änderungen, sondern auch die konkrete Abfolge dieser Änderungen – also den Diff.
Grundprinzip von Myers’ Algorithmus
Myers‘ Algorithmus basiert auf einem cleveren Traversieren eines 2D-Gitters, das alle möglichen Bearbeitungsschritte zwischen zwei Strings abbildet. Ziel ist es, den kürzesten Pfad von der linken oberen Ecke (Start) zur rechten unteren Ecke (Ziel) zu finden.
Definitionen:
A.length = NB.length = M- Ein Pfad durch das Gitter besteht aus folgenden Operationen:
- Delete (nach unten gehen): entfernt ein Zeichen aus
A. - Insert (nach rechts gehen): fügt ein Zeichen zu
Bhinzu. - Diagonal (Match): wenn
A[i] == B[j], bewegen wir uns diagonal nach rechts unten (kein Edit notwendig).
- Delete (nach unten gehen): entfernt ein Zeichen aus
Optimierung:
Myers stellte fest, dass man den kürzesten Pfad mit der geringsten Anzahl an Edits in Zeitkomplexität O(ND) finden kann, wobei D die minimale Anzahl von Änderungen ist. Zusätzlich benötigt sein Algorithmus nur O(D²) Speicher – oder mit Modifikationen sogar O(N + M).
Der Algorithmus Schritt für Schritt
Myers’ Algorithmus verwendet eine Technik, bei der in jeder Iteration alle erreichbaren Positionen im Gitter für eine gegebene Edit-Distanz d überprüft werden.
Idee:
- Für jede Edit-Distanz
dgibt es2d + 1mögliche „Diagonalen“k = -d, -d+2, ..., d-2, d - Für jedes
kwird der weiteste Punkt(x, y)entlang der Diagonale bestimmt, an dem sichAundBweiter „matchen“ lassen (sogenannter „Snake“).
Datenstruktur:
- Eine Map oder ein Array
V, das für jede Diagonalekden größtenx-Wert speichert, den man mitdÄnderungen erreichen kann.
Java-Implementierung
Hier ist eine vereinfachte Java-Implementierung von Myers‘ Algorithmus, die eine Liste von Operationen (Insert, Delete, Match) zurückgibt:
import java.util.*;
public class MyersDiff {
enum Operation {
INSERT, DELETE, MATCH
}
static class Edit {
Operation op;
int indexA;
int indexB;
char ch;
Edit(Operation op, int indexA, int indexB, char ch) {
this.op = op;
this.indexA = indexA;
this.indexB = indexB;
this.ch = ch;
}
public String toString() {
return op + " '" + ch + "' (A@" + indexA + ", B@" + indexB + ")";
}
}
public static List<Edit> diff(String a, String b) {
int n = a.length();
int m = b.length();
int max = n + m;
Map<Integer, Integer> v = new HashMap<>();
Map<String, Integer> path = new HashMap<>();
v.put(1, 0);
for (int d = 0; d <= max; d++) {
for (int k = -d; k <= d; k += 2) {
int x;
if (k == -d || (k != d && v.get(k - 1) < v.get(k + 1))) {
x = v.get(k + 1);
} else {
x = v.get(k - 1) + 1;
}
int y = x - k;
// Snake: durchlaufen solange a[x] == b[y]
while (x < n && y < m && a.charAt(x) == b.charAt(y)) {
x++;
y++;
}
v.put(k, x);
path.put(d + "," + k, x);
if (x >= n && y >= m) {
return backtrack(a, b, path, d);
}
}
}
return Collections.emptyList();
}
private static List<Edit> backtrack(String a, String b, Map<String, Integer> path, int d) {
List<Edit> edits = new ArrayList<>();
int x = a.length();
int y = b.length();
for (int i = d; i > 0; i--) {
int k = x - y;
int prevK = (k == -i || (k != i && get(path, i - 1, k - 1) < get(path, i - 1, k + 1)))
? k + 1 : k - 1;
int prevX = get(path, i - 1, prevK);
int prevY = prevX - prevK;
while (x > prevX && y > prevY) {
x--;
y--;
edits.add(new Edit(Operation.MATCH, x, y, a.charAt(x)));
}
if (x == prevX) {
y--;
edits.add(new Edit(Operation.INSERT, x, y, b.charAt(y)));
} else {
x--;
edits.add(new Edit(Operation.DELETE, x, y, a.charAt(x)));
}
}
Collections.reverse(edits);
return edits;
}
private static int get(Map<String, Integer> map, int d, int k) {
return map.getOrDefault(d + "," + k, 0);
}
public static void main(String[] args) {
String a = "ABCABBA";
String b = "CBABAC";
List<Edit> edits = diff(a, b);
for (Edit e : edits) {
System.out.println(e);
}
}
}
Code-Sprache: JavaScript (javascript)Beispielausgabe:
DELETE 'A' (A@0, B@0)
DELETE 'B' (A@1, B@0)
MATCH 'C' (A@2, B@0)
MATCH 'A' (A@3, B@1)
MATCH 'B' (A@4, B@2)
INSERT 'A' (A@5, B@3)
MATCH 'B' (A@5, B@4)
DELETE 'A' (A@6, B@5)
MATCH 'C' (A@6, B@5)
Code-Sprache: JavaScript (javascript)Vorteile des Algorithmus
- Effizient: Besonders gut für lange Texte mit wenigen Unterschieden.
- Optimal: Liefert den Pfad mit der minimalen Anzahl an Änderungen.
- Speicherschonend: Mit Optimierungen auch speichereffizient.
Einsatzgebiete
- Git / diff-Tools: Myers‘ Algorithmus ist die Grundlage vieler
diff-Implementierungen. - Texterkennung: Z.B. Rechtschreibprüfung, Autovervollständigung.
- Biologische Sequenzanalyse: DNA-Alignment.
- Compiler & Parser: Fehlertolerante Analyse von Quellcode.
Fazit
Myers‘ Algorithmus ist ein leistungsfähiger und eleganter Weg, um die Differenz zweier Zeichenketten zu berechnen. Die Java-Implementierung lässt sich an zahlreiche Anwendungsfälle anpassen und eignet sich hervorragend für den produktiven Einsatz. Wer sich tiefer mit Textvergleichen, Diff-Tools oder Edit-Distanzen beschäftigt, sollte diesen Algorithmus unbedingt kennen und verstehen.