webentwicklung-frage-antwort-db.com.de

Wann soll welche Fuzz-Funktion verwendet werden, um 2 Strings zu vergleichen?

Ich lerne fuzzywuzzy in Python.

Ich verstehe das Konzept von fuzz.ratio, fuzz.partial_ratio, fuzz.token_sort_ratio Und fuzz.token_set_ratio. Meine Frage ist, wann welche Funktion zu verwenden ist?

  • Überprüfe ich zuerst die Länge der 2 Zeichenfolgen, sage wenn nicht ähnlich, dann schließe ich fuzz.partial_ratio Aus?
  • Wenn die Länge der 2 Zeichenfolgen ähnlich ist, verwende ich fuzz.token_sort_ratio?
  • Sollte ich immer fuzz.token_set_ratio Verwenden?

Weiß jemand, welche Kriterien SeatGeek verwendet?

Ich versuche eine Immobilienwebsite zu erstellen und denke daran, fuzzywuzzy zum Vergleichen von Adressen zu verwenden.

32
Pot

Gute Frage.

Ich bin Ingenieur bei SeatGeek und kann hier helfen. Wir haben einen großartigen Blog-Beitrag , der die Unterschiede recht gut erklärt, aber ich kann zusammenfassen und einen Einblick geben, wie wir die verschiedenen Typen verwenden.

Überblick

Unter der Haube berechnet jede der vier Methoden den Bearbeitungsabstand zwischen einer bestimmten Reihenfolge der Token in beiden Eingabezeichenfolgen. Dies geschieht mit dem difflib.ratio function welches wird :

Geben Sie ein Maß für die Ähnlichkeit der Sequenzen zurück (float in [0,1]).

Dabei ist T die Gesamtzahl der Elemente in beiden Sequenzen und M die Anzahl der Übereinstimmungen. Dies ist 2,0 * M/T. Beachten Sie, dass dies 1 ist, wenn die Sequenzen identisch sind, und 0, wenn sie nichts gemeinsam haben.

Die vier Fuzzywuzzy-Methoden rufen difflib.ratio für verschiedene Kombinationen der Eingabezeichenfolgen.

fuzz.ratio

Einfach. Ruft einfach difflib.ratio auf den beiden Eingabezeichenfolgen ( Code ).

fuzz.ratio("NEW YORK METS", "NEW YORK MEATS")
> 96

fuzz.partial_ratio

Versuche, Teilzeichenfolgenübereinstimmungen besser zu berücksichtigen. Ruft ratio mit der kürzesten Zeichenfolge (Länge n) für alle Teilzeichenfolgen mit n Länge der größeren Zeichenfolge auf und gibt die höchste Punktzahl zurück ( Code ).

Beachten Sie hier, dass "YANKEES" die kürzeste Zeichenfolge (Länge 7) ist und wir das Verhältnis mit "YANKEES" für alle Teilzeichenfolgen der Länge 7 von "NEW YORK YANKEES" ausführen (einschließlich der Überprüfung gegen "YANKEES", eine 100% ige Übereinstimmung ):

fuzz.ratio("YANKEES", "NEW YORK YANKEES")
> 60
fuzz.partial_ratio("YANKEES", "NEW YORK YANKEES")
> 100

fuzz.token_sort_ratio

Versuche, ähnliche Zeichenfolgen nicht in der richtigen Reihenfolge zu berücksichtigen. Ruft ratio für beide Zeichenfolgen auf, nachdem die Token in jeder Zeichenfolge sortiert wurden ( Code ). Beachten Sie hier fuzz.ratio und fuzz.partial_ratio beide schlagen fehl, aber sobald Sie die Token sortiert haben, ist es eine 100% ige Übereinstimmung:

fuzz.ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 45
fuzz.partial_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 45
fuzz.token_sort_ratio("New York Mets vs Atlanta Braves", "Atlanta Braves vs New York Mets")
> 100

fuzz.token_set_ratio

Versuche, Unterschiede in den Zeichenfolgen auszuschließen. Ruft das Verhältnis für drei bestimmte Teilzeichenfolgensätze auf und gibt das Maximum ( Code ) zurück:

  1. nur Schnittpunkt und der Schnittpunkt mit dem Rest der ersten Zeichenfolge
  2. nur Schnittpunkt und der Schnittpunkt mit dem Rest der zweiten Zeichenfolge
  3. schnittpunkt mit dem Rest von eins und Schnittpunkt mit dem Rest von zwei

