Levenshtein-Distanz

Kurz: Die Levenshtein-Distanz zählt die minimale Zahl an Einfügungen, Löschungen und Ersetzungen einzelner Zeichen, um ein Wort in ein anderes zu verwandeln.

Genauer: „kitten” → „sitting” hat die Distanz 3 (k→s, e→i, g anhängen). Sie ist die Grundlage für Rechtschreibkorrektur, „Meintest du …?” und unscharfe Suche.

Im Detail

• Verfahren: Dynamische Programmierung mit einer Tabelle d[i][j] für die Distanz der ersten i Zeichen von A und der ersten j Zeichen von B.
• Rekurrenz: d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + (a[i]≠b[j])).
• Aufwand: O(m·n) Zeit, mit Rollen von nur zwei Zeilen O(min(m, n)) Speicher.
• Varianten: Damerau-Levenshtein zählt auch das Vertauschen benachbarter Zeichen. Die Hamming-Distanz gilt nur für gleich lange Wörter.
• Praxis: Für große Wörterbücher nutzt man Indexe wie BK-Bäume oder n-Gramme, statt jedes Wort einzeln zu vergleichen.

Siehe auch: Textsuche-Algorithmen