String matching a lo pythonico

Hace poco veía un tweet bastante interesante sobre un nuevo feature que se podría agregar a python 3.10, donde se mostraran sugerencias que aparecen al escribir mal los atributos de una librería como se aprecia en la Figura 1

Figura 1: Sugerencia de posibles nombres de atributos en python 3.10

este feature de sugerencia funciona con Levenshtein Distance este es un string metric que permite medir la distancia entre dos cadenas de caracteres, básicamente para saber que tan similares son, esto es muy usado por buscadores y como vimos también en tools de consola para ayudar a corregir errores, la formalización de lo que hace levenshtein distance se aprecia en la Figura 2

Figura 2 Formalización de Levenshtein

en este post no abordaremos a fondo en como funciona, y seremos mas utilitaristas (entender que sucede por debajo siempre es necesario dejo este post que lo explica muy bien) usando una librería que nos ayudará a resolver este problema de cadenas de string, esto me recuerda a un comic en donde se explicaba cómo volar con python ver Figura 3

Figura 3: Como volar con python Sacado de https://xkcd.com/353/

Levenshtein a muy alto nivel  básicamente funciona comparando dos cadenas de texto A y B con estas dos cadenas se cuentan las veces que debe modificarse A para quedar igual a la cadena B veamos un ejemplo con las cadenas CAT y CAP

Figura 4: Ejemplo explicativo a alto nivel de Levenshtein

en el ejemplo anterior  la distancia Levenshtein es de 1 . Es importante aclarar que en el ejemplo anterior se utilizó  la cadena A para parecerse a B para simplificar la explicación, pero puede también cambiarse la cadena B para que se parezca a A

Entendiendo un poco como funciona el algoritmo, en el mundo del desarrollo algunas veces necesitamos poder comparar cadenas de texto para saber qué tan similares son, para el ejemplo en código utilizaremos una lista de modelos de carros encontradas en github y le pasaremos nombres incompletos tratando de encontrar el que más se acerque, pasemos al código

Instalaremos la librería fuzzywuzzy utilizando poetry

poetry add fuzzywuzzy

adicionalmente para que la libreria funcione de manera más eficiente agregaremos la librería llamada python-Levenshtein

poetry add python-Levenshtein

utilizaremos la siguiente data en json

[
    {
       "Name":"chevrolet chevelle malibu",
       "Miles_per_Gallon":18,
       "Cylinders":8,
       "Displacement":307,
       "Horsepower":130,
       "Weight_in_lbs":3504,
       "Acceleration":12,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"buick skylark 320",
       "Miles_per_Gallon":15,
       "Cylinders":8,
       "Displacement":350,
       "Horsepower":165,
       "Weight_in_lbs":3693,
       "Acceleration":11.5,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"plymouth satellite",
       "Miles_per_Gallon":18,
       "Cylinders":8,
       "Displacement":318,
       "Horsepower":150,
       "Weight_in_lbs":3436,
       "Acceleration":11,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"amc rebel sst",
       "Miles_per_Gallon":16,
       "Cylinders":8,
       "Displacement":304,
       "Horsepower":150,
       "Weight_in_lbs":3433,
       "Acceleration":12,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"ford torino",
       "Miles_per_Gallon":17,
       "Cylinders":8,
       "Displacement":302,
       "Horsepower":140,
       "Weight_in_lbs":3449,
       "Acceleration":10.5,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"ford galaxie 500",
       "Miles_per_Gallon":15,
       "Cylinders":8,
       "Displacement":429,
       "Horsepower":198,
       "Weight_in_lbs":4341,
       "Acceleration":10,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"chevrolet impala",
       "Miles_per_Gallon":14,
       "Cylinders":8,
       "Displacement":454,
       "Horsepower":220,
       "Weight_in_lbs":4354,
       "Acceleration":9,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"plymouth fury iii",
       "Miles_per_Gallon":14,
       "Cylinders":8,
       "Displacement":440,
       "Horsepower":215,
       "Weight_in_lbs":4312,
       "Acceleration":8.5,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"pontiac catalina",
       "Miles_per_Gallon":14,
       "Cylinders":8,
       "Displacement":455,
       "Horsepower":225,
       "Weight_in_lbs":4425,
       "Acceleration":10,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"amc ambassador dpl",
       "Miles_per_Gallon":15,
       "Cylinders":8,
       "Displacement":390,
       "Horsepower":190,
       "Weight_in_lbs":3850,
       "Acceleration":8.5,
       "Year":"1970-01-01",
       "Origin":"USA"
    },
    {
       "Name":"citroen ds-21 pallas",
       "Miles_per_Gallon":null,
       "Cylinders":4,
       "Displacement":133,
       "Horsepower":115,
       "Weight_in_lbs":3090,
       "Acceleration":17.5,
       "Year":"1970-01-01",
       "Origin":"Europe"
    },
    {
       "Name":"chevrolet chevelle concours (sw)",
       "Miles_per_Gallon":null,
       "Cylinders":8,
       "Displacement":350,
       "Horsepower":165,
       "Weight_in_lbs":4142,
       "Acceleration":11.5,
       "Year":"1970-01-01",
       "Origin":"USA"
    }
]
Modelos de carros Sacado de https://github.com/vega/vega/blob/master/docs/data/cars.json
import json
from fuzzywuzzy import process


def get_car_models_name():
    with open("data.json", encoding="utf-8", mode="r") as data:
        car_models = json.load(data)
    car_name_models = [car_model["Name"] for car_model in car_models]
    return car_name_models


def search_model_car(model_name: str):
    car_models_name = get_car_models_name()
    return process.extractOne(model_name, car_models_name)


