Sugiriendo nombres en tiempo real
por Pablo Fernandez de Despegar.com
En nuestro objetivo de crear comunidad con el sector privado convocamos a todos los profesionales del mundo de los datos para que cuenten los avances que están realizando en su campo de conocimiento.
En esta oportunidad Pablo Fernandez de Despegar, cuenta su desarrollo para mejorar la experiencia en la compra de pasajes aéreos, y disponibiliza el algoritmo para que cualquiera pueda reutilizarlo y hacer pruebas con la base de datos de nombres que se encuentra en Datos.gob.ar
El problema
Al momento de emitir un pasaje, las aerolíneas nos piden el nombre y apellido del pasajero. Estos datos no deben contener errores, caso contrario la aerolínea puede (y muchas veces lo hace) denegar el viaje o pedir un cambio de pasaje, con un costo que depende del valor del vuelo pero que no es nada barato.
Inicialmente creíamos que los errores al ingresar los datos se debían a que el usuario confundía nombre con apellido, pero:
- Revisando los datos vimos que esto sucedía muy pocas veces.
- Incluso cuando ocurría, las aerolíneas eran más laxas con sus reglas y dejaban abordar a los pasajeros.
El error más común era un “typo”, un error casi siempre de una letra, a la hora de ingresar el nombre o el apellido.
Si bien esta es una limitación de las aerolíneas y no de Despegar, somos conscientes de que las vacaciones representan uno de los gastos más importantes en la vida de las personas y que cualquier ayuda que podamos ofrecer al pasajero a lo largo de su experiencia es más que bienvenida.
Una solución naïve
En un principio, el problema podría resolverse de la siguiente manera:
- Tomo el nombre que ingresó el usuario y lo busco en un diccionario de nombres.
- Si existe, listo.
- Si no existe, calculo la distancia entre strings del nombre con los nombres conocidos del diccionario y sugiero el más cercano.
Esta solución funciona pero tiene algunos inconvenientes, el más importante de ellos es el tiempo de respuesta: incluso la forma más eficiente de comparación de strings demora unos cuantos microsegundos. Utilizar esto para un diccionario grande (30.000 nombres) demoraría algunos segundos. Necesitamos una solución más eficiente, para poder hacer una sugerencia en “tiempo real” como la siguiente:
Una solución más eficiente
Se puede solucionar el problema de una manera menos intuitiva pero mucho más eficiente: primero transformo mi diccionario en una estructura de clave-valor, siendo la clave el nombre y el valor la cantidad de veces que el nombre se repite.
- Tomo el nombre que ingresó el usuario y lo busco.
- Si existe, listo.
- Si no existe calculo todas las variaciones posibles de una letra y busco.
- Retorno todas las opciones que encontré, ordenadas por cantidad de ocurrencias.
Veamos un ejemplo concreto:
- El usuario ingresa “palo”, el nombre no existe en el diccionario
- Generamos todas las variaciones posibles de una letra: “apalo”, “bpalo”, “aplo”, etc.
- De todas estas “pablo”, “paolo” y “paola” existen en nuestro diccionario.
- Al ser “pablo” la más frecuente, devolvemos esa.
En un principio parece que generar todas las variaciones es costoso pero no es tan así, para un nombre corto como “pablo” las variaciones son 297:
Las variaciones incrementan con el tamaño del nombre pero incluso para 1000 variaciones, son 1000 accesos a un mapa O(1). Esta velocidad varía dependiendo del lenguaje pero en cualquier caso es una operación en el orden de los nanosegundos. Por ejemplo, en Python:
Algunos números
La performance no sólo se ve en benchmarks sintéticos (que pueden estar afectados por optimizaciones del compilador o abuso de cachés L1/L2), sino que también se observa en nuestros ambientes productivos:
El percentil 99 del servicio es ~1ms, agregando el overhead de HTTP:
Y además es muy eficiente en cuanto a memoria y uso de CPU:
Implementación utilizando datos de datos.gob.ar
Actualmente la implementación productiva utiliza un diccionario interno basado en los pasajeros históricos pero se pueden obtener resultados similares usando diccionarios de nombres de libre disponibilidad. Para nombres de personas nacidas en Argentina, la Secretaría de Gobierno de Modernización mantiene un listado de nombres disponible acá.
Para simplificar y ejemplificar cómo se pueden utilizar esos datos, armé un proyecto opensource (licencia MIT, básicamente permite todo tipo de uso) que provee el servicio en una línea de comandos. Tiene como agregado la probabilidad de ocurrencia de cada corrección, para agregar reglas del tipo “solo sugerir alternativas cuyas ocurrencias sean mayores al 5%”:
Conclusiones
Con muy poco código y con pocos recursos mostramos sugerencias que los usuarios aceptan, al momento de escribir estas líneas, unas 40 veces al día. Esos son 40 pasajeros a los que les ahorramos un proceso engorroso y costoso, precisamente en el momento que están disfrutando de sus vacaciones.
Nos parece un tradeoff más que aceptable.
***
Si querés estar más informado sobre lo que hacemos y enterarte de nuestras actividades, podés inscribirte acá.
Si te sirvió este post, hacé clic en el 👏 acá abajo, así más personas se suman a #DatosArgentina.
