Unterschied zwischen Jaro-Winkler und Levenshtein Entfernung?

Question

Ich habe einen Anwendungsfall, wo ich Fuzzy-Matching von Millionen von Datensätzen aus mehreren Dateien tun muss. Ich habe zwei Algorithmen dafür gefunden: Jaro-Winkler und Levenshtein bearbeiten Abstand.

Als ich anfing beide zu erforschen, war ich nicht in der Lage zu verstehen, was der genaue Unterschied zwischen den beiden ist. Es scheint, Levenshtein gibt die Anzahl der Bearbeitungen zwischen zwei Strings, und Jaro-Winkler gibt eine übereinstimmende Punktzahl zwischen 0,0 bis 1,0. Ich habe den Algorithmus nicht verstanden. Da ich einen der beiden Algorithmen verwenden muss, muss ich die genauen Unterschiede in Bezug auf die Leistung des Algorithmus kennen.

Answer 1

Levenshtein zählt die Anzahl der Bearbeitungen (Einfügungen, Löschungen oder Ersetzungen), die zum Konvertieren einer Zeichenfolge in die andere erforderlich sind. Damerau-Levenshtein ist eine modifizierte Version, die Transpositionen auch als einzelne Bearbeitungen betrachtet. Obwohl die Ausgabe der ganzzahligen Anzahl von Änderungen ist, kann dieser normalisierten sein, einen Ähnlichkeitswert durch die Formel ergeben

1 - (edit distance/length of the larger of the two strings) 

Der Jaro Algorithmus ein Maß für Zeichen gemeinsam ist, wobei nicht mehr als die Hälfte der Länge der längeren String in Distanz, unter Berücksichtigung von Transpositionen. Winkler modifizierte diesen Algorithmus, um die Idee zu unterstützen, dass Unterschiede nahe dem Anfang der Zeichenfolge signifikanter sind als Unterschiede nahe dem Ende der Zeichenfolge. Jaro und Jaro-Winkler sind geeignet, kleinere Strings wie Wörter und Namen zu vergleichen.

Die Entscheidung, welche zu verwenden ist, ist nicht nur eine Frage der Leistung. Es ist wichtig, eine Methode auszuwählen, die der Art der Zeichenfolgen entspricht, die Sie vergleichen. Im Allgemeinen können beide der genannten Algorithmen jedoch teuer sein, da jeder String mit jedem anderen String verglichen werden muss, und mit Millionen von Strings in Ihrem Datensatz, das ist eine enorme Anzahl von Vergleichen. Das ist viel teurer als das Berechnen einer phonetischen Codierung für jede Zeichenfolge und das einfache Gruppieren von Zeichenfolgen mit identischen Codierungen.

Es gibt eine Fülle von detaillierten Informationen zu diesen Algorithmen und anderen Fuzzy-String-Matching-Algorithmen im Internet. Dieser wird Ihnen einen Start:

A Comparison of Personal Name Matching: Techniques and Practical Issues

Nach diesem Papier wird die Geschwindigkeit der vier Jaro und Levenshtein Algorithmen ich erwähnt habe, sind vom schnellsten zum langsamsten:

• Jaro
• Jaro-Winkler
• Levenshtein
• Damerau-Levenshtein

mit der langsamsten Einnahme 2 bis 3 mal so lange wie die schnellste. Natürlich hängen diese Zeiten von den Längen der Strings und der Implementierungen ab, und es gibt Möglichkeiten, diese Algorithmen zu optimieren, die möglicherweise nicht verwendet wurden.