Tutorial de Comparación de cadenas difusas en Python

Ediciones y distancia de edición

El algoritmo de concordancia de cadenas difusas trata de determinar el grado de cercanía entre dos cadenas diferentes. Esto se descubre utilizando una métrica de distancia conocida como "distancia de edición". La distancia de edición determina lo cerca que están dos cadenas encontrando el número mínimo de “edits” necesarias para transformar una cadena en otra. 

Si la distancia de edición cuenta el número de operaciones de edición para decirnos a cuántas operaciones de distancia está una cadena de otra, una edición es una operación realizada sobre una cadena para transformarla en otra.  

Hay cuatro tipos principales de ediciones:

• Insertar (añadir una letra)
• Borrar (eliminar una letra)
• Cambiar (intercambiar dos letras adyacentes)
• Sustituir (cambiar una letra por otra)

Estas cuatro operaciones de edición permiten modificar cualquier cadena. 

Combinar las operaciones de edición te permite descubrir la lista de posibles cadenas que están a N ediciones, donde N es el número de operaciones de edición. Por ejemplo, la distancia de edición entre "Londres" y "Londin" es uno, ya que la sustitución de la "i" por una "o" conduce a una coincidencia exacta. 

¿Pero cómo se calcula concretamente la distancia de edición, te preguntarás?

Existen distintas variantes de cómo calcular la distancia de edición. Por ejemplo, existe la distancia Levenshtein, la distancia Hamming, la distancia Jaro y otras más.

La distancia Levenshtein

En este tutorial, sólo nos interesa la distancia Levenshtein. 

Es una métrica que debe su nombre a Vladimir Levenshtein, quien la consideró originalmente en 1965 para medir la diferencia entre dos secuencias de palabras. Podemos utilizarlo para descubrir el número mínimo de ediciones que hay que hacer para cambiar una secuencia de una palabra por otra. 

He aquí el cálculo formal: 

Donde denota 0 cuando a=b y 1 en caso contrario. 

Es importante observar que las filas del mínimo de arriba corresponden a una supresión, una inserción y una sustitución en ese orden.

También es posible calcular el cociente de similitud de Levenshtein a partir de la distancia de Levenshtein. Esto puede hacerse utilizando la siguiente fórmula:

donde |a| y |b| son las longitudes de las secuencias a y b, respectivamente.

Comparación simple de cadenas difusas

Uno de los paquetes más populares para la concordancia difusa de cadenas en Python era FuzzyWuzzy. Sin embargo, FuzzyWuzzy se actualizó y cambió de nombre en 2021. Ahora se llama TheFuzz.  

TheFuzz sigue siendo una de las bibliotecas de código abierto más avanzadas para la comparación difusa de cadenas en Python. Fue desarrollado por primera vez por SeatGeek con el fin de distinguir si dos listados de entradas con nombres similares eran para el mismo evento. 

De acuerdo con FuzzyWuzzy, TheFuzz utiliza la distancia de edición de Levenshtein para calcular el grado de cercanía entre dos cadenas. También ofrece funciones para determinar la similitud de las cadenas en diversas situaciones, como verás en este tutorial.

En primer lugar, debemos instalar el paquete fuzz. Puedes hacerlo con pip utilizando el siguiente comando: 

!pip install thefuzz

Nota: Esta biblioteca viene preinstalada con tu DataCamp Workspace. 

Ahora, veamos algunas de las cosas que podemos hacer con thefuzz. 

Sigue el código en este DataCamp Workspace. 

Proporción simple

Podemos determinar la relación simple entre dos cadenas utilizando el método ratio() del objeto fuzz. Esto simplemente calcula la distancia de edición basándose en el orden de ambas cadenas de entrada difflib.ratio() . Consulta la documentación de difflib para saber más. 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Similarity score: {fuzz.ratio(name, full_name)}")

"""
Similarity Score: 86
"""

En el código, utilizamos dos variaciones de mi nombre para comparar la puntuación de similitud, que fue de 86. 

Comprobemos esto con la relación parcial. 

Proporción parcial 

Para comprobar la proporción parcial, lo único que debemos hacer en el código anterior es llamar a partial_ratio() en nuestro objeto fuzz en lugar de a ratio(). 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Similarity score: {fuzz.partial_ratio(name, full_name)}")

"""
Similarity Score: 67
"""

Vemos una disminución. ¿Qué está pasando? 

