Editierdistanz (Levenshtein-Distanz)

Tippen Sie recieve, und Ihr Handy schlägt receive vor. Es weiß, dass Sie nah dran waren, weil die beiden Wörter nur wenige Änderungen auseinanderliegen. Diese Nähe zu messen, also die Editierdistanz, ist eine klassische Aufgabe für die dynamische Programmierung.

Eine Tabelle mit einem Wort an der Seite und einem anderen oben, Zahlen in den Zellen und einem orangefarbenen Pfad von Änderungen von der oberen linken bis zur unteren rechten Ecke
Eine Tabelle mit einem Wort an der Seite und einem anderen oben, Zahlen in den Zellen und einem orangefarbenen Pfad von Änderungen von der oberen linken bis zur unteren rechten Ecke

Das Problem

Eine Änderung verändert ein Wort um einen Buchstaben: einen Buchstaben einfügen, einen Buchstaben löschen oder einen Buchstaben durch einen anderen ersetzen. Die Editierdistanz zweier Wörter ist die kleinste Zahl von Änderungen, die das eine in das andere verwandeln. Zwischen cat und cut liegt 1 Änderung, zwischen cat und cast ebenfalls 1 und zwischen cat und act 2. Sie heißt auch Levenshtein-Distanz, nach dem sowjetischen Mathematiker Vladimir Levenshtein, der sie 1965 untersuchte.

Die Tabelle

Sei d[i][j] die Editierdistanz zwischen den ersten i Buchstaben des einen Wortes und den ersten j Buchstaben des anderen. Ein Wort in nichts zu verwandeln kostet eine Löschung pro Buchstabe, also d[i][0] = i, und ein Wort aus dem Nichts aufzubauen kostet eine Einfügung pro Buchstabe, also d[0][j] = j. Ist Buchstabe i gleich Buchstabe j, gilt d[i][j] = d[i − 1][j − 1]. Andernfalls ist d[i][j] = 1 + das Kleinste von d[i − 1][j − 1] (Ersetzen), d[i − 1][j] (Löschen) und d[i][j − 1] (Einfügen).

Ein Beispiel

Für kitten und sitting hat die Tabelle 7 Zeilen und 8 Spalten. Die Zelle unten rechts ist 3, und das Zurücklesen von dort ergibt: k durch s ersetzen, i, t und t behalten, e durch i ersetzen, n behalten und g einfügen. Aus kitten wird sitten, dann sittin, dann sitting: drei Änderungen, und die Tabelle beweist, dass es keine kürzere Liste gibt.

Die Änderungen zurücklesen

Beginnen Sie bei der Zelle unten rechts und fragen Sie, von welchem Nachbarn ihr Wert stammt. Stimmen die Buchstaben überein und ist die Zelle gleich ihrem Nachbarn links oben, wurde der Buchstabe behalten: Gehen Sie diagonal. Ist sie um eins größer als der Nachbar links oben, war es ein Ersetzen; um eins größer als die Zelle darüber, ein Löschen; um eins größer als die Zelle links, ein Einfügen. Mehrere Wege können gleichauf liegen, und jeder ergibt eine kürzeste Liste von Änderungen.

Geschichte und Anwendungen

Levenshtein führte die Distanz 1965 ein, als er an fehlerkorrigierenden Codes arbeitete. Das Tabellenverfahren wurde von mehreren Forschern veröffentlicht, am bekanntesten 1974 von Robert Wagner und Michael Fischer, daher heißt es oft Wagner–Fischer-Algorithmus. Heute ordnen Editierdistanzen Rechtschreibvorschläge, finden Namen mit Tippfehlern in Datenbanken, vergleichen DNA- und Proteinsequenzen und bewerten Spracherkennung.

Selbst ausprobieren

Öffnen Sie die App und drücken Sie Schritt. Die beiden verglichenen Buchstaben leuchten in den Überschriften auf; bei gleichen Buchstaben wird die blaue Zelle links oben übernommen, bei verschiedenen werden alle drei blauen Nachbarn gelesen, und zum kleinsten wird eins addiert. Am Ende läuft der orangefarbene Pfad von der Ecke zurück, und die Änderungen erscheinen unter der Tabelle.

Häufig gestellte Fragen

Ist die Editierdistanz eine Metrik?

Ja. Sie ist nie negativ, sie ist nur für gleiche Wörter 0, sie ist in beide Richtungen gleich, und der Umweg über ein drittes Wort kann sie nie verkürzen: d(a, c) ≤ d(a, b) + d(b, c). Deshalb eignet sie sich gut für die Suche nach ähnlichen Treffern.

Was ist die Damerau–Levenshtein-Distanz?

Die Editierdistanz mit einer zusätzlichen Änderung: dem Vertauschen zweier benachbarter Buchstaben. Frederick Damerau stellte 1964 fest, dass Einfügen, Löschen, Ersetzen und Vertauschen zusammen mehr als 80 Prozent der Rechtschreibfehler abdecken. Mit Vertauschungen liegen recieve und receive 1 statt 2 auseinander.

Lässt sich die Editierdistanz schneller als in O(m·n) berechnen?

Nicht wesentlich. 2015 zeigten Arturs Backurs und Piotr Indyk, dass ein Verfahren mit O(n^(2 − ε)) Zeit für irgendein ε > 0 die starke Exponentialzeithypothese widerlegen würde, die die meisten Forschenden für wahr halten. Für Wörter, die sich ähnlich sind, genügt allerdings ein schmales Band um die Diagonale der Tabelle.

Wie wird die Editierdistanz beim DNA-Vergleich verwendet?

Biologen verwenden dieselbe Tabelle mit Punktwerten statt Zählungen: Übereinstimmungen bringen Punkte, und Ersetzungen und Lücken kosten Punkte, die von den Buchstaben abhängen. Das ist der Needleman–Wunsch-Algorithmus von 1970 für ganze Sequenzen und der Smith–Waterman-Algorithmus von 1981 für die am besten übereinstimmenden Abschnitte.

Bereit, es auszuprobieren?

Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.

Editierdistanz ausprobieren