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.
Zweck
Den Unterschiedsgrad zwischen Zeichenketten quantifizieren, für Fuzzy-Matching und Fehlerkorrektur.
Mechanismus
Allgemeiner Rahmen: die erlaubten Operationen und Kosten definieren, dann per dynamischer Programmierung die minimalen Gesamtkosten suchen. Levenshtein erlaubt Einfügen/Löschen/Ersetzen (je Kosten 1); Damerau-Levenshtein erlaubt zusätzlich die Transposition benachbarter Zeichen; Hamming erlaubt nur Ersetzen.
Anwendungsfälle
- Rechtschreibkorrektur
- DNA-Sequenzalignment
- OCR-Fehlerkorrektur
- Fuzzy-Deduplizierung
Beispiele
- Eingabe
cat → cutOutput1 (substituting a→u)Levenshtein
Häufige Fehler
- Confusing different edit-distance variants
- Make the operation set and costs explicit
Verwandte Begriffe
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. GLOSSAR
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
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