Inhaltsverzeichnis
Sie werden dort platziert, um die Berechnung des Abstands zu erleichtern. Anhand eines Beispiels werden die detaillierten Schritte zur Berechnung der Abstandsmatrix mit Hilfe der dynamischen Programmierung deutlich gemacht. Das Problem wird in kleine Aufgaben zur Berechnung des Minimums einer 2 x 2 Matrix aufgeteilt. Nachdem der Zweck der zusätzlichen Zeilen und Spalten in der Matrix geklärt wurde, ist es an der Zeit, die Abstandsmatrix zu füllen, um den Wert zu erreichen, der den Abstand zwischen den beiden Wörtern darstellt. Wenn die zusätzliche Zeile und Spalte nicht vorhanden sind, gibt es 4 unbekannte Werte, und der vorherige Ansatz ist in diesem Fall nicht anwendbar. Wenn diese Zeilen und Spalten vorhanden sind, gibt es nur einen fehlenden Wert, und das ist der erwartete Wert für die Lösung des Problems durch dynamische Programmierung.
- Sie ist nach Vladimir Levenshtein benannt, der diese Distanz 1965 untersucht hat.
- Für eine gegebene Zelle an der Stelle, die dem Schnittpunkt zwischen den beiden ZeichenAundB entspricht, vergleichen wir die Werte an den drei Stellen (i,j-1), (i-1,j) und (i-1,j-1).
- Inoffiziell ist die Levenshtein-Distanz zwischen zwei Wörtern die minimale Anzahl von Einzelbuchstabenänderungen (d. h. Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern.
- Die Edit-Distanz kann jedoch verwendet werden, um Übereinstimmungen einer kurzen Zeichenkette, z.
Der erste Schritt ist die Initialisierung einer Abstandsmatrix, wie in der folgenden Tabelle angegeben. Ohne die Zeilen und Spalten, die als Beschriftungen verwendet werden, beträgt die Matrixgröße 5 x 6. Die Anzahl der Zeilen, 5, entspricht der Anzahl der Zeichen im ersten Wort +1.
Levenshtein-algorithmus Für Aml-sanktionen
Durch den Vergleich der 3 vorhandenen Werte wird der vierte Wert berechnet. Inoffiziell ist die Levenshtein-Distanz zwischen zwei Wörtern die minimale Anzahl von Einzelbuchstabenänderungen (d. h. Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um ein Wort in das andere zu ändern. Sie ist nach Vladimir Levenshtein benannt, der diese Distanz 1965 untersucht hat. Es handelt sich um die minimale Anzahl von Einzelbuchstabenänderungen, die erforderlich sind, um ein Wort in ein anderes zu verwandeln. Beim approximativen String-Matching geht es darum, Übereinstimmungen für kurze Zeichenfolgen in vielen längeren Texten zu finden, in Situationen, in denen eine geringe Anzahl von Unterschieden zu erwarten ist.
Die Levenshtein-Distanz ist eine String-Metrik zur Messung der Differenz zwischen zwei Sequenzen. Sie ist nach Vladimir Levenshtein benannt, der diese Gleichung 1965 entdeckte. Zurück zu unserer Frage, warum wir die zusätzliche Zeile und Spalte in der Abstandsmatrix hinzufügen. Nehmen wir an, dass der Abstand zwischen den ersten beiden Präfixen der beiden Wörter berechnet werden soll, nämlich . Nach dem oben erläuterten Ansatz der dynamischen Programmierung muss es drei bekannte Werte und nur einen fehlenden Wert geben.
1 Textuelle Ähnlichkeit Zwischen Abfragen
Wir folgen vordefinierten Schritten, die auf zwei beliebige Wörter angewandt werden könnten, um ein Wort in ein anderes zu verwandeln. Die Strategie, die wir jetzt besprechen werden, ist die Berechnung einer Abstandsmatrix mit Hilfe der dynamischen Programmierung. Bei zwei Wörtern A und B enthält die Abstandsmatrix die Abstände zwischen allen Präfixen des Wortes A und allen Präfixen des Wortes B. Die meisten Implementierungen verwenden ein- oder zweidimensionale Arrays, um die Abstände der Präfixe der verglichenen Wörter zu speichern. In den meisten Anwendungen ist die Größe dieser Strukturen vorher bekannt. Dies ist der Fall, wenn beispielsweise der Abstand nur dann relevant ist, wenn er unter einem bestimmten maximal zulässigen Abstand liegt.
Klasse Methodenzusammenfassung
Bei einer Matrix gab es, wie im vorigen Abschnitt erläutert, 3 zu vergleichende Werte. Bei der Berechnung der Abstände sind nur 2 Werte zu vergleichen, wobei die erste Teilmenge nur im zweiten Wort enthalten ist. Die Levenshtein-Distanz zwischen zwei Zeichenfolgen ist die Anzahl der Löschungen, Einfügungen oder Ersetzungen, die erforderlich sind, um die Quellzeichenfolge in die Zielzeichenfolge umzuwandeln. Die drei möglichen Bearbeitungen sind Einfügung, Löschung und Ersetzung. Berechnen wir den Abstand zwischen dem ersten Präfix des ersten Wortes, k, und dem zweiten Präfix des zweiten Wortes, he. Wie bereits besprochen, beträgt der Abstand 2, und für die nächsten Präfixe fügen wir einfach eins hinzu, um einen Abstand von 3, 4 und 5 zu erhalten.
