LevenshteinDistanz

Die LevenshteinDistanz, auch Levenshtein-Distanz genannt, ist ein Maß für die minimale Anzahl von Einzelbearbeitungen, mit denen zwei Zeichenketten in eine gegenseitige Übereinstimmung überführt werden können. Die Bearbeitungen umfassen Einfügen, Löschen und Ersetzen einzelner Zeichen. Die Distanz ist nach dem russischen Wissenschaftler Vladimir Levenshtein benannt, der das Konzept 1965 vorstellte.

Formal lässt sich die Distanz für zwei Zeichenketten s mit Länge m und t mit Länge n über eine DP-Matrix D der Größe (m+1)×(n+1) berechnen. D[0][j] = j, D[i][0] = i. D[i][j] = min(D[i-1][j] + 1, D[i][j-1] + 1, D[i-1][j-1] + cost), wobei cost = 0, falls s[i-1] = t[j-1], ansonsten cost = 1. Der Wert D[m][n] ist die LevenshteinDistanz. Ein gängiges Beispiel ist die Distanz zwischen „kitten“ und „sitting“, die 3 beträgt.

Eigenschaften und Variationen: Die LevenshteinDistanz erfüllt grundlegende Metrik-Eigenschaften (Nicht-Negativität, Identität, Symmetrie, Dreiecksungleichung). Die maximale Distanz zwischen zwei Strings ist len(s) + len(t). Varianten wie die Damerau-Levenshtein-Distanz erlauben zusätzlich Transpositionen adjakter Zeichen. Oftmals werden gewichtete Kosten oder speichereffiziente Implementierungen verwendet.

Anwendungsgebiete umfassen Rechtschreibprüfung, fuzzy Matching, Auto-Korrektur, DNA-Sequenzvergleich und allgemeine Mustererkennung in Textdaten.