LevenshteinAlgorithmus

LevenshteinAlgorithmus bezeichnet das Verfahren zur Berechnung der Levenshtein-Distanz zwischen zwei Zeichenketten. Die Distanz gibt die minimale Anzahl von Einzelzeichenedits an, die nötig sind, um eine Zeichenkette in die andere zu überführen. Dabei werden drei Grundoperationen berücksichtigt: Einfügungen, Löschungen und Ersetzungen von Zeichen; Transpositionen zählen nicht als eine einzelne Operation.

Der Algorithmus geht auf Vladimir Levenshtein zurück, der ihn 1965 vorstellte. In der Informatik wird er oft als Wagner–Fischer-Algorithmus bezeichnet, weil eine dynamische Programmierung zur Berechnung der Distanz verwendet wird. Die Methode bildet eine Matrix und füllt sie schrittweise aus, sodass das Problem in kleinere Teilprobleme zerlegt wird.

In einer typischen Implementierung vergleicht man zwei Zeichenketten mit Längen m und n. Man erzeugt eine (m+1)×(n+1) Matrix D, wobei D[0][j] = j und D[i][0] = i. Dann gilt für i von 1 bis m und j von 1 bis n: Kosten = (s[i-1] == t[j-1]) ? 0 : 1; D[i][j] = min( D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + Kosten ). Die Distanz ist D[m][n].

Komplexität: Die Berechnung benötigt Zeit O(mn) und typischerweise O(mn) Speicher; mit Optimierungen lässt sich der Speicher auf O(min(m, n)) reduzieren, indem man nur zwei Zeilen oder Spalten hält.

Varianten und Anwendungen: Die Damerau-Levenshtein-Distanz berücksichtigt Transpositionen. Weitere Varianten umfassen gewichtete oder anpassbare Kosten für Operationen. Anwendungen finden sich in Rechtschreibprüfungen, fuzzy Matching, DNA-/Genomvergleichen, OCR-Nachbearbeitung und Duplikats-Erkennung.