Levenshtein Distanz

Die Levenshtein-Distanz ist ein Maß für den Unterschied zwischen zwei Zeichenketten (Strings). Sie gibt an, wie viele einzelne Bearbeitungsschritte (Operationen) notwendig sind, um eine Zeichenkette in eine andere zu überführen. Dabei sind die folgenden Operationen erlaubt:

1. Einfügen eines Zeichens

2. Löschen eines Zeichens

3. Ersetzen eines Zeichens durch ein anderes

Beispiel:

Die Levenshtein-Distanz zwischen den Wörtern "Haus" und "Maus" ist 1, weil nur ein Buchstabe (H → M) geändert werden muss.

Anwendung:

Die Levenshtein-Distanz wird in vielen Bereichen verwendet, z. B.:

• Rechtschreibprüfung (Vorschlag ähnlicher Wörter)

• DNA-Sequenzvergleiche

• Plagiaterkennung

• Fuzzy-Suche in Datenbanken oder Suchmaschinen

Formel (rekursiv, vereinfacht):

Für zwei Strings a und b, mit Längen i und j:

lev(a, b) = min(
  lev(a-1, b) + 1,        // löschen
  lev(a, b-1) + 1,        // einfügen
  lev(a-1, b-1) + cost    // ersetzen (cost = 0, wenn Zeichen gleich; sonst 1)
)

Es gibt auch effizientere dynamische Programmieralgorithmen, um diese Distanz zu berechnen.