Pues bien, la partial_ratio() trata de averiguar lo parcialmente parecidas que son dos cuerdas. Dos cadenas son parcialmente similares si tienen algunas de las palabras en un orden común. 

El partial_ratio() calcula la similitud tomando la cadena más corta, que en este caso se almacena en la variable nombre, y luego la compara con las subcadenas de la misma longitud de la cadena más larga, que se almacena en nombre_completo. 

Como el orden importa en la relación parcial, nuestra puntuación bajó en este caso. Por lo tanto, para obtener una coincidencia de similitud del 100 %, tendrías que mover la parte "K D" (que significa mi segundo nombre) al final de la cadena. Por ejemplo: 

# Order matters with partial ratio
# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis Pykes K D"
​
print(f"Partial ratio similarity score: {fuzz.partial_ratio(name, full_name)}")
​
# But order will not effect simple ratio if strings do not match
print(f"Simple ratio similarity score: {fuzz.ratio(name, full_name)}")

"""
Partial ratio similarity score: 100
Simple ratio similarity score: 86
"""

¿Y si queremos que nuestro comparador de cadenas difusas ignore el orden? 

Entonces puede que quieras utilizar la “token sort ratio”. 

Token sort ratio

De acuerdo, queremos ignorar el orden de las palabras en las cadenas, pero determinar lo parecidas que son: la ordenación por tokens te ayuda a hacer exactamente eso. A la clasificación por tokens no le importa en qué orden aparecen las palabras. Tiene en cuenta las cadenas similares que no están en el orden expresado anteriormente. 

Por tanto, deberíamos obtener una puntuación del 100 % utilizando la relación de clasificación por tokens con el ejemplo más reciente: 

# Check the similarity score
full_name = "Kurtis K D Pykes"
full_name_reordered = "Kurtis Pykes K D"
​
# Order does not matter for token sort ratio
print(f"Token sort ratio similarity score: {fuzz.token_sort_ratio(full_name_reordered, full_name)}")
​
# Order matters for partial ratio
print(f"Partial ratio similarity score: {fuzz.partial_ratio(full_name, full_name_reordered)}")
​
# Order will not effect simple ratio if strings do not match
print(f"Simple ratio similarity score: {fuzz.ratio(name, full_name)}")

"""
Token sort ratio similarity score: 100
Partial ratio similarity score: 75
Simple ratio similarity score: 86
"""

... y como era de esperar, lo hicimos. 

Volvamos a las variables originales name y full_name. ¿Qué crees que ocurrirá si utilizamos ahora la clasificación por tokens? 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"

print(f"Token sort ratio similarity score: {fuzz.token_sort_ratio(name, full_name)}")

"""
Token sort ratio similarity score: 86
"""

La puntuación baja. 

Esto se debe a que la ordenación por tokens sólo tiene en cuenta el orden. Si en las cadenas hay palabras que no son similares, tendrá un impacto negativo en la proporción de similitud, como hemos visto anteriormente.

Pero hay una solución. 

Token set ratio

El método token_set_ratio() es bastante similar al token_sort_ratio(), salvo que elimina los tokens comunes antes de calcular lo similares que son las cadenas: esto es extremadamente útil cuando las cadenas tienen una longitud significativamente diferente. 

Como las variables nombre y nombre_completo tienen ambas "Kurtis Pykes", podemos esperar que la similitud de la proporción del conjunto de tokens sea del 100 %. 

# Check the similarity score
name = "Kurtis Pykes"
full_name = "Kurtis K D Pykes"
​
print(f"Token sort ratio similarity score: {fuzz.token_set_ratio(name, full_name)}")

"""
Token sort ratio similarity score: 100
"""

Proceso 

El módulo de proceso permite a los usuarios extraer texto de una colección mediante la concordancia difusa de cadenas. Llamar al método extract() en el módulo proceso devuelve las cadenas con una puntuación de similitud en un vector. Por ejemplo: 

from thefuzz import process
​
collection = ["AFC Barcelona", "Barcelona AFC", "barcelona fc", "afc barcalona"]
print(process.extract("barcelona", collection, scorer=fuzz.ratio))

"""
[('barcelona fc', 86), ('AFC Barcelona', 82), ('Barcelona AFC', 82), ('afc barcalona', 73)]
"""

Podemos controlar la longitud del vector devuelto por el método extract() ajustando el parámetro limit a la longitud deseada.

print(process.extract("barcelona", collection, scorer=fuzz.ratio))

