Edit-Distanz · dynamische Programmierung

Eine minimale Editfolge finden und ihre Präfixtabelle Zelle für Zelle nachvollziehen.

About this tool

Einen Text in einen anderen überführen

Quelle und Ziel mit jeweils 0…20 wohlgeformten Unicode-Codepunkten eingeben. Leere Texte sind gültig. Berechnen zeigt die vollständige Tabelle, die minimale Distanz und eine optimale Editfolge. Schritt beginnt bei Bedarf eine neue Tabelle und deckt genau eine Zelle in Zeilenreihenfolge auf. Die letzte Zelle schließt das Ergebnis sofort ab. Ergebnis leeren behält die Eingaben; eine Text- oder Beispieländerung entfernt das alte Ergebnis.

So entsteht die Tabelle

Zeile i steht für die ersten i Codepunkte der Quelle, Spalte j für die ersten j Codepunkte des Ziels. Die Kopfzellen zeigen die Präfixlänge und anschließend den letzten Codepunkt dieses Präfixes. ∅ steht für das leere Präfix. D[0,j] = j Einfügungen und D[i,0] = i Löschungen. Eine innere Zelle wählt das Minimum aus dem diagonalen Wert plus 0 bei Übereinstimmung oder 1 beim Ersetzen, dem oberen Wert plus 1 fürs Löschen und dem linken Wert plus 1 fürs Einfügen.

Zur aktuellen Zelle erscheinen die Kandidaten und der gewählte Vorgänger. Bei Gleichstand gilt die Reihenfolge diagonal, Löschen, Einfügen. Der am Ende markierte Pfad verbindet (0,0) mit der rechten unteren Zelle. Er liefert eine deterministische optimale Folge; andere optimale Folgen können existieren. Das Vertauschen benachbarter Zeichen ist keine eigene Operation: ab → ba hat hier Distanz 2.

Die Editfolge lesen

Jede aufgeführte Änderung kostet 1. Übereinstimmungen kosten 0 und stehen unter Vollständige Ausrichtung. Positionen zählen ab 0 im Text unmittelbar vor der Operation, gemessen in Codepunkten. Text danach zeigt den gesamten aktuellen Text, nicht nur das geänderte Zeichen. Für kitten → sitting ist die minimale Distanz 3: k an Position 0 durch s ersetzen ergibt sitten, e an Position 4 durch i ersetzen ergibt sittin, anschließend g an Position 6 einfügen ergibt sitting.

Ausrichtungslücken heißen ausdrücklich Lücke. Ein tatsächlicher Bindestrich bleibt ein Zeichen, gekennzeichnet mit U+002D, und dient nie als Lückensymbol. Die Änderungsnummern zählen tatsächliche Edits; die Schrittnummern der vollständigen Ausrichtung zählen auch Übereinstimmungen.

Unicode und unveränderte Texte

Die Berechnung verwendet Codepunkte, keine UTF-16-Codeeinheiten oder sichtbaren Graphemcluster. 😀 → leer hat Distanz 1, während 👩‍💻 drei Codepunkte enthält. Zusammengesetztes é und e mit nachfolgendem U+0301 bleiben verschiedene Eingaben. Es gibt weder Normalisierung noch Abschneiden von Leerraum, Umwandlung der Großschreibung oder stille Kürzung. Ungepaarte UTF-16-Surrogate werden abgelehnt.

Jedes Zeichen außerhalb der ASCII-Buchstaben und -Ziffern erhält in Matrix oder Ausrichtung eine U+…-Kennzeichnung. □ vertritt Leerraum oder unsichtbare Zeichen; der Code benennt das genaue Zeichen. Ein gepunkteter Kreis trägt ein kombinierendes Zeichen und gehört nicht zum Quelltext. Zwischenstände behalten ihren tatsächlichen Leerraum; die Codehinweise verwenden Positionen ab 0. Die isolierte Textrichtung verhindert, dass Zeichen mit Rechts-nach-links-Richtung oder Richtungssteuerzeichen umliegende Beschriftungen umordnen.

Quellen