Haben Sie http://www.merriampark.com/ld.htm gelesen?
Sie berechnen die Kosten für die Umwandlung - die Anzahl der Einfügungen und Löschungen -, die erforderlich sind, um eine Zeichenfolge in eine andere zu konvertieren.
Diese zu transformierende "Kosten" gibt den Abstand zwischen den beiden Saiten an.
Was ist mit Austausch? Das ist der Damerau–Levenshtein Algorithmus, der anders ist. Die Einbeziehung von Börsen verbessert die Dinge nicht sehr.
Die Essenz besteht darin, eine Matrix zwischen den beiden Wörtern zu erstellen und Spalte für Spalte zu berechnen - die "Entfernung" von jedem Buchstaben jedes Wortes zu jedem Buchstaben des anderen Wortes. Die untere rechte Ecke dieser Matrix ist die Gesamtentfernung unter Berücksichtigung aller Buchstaben.
Frage 1)
Die Zelle „oberhalb“ spiegelt eine Geschichte von Veränderungen, und das Zeichen für diese Zeile ist (in der Regel) verschieden ist, so dass diese Zelle eine Deletion relativ zu ihm.
Die Zelle "left" gibt eine Änderungshistorie wieder, und das Zeichen für diese Spalte ist (normalerweise) anders als das, daher ist diese Zelle eine Einfügung relativ zu ihr.
Die einzige Zeit, die dies normalerweise falsch wäre, sind Wörter mit einer Drei-Buchstaben-Sequenz. Selten in Englisch.
Der Zeilen-Spalten-Vergleich hat eine Gebühr von 0 oder 1.
das Minimum von „Geschichte plus eine Veränderung“, und die tatsächlich Kosten für eine Änderung sind die anwendbar Kosten.
Frage 2)
Die Variablen i und j sind nicht Längen von irgendetwas. Sie sind Positionen in der Vergleichsmatrix. Die "Einfügung" und "Löschung" ist die Aktion, die erforderlich ist, um ein Wort in das andere umzuwandeln. Die Anzahl der Einfüge-/Löschaktionen ist der Abstand zwischen den Wörtern.
Ja, ich habe diesen Link tatsächlich gelesen. Gute Antwort. Eine letzte Sache jedoch: In der minimalen Funktion gibt es +1 für eine Zelle und + Kosten für eine Zelle. Sicherlich sind 1 und Kosten derselbe Wert (1), da Kosten niemals größer als 1 sind und nicht 0, da dies zur Ausführung der if-Anweisung führen würde (wenn cost == 0 usw.). Ich verstehe diese Logik nicht? – dotnetdev
Nein. Die Kosten sind nicht immer 1. Es kann viel, viel größer als eins sein, wenn die benachbarten Buchstaben keine guten Übereinstimmungen sind. Beim ersten Start gehen Sie davon aus, dass der letzte Buchstabe eines n-Zeichen-Worts das Ergebnis von n Einfügungen ist. Es kostet zunächst n, bis Ihr Vergleich zeigt, dass es weniger ist, weil einige Zeichen tatsächlich übereinstimmen. –