Levenshtein-Distanz

Die Levenshtein-Distanz (auch Editierdistanz) zwischen zwei Zeichenketten ist die minimale Anzahl einfügender, löschender und ersetzender Operationen, um die erste Zeichenkette in die zweite umzuwandeln. Benannt ist die Distanz nach dem russischen Wissenschaftler Wladimir Lewenstein (engl. Levenshtein), der sie 1965 einführte. Mathematisch ist die Levenshtein-Distanz eine Metrik auf dem Raum der Symbolsequenzen.

Beispielsweise entspricht die Levenshtein-Distanz zwischen „Bar“ und „Bier“ zwei. Eine mögliche Folge von zwei Operationen ist:

Ein anderes Beispiel ist die Distanz von eins zwischen „uninformiert“ und „uniformiert“

In der Praxis wird die Levenshtein-Distanz zur Bestimmung der Ähnlichkeit von Zeichenketten beispielsweise zur Rechtschreibprüfung oder bei der Duplikaterkennung angewandt.