Curso
Introduction to Python
4 h
6.3M
Aprende Python desde cero
Domina Python para la ciencia de datos y adquiere habilidades muy demandadas.
Ediciones y distancia de edición
El algoritmo de emparejamiento 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 "ediciones" 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:
| Operación de edición | Descripción | Ejemplo |
|---|---|---|
| Inserta | Añade una letra | "Londn" -> "Londres" |
| Borra | Eliminar una letra | "Londoon" -> "London" |
| Interruptor | Intercambia dos letras adyacentes | "Lnodon" -> "Londres" |
| Sustituye | Cambiar una letra por otra | "Londin" -> "Londres" |
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 
1ab 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 proporciona 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 thefuzzNota: Esta biblioteca viene preinstalada en el libro de trabajo DataLab.
Ahora, veamos algunas de las cosas que podemos hacer con el zumbido.
Sigue el código de este cuaderno DataLab.
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 "relación de ordenación de fichas".
Ratio de clasificación de fichas
De acuerdo, queremos ignorar el orden de las palabras en las cadenas, pero determinar lo parecidas que son: la ordenación por fichas te ayuda a hacer exactamente eso. A la clasificación por fichas 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 fichas 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 nombre y nombre_completo. ¿Qué crees que ocurrirá si utilizamos ahora la clasificación por fichas?
# 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 fichas sólo tiene en cuenta el orden. Si hay palabras que no son similares en las cadenas, afectará negativamente a la proporción de similitud, como hemos visto antes.
Pero hay una solución.
Proporción del conjunto de fichas
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 hemos definido.
Técnicas de concordancia de cadenas difusas con TheFuzz compapred
En la tabla siguiente, puedes ver una comparación rápida de los distintos tipos de técnicas disponibles en TheFuzz:
| Técnica | Descripción | Ejemplo de código |
|---|---|---|
| Relación simple | Calcula la similitud teniendo en cuenta el orden de las cadenas de entrada. | fuzz.ratio(name, full_name) |
| Relación parcial | Encuentra la similitud parcial comparando la cadena más corta con las subcadenas. | fuzz.partial_ratio(name, full_name) |
| Ratio de clasificación de fichas | Ignora el orden de las palabras en las cadenas. | fuzz.token_sort_ratio(full_name_reordered, full_name) |
| Proporción del conjunto de fichas | Elimina los tokens comunes antes de calcular la similitud. | fuzz.token_set_ratio(name, full_name) |
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).
Comparación de cadenas difusas con pandas DataFrames
Si necesitas un resumen rápido de las técnicas mencionadas anteriormente, puedes encontrarlas en la tabla siguiente:
| Paso | Descripción | Fragmento de código |
|---|---|---|
| Crear marcos de datos | Define datos con posibles faltas de ortografía. | existing_data = pd.DataFrame(dict_one), exported_data = pd.DataFrame(dict_two) |
| Intento de Fusión con Errores | La fusión inicial falla debido a cadenas no coincidentes. | data = pd.merge(existing_data, exported_data, on="country", how="left") |
| Corrige las faltas de ortografía | Utiliza la concordancia difusa para corregir nombres de países mal escritos. | exported_data["country"] = exported_data["country"].apply(lambda x: process.extractOne(x, existing_data["country"], scorer=fuzz.partial_ratio)[0]) |
| Fusión exitosa | Fusiona los marcos de datos tras corregir los errores ortográficos mediante la concordancia difusa de cadenas. | data = pd.merge(existing_data, exported_data, on="country", how="left") |
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
¿Cómo gestiona la concordancia difusa de cadenas la distinción entre mayúsculas y minúsculas?
¿Puedo utilizar la biblioteca TheFuzz con otras estructuras de datos además de cadenas?
¿Cómo gestiono las correspondencias difusas con grandes conjuntos de datos para optimizar el rendimiento?
¿Cuáles son algunas aplicaciones comunes de la concordancia difusa de cadenas más allá de los motores de búsqueda?
¿En qué se diferencia la distancia Levenshtein de otros algoritmos de distancia de edición?
Temas
