C++ / Manejar errores tipograficos en queries

Bienvenidos sean a este post, hoy veremos un resumen teorico de como manejar los errores tipograficos.

Algo que sucede muy habitualmente son los errores tipograficos al momento de hacer la busqueda. Aunque no lo parezca, este tipo de error puede dar como resultado respuestas inadecuadas. Tomemos el caso de busqueda del post anterior y lo hacemos de la siguiente manera:

Observen como el buscador no corrige lo que escribimos sino que nos muestra una opcion sugiriendo lo que quisimos buscar. Igualmente, ofrece buscar lo que escribimos porque no deja de ser una sugerencia pero en realidad necesitamos saber sobre lo que escribimos. Por eso, al momento de desarrollar un engine de busqueda desde el inicio debemos solucionar como manejar las solicitudes del usuario. Como mencionamos en el post anterior, lo primero que debemos hacer es proveer una interfaz adecuada para que puedan ingresar las solicitudes los usuarios. Como mencionamos recien, no solamente debemos proveer lo solicitado sino tambien una mejor experiencia y entre ellas son las posibles sugerencias. Ya sea, para corregir lo que escribimos medainte sugerencias o ir mostrando resultados a medida que lo vamos escribiendo.

Con esto comentado, lo siguiente es el chequeo de los errores tipograficos y/o las palabras incompletas, y como se imaginaran no es una tarea nada facil. Si retenemos todas las palabras en una lista y las vamos comparando con un diccionario nos va a llevar muchisimo tiempo. Como podran deducir, el uso de estructura de datos especificos y algoritmos es un deber. Tomemos como ejemplo, encontrar la distancia Levenshtein entre la distintas palabras puede ser algo muy util para chequear por errores tipograficos en las solicitudes del usuario.

La distancia Levenshtein es el numero de caracteres que deben ser agregados, removidos o substituidos en una palabra para ser igual a otro. Tomemos el caso de la imagen, la diferencia entre worl y world es 1 porque remover la d de una de las dos palabras o agregarla en la faltante pero en ambos casos hara que las dos sean iguales. Analicemos lo siguiente, la distancia Levenshtein entre coding y sitting es 4 porque son la cantidad de pasos que necesitamos realizar para convertirla en una o en otra. Veamos como puede ser esto:

• coding -> codting (agregado de la t en el medio)
• codting -> cotting (sustituicion de la t para la d)
• cotting -> citting (sustitucion de la i para la o)
• citting -> sitting (sustitucion de la s para la c)

Esto dara como resultado la conversion de la palabra coding en sitting. Para entender esto, vamos a analizar la palabra worl del ejemplo. Como mencionamos para analizar cada palabra utiliza una estructura de datos donde descompone a cada caracter como un nodo de la misma. La primera es w, y al ser la primera estara bien en todo sentido, lo mismo ocurre con la o y con la r pero luego de esta tenemos un tema. Como existe la palabra word, este asume que el siguiente nodo sera la letra pero no pasamos este caracter sino que al caracter l. Como este nodo no tiene uno que siga, asume que la palabra es world y se asocia con este nodo. Dando como resultado la sugerencia de la palabra world.

Aqui entramos en otro inconveniente porque para dar mejores sugerencias para corregir errores tipograficos deberiamos tener un diccionario completo de palabras del lenguaje del usuario. Y con los tiempos actuales, no solamente en ingles sino que para cada lenguaje registrado. Si bien almacenar las palabras de un diccionario no es una tarea dificil, ardua si pero no dificil. Sin embargo, el recolectar todos los documentos (paginas web) y almacenarlos para ejecutar una busqueda rapida si es una tarea dificil. La herramienta, programa, o modulo del engine de busqueda que recolecta y analiza las paginas web para crear la base de datos del engine se lo denomida como rastreador (crawler) pero sobre esto hablaremos en el proximo post.

En resumen, hoy hemos visto como manejar errores tipograficos en forma teorica, vimos como es una posibilidad y a su vez como permite mejorar la experiencia de los usuarios mediante otras posibilidades. Espero les haya resultado de utilidad sigueme en tumblr, Twitter o Facebook para recibir una notificacion cada vez que subo un nuevo post en este blog, nos vemos en el proximo post.