webentwicklung-frage-antwort-db.com.de

Unterschied zwischen Jaro-Winkler und Levenshtein Abstand?

Ich habe einen Anwendungsfall, in dem ich Millionen von Datensätzen aus mehreren Dateien im Fuzzy-Modus abgleichen muss. Dafür habe ich zwei Algorithmen identifiziert: Jaro-Winkler und Levenshtein Entfernung bearbeiten.

Als ich anfing, beide zu erforschen, konnte ich den genauen Unterschied zwischen beiden nicht verstehen. Es scheint, dass Levenshtein die Anzahl der Änderungen zwischen zwei Zeichenfolgen angibt und Jaro-Winkler eine übereinstimmende Punktzahl zwischen 0,0 und 1,0 angibt. Ich habe den Algorithmus nicht verstanden. Da ich einen der beiden Algorithmen verwenden muss, muss ich die genauen Unterschiede in Bezug auf die Algorithmusleistung kennen.

69
Bhavesh Shah

Levenshtein zählt die Anzahl der Bearbeitungen (Einfügungen, Löschungen oder Ersetzungen), die erforderlich sind, um eine Zeichenfolge in die andere umzuwandeln. Damerau-Levenshtein ist eine modifizierte Version, die auch Transpositionen als einzelne Bearbeitungen betrachtet. Obwohl es sich bei der Ausgabe um die ganzzahlige Anzahl von Bearbeitungen handelt, kann diese durch die Formel auf einen Ähnlichkeitswert normiert werden

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

Der Jaro-Algorithmus ist ein Maß für gemeinsame Zeichen, das unter Berücksichtigung von Transpositionen nicht mehr als die Hälfte der Länge der längeren Zeichenfolge im Abstand beträgt. Winkler hat diesen Algorithmus dahingehend modifiziert, dass Unterschiede am Anfang der Zeichenfolge wichtiger sind als Unterschiede am Ende der Zeichenfolge. Jaro und Jaro-Winkler eignen sich zum Vergleichen kleinerer Zeichenfolgen wie Wörter und Namen.

Die Entscheidung für eine Verwendung ist nicht nur eine Frage der Leistung. Es ist wichtig, eine Methode auszuwählen, die der Art der zu vergleichenden Zeichenfolgen entspricht. Im Allgemeinen können beide von Ihnen erwähnten Algorithmen jedoch teuer sein, da jede Zeichenfolge mit jeder anderen Zeichenfolge verglichen werden muss. Bei Millionen von Zeichenfolgen in Ihrem Datensatz ist dies eine enorme Anzahl von Vergleichen. Das ist weitaus teurer als die Berechnung einer phonetischen Codierung für jede Zeichenfolge und die anschließende Gruppierung von Zeichenfolgen mit identischen Codierungen.

Zu diesen Algorithmen und anderen Fuzzy-String-Matching-Algorithmen gibt es im Internet eine Fülle detaillierter Informationen. Dieser wird Ihnen einen Anfang geben:

Ein Vergleich der Übereinstimmung von persönlichen Namen: Techniken und praktische Probleme

Demnach ist die Geschwindigkeit der vier von mir erwähnten Jaro- und Levenshtein-Algorithmen von schnell bis langsam:

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

der langsamste dauert 2 bis 3 Mal so lange wie der schnellste. Natürlich hängen diese Zeiten von der Länge der Zeichenfolgen und den Implementierungen ab, und es gibt Möglichkeiten, diese Algorithmen zu optimieren, die möglicherweise nicht verwendet wurden.

133
hatchet