DE 
English
Українська
Polski📝 Editierdistanz — Levenshtein-DP-Tabelle
Fülle die Levenshtein-Dynamic-Programming-Tabelle Zelle für Zelle, dann verfolge den günstigsten Pfad aus Einfügungen, Löschungen und Ersetzungen zurück, der eine Zeichenkette in eine andere verwandelt.
Über diese Simulation
Die Editierdistanz, 1965 von Vladimir Levenshtein formalisiert, misst die minimale Anzahl einzelner Zeicheneinfügungen, -löschungen und -ersetzungen, die nötig sind, um eine Zeichenkette in eine andere umzuwandeln. Sie wird mit dynamischer Programmierung in O(mn) Zeit und O(mn) Speicher berechnet: eine (m+1)×(n+1)-Tabelle wird gefüllt, wobei jede Zelle d[i][j] die Editierdistanz zwischen den ersten i Zeichen der Quelle und den ersten j Zeichen des Ziels enthält.
🔬 Was gezeigt wird
Die Simulation füllt die DP-Tabelle Zelle für Zelle mit einstellbarer Geschwindigkeit und färbt jede Operation ein. Nach Abschluss markiert das Zurückverfolgen den optimalen Ausrichtungspfad durch die Matrix.
🎮 Bedienung
Bearbeite die Quellzeichenkette A und die Zielzeichenkette B, stelle die Geschwindigkeit ein und nutze die Play-, Step- und Reset-Schaltflächen.
💡 Wusstest du schon?
Die Editierdistanz zwischen „kitten“ und „sitting“ ist 3 — dies ist das klassische Lehrbuchbeispiel, mit dem der Algorithmus veranschaulicht wird.
Häufig gestellte Fragen
Was ist die Editierdistanz?
Die Editierdistanz, oder Levenshtein-Distanz, ist die minimale Anzahl einzelner Zeichenänderungen — Einfügungen, Löschungen oder Ersetzungen —, die nötig sind, um eine Zeichenkette in eine andere umzuwandeln.
Wie funktioniert die Dynamic-Programming-Tabelle?
Ein Raster der Größe (m+1)×(n+1) speichert die Editierdistanz zwischen jedem Präfix der beiden Zeichenketten. Jede Zelle ist das Minimum ihrer linken, oberen und diagonalen Nachbarn plus den Kosten der Bearbeitung.
Warum ist der diagonale Schritt besonders?
Ein diagonaler Schritt richtet ein Zeichen jeder Zeichenkette aus. Stimmen die Zeichen überein, sind die Kosten null (Kopie); unterscheiden sie sich, ist es eine Ersetzung mit Kosten von eins.
Was ist das Zurückverfolgen (Backtracking) in diesem Algorithmus?
Nach dem Füllen der Tabelle beginnst du in der unteren rechten Zelle und gehst zurück zur oberen linken, wobei du bei jedem Schritt den Nachbarn wählst, der den aktuellen Wert erzeugt hat.
Wie hoch ist die Zeitkomplexität?
Das Füllen der Tabelle benötigt O(m*n) Zeit und O(m*n) Speicher, wobei m und n die Zeichenkettenlängen sind. Der Speicher kann auf O(min(m,n)) reduziert werden, wenn nur die Distanz benötigt wird.
Wo wird die Editierdistanz eingesetzt?
Rechtschreibprüfungen, unscharfe Suche, DNA- und Proteinausrichtung, Plagiatserkennung, OCR-Korrektur und Diff-Werkzeuge beruhen alle auf Berechnungen der Editierdistanz.