python - levenshtein - Cuándo usar qué función fuzz para comparar 2 cadenas

python fuzzy

Question

Aprendo fuzzywuzzy en python, entiendo el concepto de fuzz.ratio, fuzz.partial_ratio, fuzz.token_sort_ratio y fuzz.token_set_ratio. Mi pregunta es cuándo usar qué función? ¿Verifico primero la longitud de las 2 cuerdas, decir si no es similar, luego descartar fuzz.partial_ratio? O si la longitud de las 2 cuerdas es similar, usaré fuzz.token_sort_ratio? O siempre debería usar fuzz.token_set_ratio?

¿Alguien sabe qué criterios utiliza SeatGeek?

Estoy tratando de construir un sitio web de bienes raíces, pensando en usar fuzzywuzzy para comparar direcciones.

Cualquier idea es muy apreciada.

R.

Answer 1

A partir de junio de 2017, fuzzywuzzy también incluye algunas otras funciones de comparación. Aquí hay un resumen de los que faltan en la respuesta aceptada (tomada del código fuente ):

fuzz.partial_token_sort_ratio

El mismo algoritmo que en token_sort_ratio , pero en lugar de aplicar la ratio después de ordenar los tokens, usa partial_ratio .

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

El mismo algoritmo que en token_set_ratio , pero en lugar de aplicar la ratio a los conjuntos de tokens, usa partial_ratio .

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

Solo envoltorios alrededor de fuzz.ratio con algunas validaciones y cortocircuitos, incluidos aquí para completar. UQRatio es una versión Unicode de QRatio .

fuzz.WRatio

Un intento de ponderar (el nombre significa ''Relación ponderada'') resulta de diferentes algoritmos para calcular la puntuación ''mejor''. Descripción del código fuente:

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

Versión Unicode de WRatio .

Answer 2

Gran pregunta

Soy ingeniero en SeatGeek, así que creo que puedo ayudar aquí. Tenemos una excelente publicación en el blog que explica las diferencias bastante bien, pero puedo resumir y ofrecer información sobre cómo usamos los diferentes tipos.

Visión general

Bajo el capó, cada uno de los cuatro métodos calcula la distancia de edición entre algunos ordenamientos de los tokens en ambas cadenas de entrada. Esto se hace usando la función difflib.ratio que :

Devuelve una medida de la similitud de las secuencias (float en [0,1]).

Donde T es el número total de elementos en ambas secuencias, y M es el número de coincidencias, esto es 2.0 * M / T. Tenga en cuenta que esto es 1 si las secuencias son idénticas y 0 si no tienen nada en común.

Los cuatro métodos fuzzywuzzy llaman difflib.ratio en diferentes combinaciones de las cadenas de entrada.

fuzz.ratio

Sencillo. Simplemente llama a difflib.ratio en las dos cadenas de entrada ( code ).

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

fuzz.partial_ratio

Intenta tener en cuenta las coincidencias de cadena parcial mejor. ratio llamadas que usa la cadena más corta (longitud n) contra todas las subcadenas de longitud n de la cadena más grande y devuelve la puntuación más alta ( code ).

Observe aquí que "YANKEES" es la cadena más corta (longitud 7), y ejecutamos la relación con "YANKEES" contra todas las subcadenas de longitud 7 de "NEW YORK YANKEES" (que incluiría la verificación contra "YANKEES", una coincidencia del 100%) ):

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

fuzz.token_sort_ratio

Intenta dar cuenta de cadenas similares fuera de orden. ratio llamadas en ambas cadenas después de ordenar las fichas en cada cadena ( code ). Fíjate en que fuzz.ratio y fuzz.partial_ratio fallan, pero una vez que fuzz.partial_ratio los tokens es una coincidencia del 100%:

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

Intenta descartar diferencias en las cuerdas. Relación de llamadas en tres conjuntos de subcadenas particulares y devuelve el máximo ( code ):

1. solo intersección y la intersección con el resto de la cadena uno
2. solo intersección y la intersección con el resto de la cadena dos
3. intersección con el resto de uno e intersección con el resto de dos

Tenga en cuenta que al dividir la intersección y los restos de las dos cadenas, consideramos qué tan similares y diferentes son las dos cadenas:

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

Solicitud

Aquí es donde ocurre la magia. En SeatGeek, esencialmente creamos un puntaje vectorial con cada proporción para cada punto de datos (lugar, nombre del evento, etc.) y lo usamos para informar decisiones programáticas de similitud que son específicas de nuestro dominio de problemas.

Dicho esto, la verdad por la que se dice no suena como si FuzzyWuzzy fuera útil para su caso de uso. Será tremendamente malo para determinar si dos direcciones son similares. Considere dos direcciones posibles para SeatGeek HQ: "235 Park Ave Floor 12" y "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 otorga a estas cadenas un alto puntaje de coincidencia, pero una dirección es nuestra oficina cerca de Union Square y la otra está en el otro lado de Grand Central.

Para su problema, sería mejor utilizar la API de geocodificación de Google .