Levenshtein Distance
Die Levenshtein-Distanz ist die minimale Anzahl an Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, die nötig sind, um zwei Zeichenketten identisch zu machen.
Zweck
Misst den Editierunterschied zwischen Zeichenketten; wird für Fuzzy-Matching und Rechtschreibkorrektur verwendet.
Mechanismus
Dynamische Programmierung: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+Kosten), wobei die Kosten 0 sind, wenn die Zeichen übereinstimmen, sonst 1. Zeit und Raum sind O(m×n); der Raum lässt sich auf O(min(m,n)) optimieren.
Anwendungsfälle
- Rechtschreibprüfung und -korrektur
- DNA-Sequenzalignment
- Fuzzy-Suche und Deduplizierung
- Natürliche Sprachverarbeitung
Beispiele
- Eingabe
kitten → sittingOutput3Substitute k→s, e→i, and insert g
Häufige Fehler
- Full O(mn) computation is too slow for long strings
- Use a BK-tree or early termination by threshold
Verwandte Begriffe
Hamming Distance
Die Hamming-Distanz ist die Anzahl der Positionen, an denen sich entsprechende Zeichen zweier gleich langer Zeichenketten unterscheiden; sie gilt nur für Vergleiche gleicher Länge. GLOSSAR
Jaro-Winkler Distance
Die Jaro-Winkler-Distanz verfeinert die Jaro-Distanz, indem gemeinsame Präfixe gewichtet werden — besser geeignet für kurze Strings wie Personennamen, bei denen Präfixe zählen. GLOSSAR
Edit Distance
Die Editierdistanz ist die minimale Anzahl einzeichenlicher Editieroperationen (Einfügen, Löschen, Ersetzen), um eine Zeichenkette in eine andere umzuwandeln; die Levenshtein-Distanz ist ihre häufigste Form. GLOSSAR
Fuzzy Search
Unscharfe Suche (Fuzzy Search) ist eine Suchtechnik, die Schreibvarianten toleriert und über Editierdistanz, N-Gramme oder phonetische Algorithmen ungefähre Treffer zuordnet. GLOSSAR