"""
[('barcelona fc', 86), ('AFC Barcelona', 82), ('Barcelona AFC', 82)]
"""

En este caso, la función extract() devuelve las tres cadenas que más se aproximan en función del puntuador que hayamos definido. 

Coincidencia de cadenas difusas con pandas

En esta sección, veremos cómo hacer coincidencias difusas de cadenas en un marco de datos de pandas. 

Supongamos que tienes unos datos que has exportado a un marco de datos de pandas, y te gustaría unirlos a los datos que ya tienes. 

import pandas as pd
​
# Creating a dataframe
dict_one = {
  "country": ["England", "Scotland", "Wales", "United Kingdom", "Northern Ireland"],
  "population_in_millions": [55.98, 5.45, 3.14, 67.33, 1.89]
}
​
dict_two = {
  "country": ["Northern Iland", "Wles", "Scotlnd", "Englnd", "United K."],
  "GDP_per_capita": [24900, 23882, 37460, 45101, 46510.28]
}
​
existing_data = pd.DataFrame(dict_one)
exported_data = pd.DataFrame(dict_two)
​
print(existing_data, exported_data, sep="\n\n")

"""
          country  population_in_millions
0           England                   55.98
1          Scotland                    5.45
2             Wales                    3.14
3    United Kingdom                   67.33
4  Northern Ireland                    1.89

          country  GDP_per_capita
0  Northern Iland        24900.00
1            Wles        23882.00
2         Scotlnd        37460.00
3          Englnd        45101.00
4       United K.        46510.28
"""

Hay un problema importante. 

Los datos existentes tienen la ortografía correcta de los países, pero los datos exportados no. Si intentamos unir los dos marcos de datos en la columna país, pandas no reconocería las palabras mal escritas como iguales a las correctamente escritas. Por tanto, el resultado devuelto por la función de fusión no será el esperado. 

Esto es lo que ocurriría si lo intentáramos: 

# Attempt to join the two dataframe
data = pd.merge(existing_data, exported_data, on="country", how="left")
print(data.head())

"""
          country  population_in_millions  GDP_per_capita
0           England                   55.98             NaN
1          Scotland                    5.45             NaN
2             Wales                    3.14             NaN
3    United Kingdom                   67.33             NaN
4  Northern Ireland                    1.89             NaN
"""

Esto anula todo el propósito de intentar fusionar estos marcos de datos. 

Sin embargo, podemos evitar este problema con la concordancia difusa de cadenas.

Veamos cómo queda en código: 

# Rename the misspelled columns
exported_data["country"] = exported_data["country"].apply(
  lambda x: process.extractOne(x, existing_data["country"], scorer=fuzz.partial_ratio)[0]
)
​
# Attempt to join the two dataframe
data = pd.merge(existing_data, exported_data, on="country", how="left")
print(data.head())

"""
          country  population_in_millions  GDP_per_capita
0           England                   55.98        45101.00
1          Scotland                    5.45        37460.00
2             Wales                    3.14        23882.00
3    United Kingdom                   67.33        46510.28
4  Northern Ireland                    1.89        24900.00
"""

En este código, hemos renombrado los valores mal escritos de la columna país de los datos exportados utilizando una función lambda ordenada en asociación con el método process.extractOne(). Ten en cuenta que hemos utilizado un índice 0 en el resultado del extractOne() para devolver en línea la cadena similar en lugar de una lista que contenga la cadena y el valor de similitud. 

A continuación, unimos los marcos de datos de la columna país mediante una unión izquierda. El resultado es un único marco de datos que contiene los países correctamente escritos (incluida la unión política del Reino Unido).

Reflexiones finales

En este tutorial, has aprendido 

• Ediciones y distancia de edición
• La distancia de edición de Levenshtein y cómo funciona
• Cómo hacer coincidencias difusas de cadenas en Python con la biblioteca fuzz
• Cómo hacer coincidencias difusas de cadenas con marcos de datos Pandas. 

Los ejemplos que aquí se presentan pueden ser sencillos, pero bastan para ilustrar cómo tratar diversos casos de lo que un ordenador cree que son cadenas que no coinciden. Existen varias aplicaciones de la concordancia difusa en ámbitos como la corrección ortográfica y la bioinformática, donde se utiliza la lógica difusa para cotejar secuencias de ADN.

Recursos adicionales

• Tutorial de cadenas en Python
• Tutorial Python contiene cadenas
• Curso Expresiones regulares en Python
• Tutorial de Expresiones regulares en Python