Lektion
Die Theorie — Levenshtein-Distanz-Visualisierer
Die Levenshtein-Distanz zwischen zwei Zeichenketten ist die kleinste Zahl von Einzelzeichen-Bearbeitungen, die eine in die andere überführt, wobei eine Bearbeitung ein Einfügen, ein Löschen oder ein Ersetzen ist. Sie ist ein Minimum über alle denkbaren Wege, das zu tun — und genau deshalb ist sie mit bloßem Auge schwer und mit einem Gitter leicht zu bestimmen: Es gibt unvorstellbar viele Bearbeitungsfolgen, und dieses Verfahren findet die kürzeste, ohne eine einzige davon aufzulisten.
Was die einzelnen Symbole bedeuten
m, n- die Längen der beiden Zeichenketten A und B.
D(i, j)- der günstigste Weg, die ersten i Zeichen von A in die ersten j Zeichen von B zu überführen. Eine Zelle der Tabelle auf dieser Seite.
[aᵢ ≠ bⱼ]- kostet 1, wenn sich die beiden Zeichen unterscheiden, und 0, wenn sie übereinstimmen — der Preis der Ersetzung, der entfällt, wenn nichts zu ersetzen ist.
d- die Antwort,
D(m, n): die Zelle unten rechts.
Woher die Formel kommt
- Lege fest, was eine Zelle bedeutet, bevor du irgendeine füllst. Sei
D(i, j)die kleinste Zahl von Bearbeitungen, die die ersteniZeichen von A in die erstenjvon B überführt. Gesucht istD(m, n), und jede andere Zelle ist eine kleinere Fassung derselben Frage. - Die Ränder erfordern kein Nachdenken. Um die ersten
jZeichen von B aus dem Nichts aufzubauen, musst du allejeinfügen, alsoD(0, j) = j. Um die ersteniZeichen von A auf nichts zu reduzieren, musst du alleilöschen, alsoD(i, 0) = i. Das ist die oberste Zeile und die linke Spalte des Gitters — und der Grund, warum sie einfach hochzählen. - Nun der Schritt, der die ganze Arbeit leistet. Nimm irgendeine optimale Folge für
D(i, j)und betrachte nur ihren letzten Zug. Es gibt genau drei Möglichkeiten: Sie hataᵢgelöscht und damit die AufgabeD(i−1, j)übrig gelassen; sie hatbⱼeingefügt undD(i, j−1)übrig gelassen; oder sie hataᵢmitbⱼgepaart undD(i−1, j−1)übrig gelassen. Jede davon ist eine bereits gefüllte Zelle. - Also ist die Zelle das Günstigste der drei:
D(i, j) = min( D(i−1, j) + 1, D(i, j−1) + 1, D(i−1, j−1) + [aᵢ ≠ bⱼ] ). Fülle das Gitter von links nach rechts und von oben nach unten, dann sind bei jeder Zelle ihre drei Nachbarn schon bekannt. Das ist der ganze Algorithmus —m × nZellen, drei Vergleiche je Zelle.
So liest du, was du siehst
Das Gitter auf dieser Seite ist genau diese Tabelle. Zeilen sind A, Spalten sind B, und die zusätzliche Zeile und Spalte oben links sind die leeren Präfixe aus Schritt 2 — deshalb zählen sie 0, 1, 2, 3. Die Einfärbung ist der Wert: der blasse diagonale Korridor ist dort, wo die beiden Zeichenketten noch günstig übereinstimmen. Fahre über eine Zelle oder tippe sie an, und das Feld darunter buchstabiert Schritt 3 für genau diese Zelle aus — die drei Kandidaten, jeder mit seiner Rechnung, der Sieger hervorgehoben. Die farbige Linie ist eine optimale Route, von unten rechts zurückverfolgt, und der Zuordnungsstreifen darunter ist dieselbe Route in Zeichen geschrieben.
- Setzt voraus
- Jede Bearbeitung kostet genau 1, und Zeichen werden auf exakte Gleichheit geprüft — keine Groß-/Kleinschreibungsangleichung, keine Unicode-Normalisierung, keine Vorstellung davon, welche Zeichen einander ähneln. Zwei Folgen sind hier sichtbar. Gezählt werden hier UTF-16-Codeeinheiten, nicht das, was du Buchstaben nennen würdest: Tippe ein einzelnes Emoji in ein Feld, und die Tabelle ist 3 × 1, denn ein Emoji sind zwei Einheiten, und es zu löschen kostet 2. Und
cafémit vorkomponiertemégegencaféalseplus kombinierendem Akzent ergibt Distanz 2, obwohl beide auf dem Bildschirm identisch aussehen. - Versagt, wenn
- Das Gitter hat
m × nZellen, der Aufwand wächst also mit dem Produkt der Längen. Für zwei Wörter ist das kein Problem, für eine Anfrage gegen ein Wörterbuch mit einer Million Einträgen ist es aussichtslos — das sind eine Million Gitter. Die naheliegende Antwort wäre ein raffinierterer Algorithmus, und die Überraschung ist, dass es im Wesentlichen keinen gibt: Backurs und Indyk zeigten 2015, dass eine deutlich subquadratische Editierdistanz die starke Exponentialzeit-Hypothese widerlegen würde. Echte Rechtschreibprüfungen unterbieten die Schranke nicht, sie weichen ihr aus — sie brechen ab, sobald die Distanz eine kleine Grenze überschreitet, oder indizieren so, dass fast jeder Kandidat nie verglichen wird.
Aufgabe vollständig gelöst
-
Die günstigste Editiersequenz, um kitten in sitting umzuwandeln 5 Schritte
Wandeln Sie kitten in sitting um. Finden Sie die günstigste Editiersequenz und beweisen Sie, dass keine günstigere existiert — berechnen Sie dann, was dies kostet, wenn das zweite Wort ein ganzes Wörterbuch ist.
-
Die Rekursionsformel ist bereits der gesamte Algorithmus. Jede Zelle fragt, was es kostet, hierher durch Löschen, Einfügen oder Ausrichten der beiden aktuellen Zeichen zu gelangen — wobei die letzte Option kostenlos ist, wenn sie übereinstimmen. Eine Zelle benötigt nur die drei Nachbarn oberhalb und zu ihrer Linken, sodass ein einziger Durchlauf von links nach rechts die Tabelle füllt.
-
Bevor irgendetwas ausgefüllt wird, schränken Sie das Ergebnis ein. Die Längen unterscheiden sich um eins, sodass mindestens eine Einfügung unvermeidbar ist; und das vollständige Überschreiben des Wortes kostet 7. Das Ergebnis liegt dazwischen, was die meisten Vermutungen bereits ausräumt.
-
Drei Editierungen reichen aus: Ersetzen k → s, Ersetzen e → i, Einfügen g. Jede ist eine einzelne zulässige Editieroperation, und die Kette endet auf dem Zielwort.
-
Das Vorweisen von drei Editierschritten beweist nur, dass die Distanz höchstens 3 beträgt. Die Tabelle beweist, dass sie exakt 3 ist, weil jede Route zur untersten rechten Ecke bewertet und an jeder Zelle auf dem Weg das Minimum genommen wird. Das ist der Unterschied zwischen dem Finden einer Antwort und dem Wissen, dass sie nicht übertroffen werden kann.
-
Der Aufwand beträgt eine Zelle pro Zeichenpaar — hier 42, was praktisch nichts ist. Bei einem Wörterbuch mit 100 000 Wörtern zu je sieben Buchstaben sind das über vier Millionen Zell-Updates für eine einzige Abfrage.
Antwort
Das Tool gibt 3 und eine Ähnlichkeit von 57,14% aus, was 1 − 3/7 entspricht: die durch das längere Wort normalisierte Distanz. Beide Werte stammen aus einer Tabelle, die Sie in einer Minute von Hand ausfüllen können. Was nicht skaliert, ist die Tabelle — der Aufwand beträgt Θ(mn), sodass das Verdoppeln beider Zeichenketten den Aufwand vervierfacht, und jede Rechtschreibprüfung, die Sie je benutzt haben, ist darauf ausgelegt, genau dies zu vermeiden. Der Ausweg ist nicht eine schnellere Tabelle. Es ist die Tatsache, dass Levenshtein die Dreiecksungleichung erfüllt, sodass d(a, c) ≤ d(a, b) + d(b, c) einem Index erlaubt zu beweisen, dass ein Kandidat zu weit entfernt ist, ohne jemals zu messen, wie weit.
-
Quellen (4)
- The theory section ends on why nobody has a much faster algorithm. This is the result that says they probably cannot have one: A. Backurs & P. Indyk, "Edit Distance Cannot Be Computed in Strongly Subquadratic Time (Unless SETH is False)." SIAM Journal on Computing 47(3), 1087–1097, 2018; first presented at STOC 2015.
- The grid this tool fills, and why filling each cell once is enough: R. A. Wagner & M. J. Fischer, "The String-to-String Correction Problem." Journal of the ACM 21(1), 168–173, 1974 — the dynamic-programming algorithm for the edit distance Levenshtein had defined in 1965.
- The fourth move in the Damerau cost model, and the survey of typing errors that argued for it: F. J. Damerau, "A technique for computer detection and correction of spelling errors." Communications of the ACM 7(3), 171–176, 1964.
- Insight block 3 ends on the problem of recovering the route without keeping the grid. This is the paper that solved it: D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequences." Communications of the ACM 18(6), 341–343, 1975.