print(search_model_car("CoNcurOs"))

Ejecutamos el código

poetry run python main.py

y el resultado es una tupla que contiene la cadena encontrada y un porcentaje de similitud

('chevrolet chevelle concours (sw)', 79)

En el ejemplo del código anterior utilizamos la librería fuzzywuzzy esta utiliza el algoritmo de Levenshtein y basado en las distancia obtenidas otorga unos porcentajes y a partir de ello devuelve el que más porcentaje tiene de similitud con la cadena a comparar dado que estamos solicitando a la librería que devuelva uno, sin embargo se podría también solicitar que a cada cadena le ponga un porcentaje como se muestra a continuación

import json
from fuzzywuzzy import process
from fuzzywuzzy import fuzz


def get_car_models_name():
    with open("data.json", encoding="utf-8", mode="r") as data:
        car_models = json.load(data)
    car_name_models = [car_model["Name"] for car_model in car_models]
    return car_name_models


def search_model_car(model_name: str):
    car_models_name = get_car_models_name()
    return process.extract(model_name, car_models_name, limit=3, scorer=fuzz.ratio)


print(search_model_car("CoNcurOs"))

ejecutamos el código

poetry run python main.py

y obtenemos  el siguiente resultado

[('chevrolet chevelle concours (sw)', 79), ('chevrolet chevelle malibu', 34), ('plymouth satellite', 34)]

obtenemos una lista de tuplas con el nombre de la cadena y porcentaje de similitud, esto porque en el método search_model_car se modifico la siguiente porcion de codigo

return process.extract(model_name, car_models_name, limit=3, scorer=fuzz.ratio)

aquí ahora se le dice que devuelva una lista de las 3 primeras que más porcentaje de similitud tengan, adicionalmente como vimos se agregó un parámetro score, esto es porque la librería permite utilizar scores que son funciones que facilitan calcular la similitud de las cadenas pero de diferentes formas como veremos a continuación

  • fuzz.ratio: es el método por defecto aquí aplica el algoritmo de levenshtein tal cual se explico al principio del post
  • fuzz.partial_ratio: esta función utiliza la similitud de cadenas pero de forma parcial, utilizando el tamaño de la cadena A para buscar coincidencias comparando con subcadenas de B del tamaño de A y obtener un mejor resultado observemolo en código
from fuzzywuzzy import fuzz

def partial():
    return fuzz.partial_ratio("Mother","My mother is beautiful")

def default():
    return fuzz.ratio("Mother","My mother is beautiful")


print(f"Partial score {partial()}")
print(f"Default score {default()}")

Ejecutando el código tenemos las siguientes salidas

Partial score 83
Default score 43

como podemos observar en el Partial score al comparar subcadenas la score es muchisimo mas alto que una comparación por defecto, por ende esta función es buena opción si se sabe de antemano que la cadena A podría ser una subcadena de B

  • fuzz.token_sort_ratio: esta función especialmente se encarga de ordenar primero los tokens de las cadenas intentando obtener un mejor resultado al aplicar el algoritmo, veamos un ejemplo
from fuzzywuzzy import fuzz

def partial(data_to_search:str,data:str):
    return fuzz.partial_ratio(data_to_search,data)

def default(data_to_search:str,data:str):
    return fuzz.ratio(data_to_search,data)

def order(data_to_search:str,data:str):
    return fuzz.token_sort_ratio(data_to_search,data)


print(f"Partial score {partial('Lakers vs Golden state warriors', 'Golden state warriors vs Lakers')}")
print(f"Default score {default('Lakers vs Golden state warriors', 'Golden state warriors vs Lakers')}")
print(f"Token sort score {order('Lakers vs Golden state warriors', 'Golden state warriors vs Lakers')}")

Al ejecutar  el código obtenemos el siguiente resultado

Partial score 68
Default score 68
Token sort score 100

como podemos observar los primeros métodos no obtienen un buen resultado en comparación con el 100% del Token sort, ya que ordenó los tokens de las cadenas para obtener este resultado

  • fuzz.token_set_ratio esta función utiliza las subcadenas de A para hacer intersección contra  las subcadenas de B y retornando la que obtenga  el mayor porcentaje de similitud, veamos un ejemplo
from fuzzywuzzy import fuzz

def partial(data_to_search:str,data:str):
    return fuzz.partial_ratio(data_to_search,data)

def default(data_to_search:str,data:str):
    return fuzz.ratio(data_to_search,data)

def order(data_to_search:str,data:str):
    return fuzz.token_sort_ratio(data_to_search,data)

def set_ratio(data_to_search:str,data:str):
    return fuzz.token_set_ratio(data_to_search,data)

print(f"Partial score {partial('mariners vs angels', 'los angeles angels of anaheim at seattle mariners')}")
print(f"Default score {default('mariners vs angels', 'los angeles angels of anaheim at seattle mariners')}")
print(f"Token sort score {order('mariners vs angels', 'los angeles angels of anaheim at seattle mariners')}")
print(f"Token set ratio score {set_ratio('mariners vs angels', 'los angeles angels of anaheim at seattle mariners')}")

y de salida en consola obtenemos

Partial score 61
Default score 36
Token sort score 51
Token set ratio score 91

vemos como el Token set ratio obtiene un mayor porcentaje debido a su método de la intersección de cadenas

Conclusión

Esta librería es muy útil a la hora de trabajar con comparaciones con cadenas, a veces incluso los query de los motores de bases de datos no son suficientes debido a que las cadenas varían demasiado con lo que se tiene guardado, por tanto esta es una buena opción para enfrentarse a este tipo de situaciones