C++ / La estructura de un engine de busqueda

Bienvenidos sean a este post, hoy hablaremos de la teoria sobre este tema.

Cuando abrimos un navegador e ingresamos a un buscador, tipeamos una palabra o frase en su interfaz y esta nos devuelve una lista con todas las coinicidencias posibles en cuestion de segundos. Pero como puede lograr esto? Vamos a analizar la teoria sobre esto.

El usuario ingresa las palabras para la busqueda en la interfaz del buscador. Este explora todos los documentos, los filtra, los ordena por relevancia y responde lo mas rapido que se puede Tratemos de crear un enfoque aproximado de como seria buscar a «hola, mundo!» entre millones de documentos (en realidad paginas web pero las denominaremos asi por comodidad). Escaneando cada documento por la frase tomara muchisimo tiempo, si consideramos que cada documento posee 500 palabras y esto llevara mucho tiempo analizar cada uno buscando las palabras o combinaciones de estas. Para evitar esto, el proceso de busqueda incluye la construccion de un indice de cada ocurrencia de palabras en los documentos y almacena la informacion en una base de datos, habitualmente se lo denomina como indexacion de documentos, y esto permite que al momento del usuario tipear su busqueda, el engine busca esto en la base de datos y devuelve los links que satisfacen a la solicitud.

Otra caracteristica interesante es la verificacion de lo que ingresa el usuario para buscar. Es muy usual, a todos nos pasa, que cometamos errores de tipografia en el texto. Si bien, el corregir estos errores automaticamente seria un gran agregado, si le adicionammos la posibilidad de autocompletar una frase tambien lo seria. Como ocurre en muchos buscadores, a medida que vamos tipeando las palabras se nos van sugiriendo posibilidades. Esto habitualmente se logra llevando un seguimiento de lo que ingresa el usuario, como puede ser el historial de sus busquedas, detalles del dispositivo que mas utilizamos, etc. Tomemos como ejemplo la busqueda de un programa, este le entregara como primera opcion la descarga de ese programa su S.O.. Si este fuera un linux, puede llevarnos a una pagina que explica todos los pasos para compilarlo e instalarlo.

Ahora nos surge otro tema como son los nuevos documentos que se agregan en internet todos los dias. Un proceso puede realizar el trabajo de trasfondo de analizar continuamente la web para encontrar nuevo contenido. Habitualmente se lo denomina como crawler (rastreador), para rastrear la web e indexar los documentos. Este se encarga de descargar los documentos para analizarlos y construir su indice. Otra tarea que se realizan son tambien la actualizacion y/o remocion de los documentos ya indexados. A su vez, deberia existir otro proceso que se encargue exclusivamente de tener actualizados los documentos ya indexados regularmente. Por esta razon, usualmente se pueden usar los terminos de araña para las tareas de rastreo en la web para el analisis de documentos. Esto tambien se puede aplicar en muchos programas, veamos el siguiente ejemplo practico:

using palabras = std::vector<std::string>;
words lista = get_lista_palabras();

auto buscar_en_palabras(const std::string& termino)
{
  return std::find(lista.begin(), lista.end(), termino);
}

Este es un codigo simple para buscar y encontrar palabras en un array. Si bien, esto es un ejemplo simple de un engine de busqueda. Este puede ser util pero el verdadero desafio es hacerlo escalable. Porque no es una buena idea completar las solicitudes del usuario mediante un array de cosas. En su lugar, debemos apuntar a implemetar un engine de busqueda escalable, como mencionamos antes, que sea capaz de bucar en millones y millones de documentos.. Esto nos llevara a pensar y diseñar un monton porque hasta el mas minimo detalle importa, desde la correcta seleccion de estructura de datos hasta algoritmos eficientes para procesarlos. Veamos algunos de los componentes de un engine de busqueda:

• Interface apropiada para el usuario
• Manejar errores tipograficos en queries
• Rastreando websites

Nota:
A medida que suba los posts, los ire vinculando con esta lista.

En resumen, hoy hemos visto una estructura basica de un engine de busqueda, teoria de algunos conceptos basicos, asi como otros temas a tener en cuenta, y por ultimo algunos temas de los cuales se compone y veremos mas adelante. Espero les haya sido 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.