Damerau–Levenshtein-Distanz

Die Damerau–Levenshtein-Distanz ist eine klassische Edit-Metrik, die zählt, wie viele Einzelzeichen-Operationen eine Zeichenkette in eine andere überführen, wenn Einfügen, Löschen, Ersetzen und die Vertauschung zweier benachbarter Zeichen erlaubt sind. Gerade diese vierte Operation trennt sie von der einfachen Levenshtein-Distanz und macht sie besonders nützlich bei realen Tippfehlern: Menschen vertauschen oft zwei benachbarte Tasten (form versus from, teh versus the), und das soll einen Schritt kosten, nicht zwei Ersetzungen. Diese Fähigkeit implementiert die Optimal-String-Alignment-Form der Distanz mit einer reinen dynamischen Programmierungstabelle, sodass jedes Eingabepaar auf jeder Runtime dieselbe Ganzzahl liefert. Sie senden zwei Texte und optional ein Groß-/Kleinschreibungs-Flag; Sie erhalten die Distanz, beide Längen, eine normalisierte Ähnlichkeit zwischen null und eins sowie das boolesche Feld identical.

Was Damerau–Levenshtein misst und wie es sich von reinem Levenshtein unterscheidet

Edit-Distanz fragt, wie viele Einheitsänderungen nötig sind, um eine Quellzeichenkette als Zielzeichenkette umzuschreiben. Klassisches Levenshtein erlaubt drei Einheitsoperationen: ein Zeichen einfügen, ein Zeichen löschen oder ein Zeichen durch ein anderes ersetzen. Jede kostet eins.

Dameraus Erweiterung fügt eine vierte Operation hinzu: zwei benachbarte Zeichen für einen einzigen Einheitspreis tauschen. Diese Erweiterung entspricht dem tatsächlichen Tippverhalten auf einer Tastatur. Zum Beispiel unterscheiden sich die Ketten ab und ba unter Damerau–Levenshtein um eine benachbarte Transposition und unter reinem Levenshtein um zwei Ersetzungen.

Kitten versus sitting kostet weiterhin drei (wie im Lehrbuchbeispiel zu Levenshtein), weil der günstigste Pfad Ersetzungen und eine Einfügung nutzt, nicht einen einzigen Tausch. Dieser Endpunkt verwendet die Optimal-String-Alignment-Rekurrenz (OSA): eine dynamische Programmiermatrix, in der Zelle (i, j) das Minimum aus Löschen, Einfügen, Ersetzen-oder-Treffer und—wenn die letzten beiden Zeichen jedes Präfixes ein gekreuztes Paar bilden—Transposition aus Zelle (i−2, j−2) ist.

OSA ist die Form, die die meisten Bibliotheken für Tippfehlerkorrektur als Damerau–Levenshtein bezeichnen; sie verbietet zwei überlappende Transpositionen auf derselben Teilkette und hält die Metrik einfach sowie O(n·m) in Zeit und Speicher. Leere Zeichenketten sind gültig: die Distanz von der leeren Kette zu einer beliebigen Kette ist deren Länge, und die Distanz zwischen zwei leeren Ketten ist null. Identische Ketten ergeben stets Distanz null und Ähnlichkeit eins, auch nach optionaler Klein-/Großschreibung-Normalisierung.

Wo diese Distanz ihren Nutzen zeigt

Produktsuche und Bestands-Tools nutzen Edit-Distanz mit Transpositionen, um Fast-Treffer bei SKUs und Markennamen zu ranken, bevor langsamere semantische Modelle greifen. CRM- und Deduplizierungs-Pipelines markieren Kandidatenzeilen, wenn die Distanz höchstens eins oder zwei ist und die Ähnlichkeit über einer festen Schwelle liegt, und fangen so vertauschte Buchstaben ein, die reine Gleichheit oder selbst reines Levenshtein unterschätzen würden. Rechtschreib-Demos und Unterrichtsübungen brauchen ein deterministisches Orakel, das form versus from als Distanz eins wertet und eine transparente Festgebühr statt Token-Kosten berechnet.

Ungültige Eingabe wird nicht berechnet. Kombinieren Sie die ganzzahlige Distanz mit Ihrer eigenen Schwellenpolitik—akzeptieren Sie Distanz null nur für exakte Schlüssel, Distanz eins für aggressive Tippfehlerkorrektur, Ähnlichkeit über 0.8 für weiche Merge-Hinweise—und Sie erhalten einen kleinen, auditierbaren Baustein für Fuzzy-Matching, ohne eine vollständige Suchmaschine oder einen eigenen NLP-Stack aufzubauen.