Beachten Sie, dass wir durch Aufteilen des Schnittpunkts und der Reste der beiden Zeichenfolgen berücksichtigen, wie ähnlich und unterschiedlich die beiden Zeichenfolgen sind:

fuzz.ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 36
fuzz.partial_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 61
fuzz.token_sort_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 51
fuzz.token_set_ratio("mariners vs angels", "los angeles angels of anaheim at seattle mariners")
> 91

Anwendung

Hier geschieht die Magie. Bei SeatGeek erstellen wir im Wesentlichen eine Vektorbewertung mit jedem Verhältnis für jeden Datenpunkt (Veranstaltungsort, Ereignisname usw.) und verwenden diese, um programmatische Ähnlichkeitsentscheidungen zu informieren, die für unsere Problemdomäne spezifisch sind.

Davon abgesehen klingt die Wahrheit nicht so, als ob FuzzyWuzzy für Ihren Anwendungsfall nützlich wäre. Es wird enorm schlecht sein, festzustellen, ob zwei Adressen ähnlich sind. Betrachten Sie zwei mögliche Adressen für SeatGeek HQ: "235 Park Ave Floor 12" und "235 Park Ave S. Floor 12":

fuzz.ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 93
fuzz.partial_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 85
fuzz.token_sort_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 95
fuzz.token_set_ratio("235 Park Ave Floor 12", "235 Park Ave S. Floor 12")
> 100

FuzzyWuzzy gibt diesen Saiten eine hohe Match-Punktzahl, aber eine Adresse ist unser eigentliches Büro in der Nähe des Union Square und die andere befindet sich auf der anderen Seite von Grand Central.

Verwenden Sie für Ihr Problem besser die Google Geocoding API .

55
Rick Hanlon II

Ab Juni 2017 enthält fuzzywuzzy auch einige andere Vergleichsfunktionen. Hier ist eine Übersicht derjenigen, die in der akzeptierten Antwort fehlen (entnommen aus dem Quellcode ):

fuzz.partial_token_sort_ratio

Gleicher Algorithmus wie in token_sort_ratio, Aber anstatt ratio nach dem Sortieren der Token anzuwenden, wird partial_ratio Verwendet.

fuzz.token_sort_ratio("New York Mets vs Braves", "Atlanta Braves vs New York Mets")
> 85
fuzz.partial_token_sort_ratio("New York Mets vs Braves", "Atlanta Braves vs New York Mets")
> 100    
fuzz.token_sort_ratio("React.js framework", "React.js")
> 62
fuzz.partial_token_sort_ratio("React.js framework", "React.js")
> 100

fuzz.partial_token_set_ratio

Der gleiche Algorithmus wie in token_set_ratio, Verwendet jedoch partial_ratio, Anstatt ratio auf die Tokensätze anzuwenden.

fuzz.token_set_ratio("New York Mets vs Braves", "Atlanta vs New York Mets")
> 82
fuzz.partial_token_set_ratio("New York Mets vs Braves", "Atlanta vs New York Mets")
> 100    
fuzz.token_set_ratio("React.js framework", "Reactjs")
> 40
fuzz.partial_token_set_ratio("React.js framework", "Reactjs")
> 71   

fuzz.QRatio, fuzz.UQRatio

Der Vollständigkeit halber nur fuzz.ratio Mit einigen Validierungen und Kurzschlüssen umwickeln. UQRatio ist eine Unicode-Version von QRatio.

fuzz.WRatio

Ein Versuch zu gewichten (der Name steht für 'Weighted Ratio') ergibt sich aus verschiedenen Algorithmen, um die 'beste' Punktzahl zu berechnen. Beschreibung aus dem Quellcode:

1. Take the ratio of the two processed strings (fuzz.ratio)
2. Run checks to compare the length of the strings
    * If one of the strings is more than 1.5 times as long as the other
      use partial_ratio comparisons - scale partial results by 0.9
      (this makes sure only full results can return 100)
    * If one of the strings is over 8 times as long as the other
      instead scale by 0.6
3. Run the other ratio functions
    * if using partial ratio functions call partial_ratio,
      partial_token_sort_ratio and partial_token_set_ratio
      scale all of these by the ratio based on length
    * otherwise call token_sort_ratio and token_set_ratio
    * all token based comparisons are scaled by 0.95
      (on top of any partial scalars)
4. Take the highest value from these results
   round it and return it as an integer.

fuzz.UWRatio

Unicode-Version von WRatio.

9