Die Levenshtein-Distanz, auch Edit Distance genannt, misst den Unterschied zwischen zwei Strings anhand der minimal notwendigen Bearbeitungsoperationen.
Erlaubt sind normalerweise:
- Insert
- Delete
- Replace
Jede Operation kostet standardmäßig 1.
Beispiel:
cat → cut
Nur ein Zeichen muss ersetzt werden:
Distance = 1
Klassisches Beispiel
kitten → sitting
Eine optimale Folge ist:
kitten → sitten
sitten → sittin
sittin → sitting
Damit beträgt die Distanz 3.
Dynamic Programming
Wir definieren:
dp[i][j]
als minimale Anzahl von Operationen, um die ersten i Zeichen des ersten Strings in die ersten j Zeichen des zweiten Strings umzuwandeln.
Die Basisfälle lauten:
dp[0][j] = j
dp[i][0] = i
Sind die aktuellen Zeichen gleich:
dp[i][j] = dp[i - 1][j - 1]
Ansonsten:
dp[i][j] = 1 + min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
)
Die drei Werte repräsentieren Delete, Insert und Replace.
TypeScript-Implementierung
function levenshteinDistance(a: string, b: string): number {
const dp = Array.from(
{ length: a.length + 1 },
() => new Array(b.length + 1).fill(0)
);
for (let i = 0; i <= a.length; i++) {
dp[i][0] = i;
}
for (let j = 0; j <= b.length; j++) {
dp[0][j] = j;
}
for (let i = 1; i <= a.length; i++) {
for (let j = 1; j <= b.length; j++) {
if (a[i - 1] === b[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j],
dp[i][j - 1],
dp[i - 1][j - 1]
);
}
}
}
return dp[a.length][b.length];
}
Komplexität
Für Stringlängen n und m:
Time Complexity: O(n × m)
Space Complexity: O(n × m)
Der Speicher kann auf O(min(n, m)) reduziert werden, wenn nur die aktuelle und vorherige Zeile gespeichert werden.
Spell Checking
Ein Benutzer schreibt beispielsweise:
programing
Die Distanz zu programming beträgt nur 1. Damit kann das Wort als guter Korrekturvorschlag verwendet werden.
Fuzzy Search
Bei:
Alexander
Alexnder
scheitert Exact Matching, obwohl die Strings offensichtlich sehr ähnlich sind.
Edit Distance kann diese Ähnlichkeit quantifizieren.
CRM und Datenbereinigung
Levenshtein kann bei der Erkennung möglicher Duplicate Records helfen.
Beispielsweise:
Arian Soleimanzadeh
Arian Soleimanzade
Eine geringe Distanz ist ein Signal, sollte aber in realen CRM-Systemen mit E-Mail, Telefonnummer oder anderen Identifikatoren kombiniert werden.
Weitere Anwendungen
- Fuzzy Search
- Rechtschreibkorrektur
- OCR
- NLP
- Data Cleaning
- Record Matching
- Bioinformatik
Unterschied zur Hamming-Distanz
Die Hamming-Distanz vergleicht nur korrespondierende Positionen und setzt normalerweise gleiche Längen voraus.
Levenshtein berücksichtigt auch Insert und Delete.
cat → cats
hat deshalb eine Levenshtein-Distanz von 1.
Weighted Edit Distance
Die Operationskosten können angepasst werden:
Insert = 1
Delete = 1
Replace = 2
Dadurch lässt sich der Algorithmus an bestimmte Anwendungen anpassen.
Typische Interviewfrage
Ein klassisches Dynamic-Programming-Problem lautet:
Bestimme die minimale Anzahl von Insert-, Delete- und Replace-Operationen zwischen zwei Strings.
Für:
horse → ros
ist das Ergebnis 3.
Fazit
Die Levenshtein-Distanz berechnet die minimale Anzahl von Insert-, Delete- und Replace-Operationen zwischen zwei Strings.
Die Standardlösung nutzt Dynamic Programming mit:
Time: O(n × m)
Space: O(n × m)
Das Verfahren ist nicht nur für Algorithmusaufgaben wichtig, sondern auch für Fuzzy Search, Rechtschreibprüfung, CRM-Deduplizierung, OCR und NLP.