Hace unos días, encontré una web, que proponía hacer un algoritmo de autcompletado.
Se puede plantear este challenge, como la búsqueda en un listado de palabras de una longitud variable L(i) y un prefijo X. La búsqueda sería recorrer todo el listado y comprobar si las palabras empiezan por el prefijo que le hemos pasado o no.
Si has llegado hasta aquí, probablemente te interese, la explicación de como implementé esta parte y si eres como yo, será mas fácil viendo el código. Por eso te pongo al principio el enlace al repo dónde tengo mi implementación
Implementación
GITHUB Comentando el algoritmo
Cuando leía sobre el planteamiento del problema, lo primero que piensas es en recorrer una lista y cachear los resultados para volver a filtrarlos. Un mecanismo chulo y rápido que te vaya devolviendo según vayas «profundizando», en la palabra.
Pero si piensas en las letras de cada palabra como nodos y en una palabra como un conjunto de nodos, puedes ver tranquilamente un árbol.
Si cada nodo esta constituido por la letra (byte) y un map[byte][node], tendremos las bases establecidas para nuestro algoritmo.
A parte de eso, en nuestro árbol, temen que tener si el nodo acumulado es una palabra completa o no, de esta manera, palabras que tienen sentido incluidas en otras aparecerán en el listado: pájara, pajarera
Complejidad compartida
Cuando expuse al principio del post, el primer enfoque es el que guió los pasos, hasta llegar aquí. Obviamente yo no he inventado nada, pero de leer y leer, al final el sistema 2 (cómo diría o como dice Daniel Kahneman, en su ensayo: pensar rápido, pensar despacio), hace su trabajo.
Qué quiero decir, que compartimos la complejidad en dos fases, fase de carga y fase de trabajo. La fase de carga, sería montar nuestro resource (árbol), con un ficho o base de datos. La fase de trabajo, sería la que devuelve el nodo y devuelve el acumulado de nodos.
En resumen, nuestro cache es el preload d ella información en nuestra estructura, para que luego el usuario o el algoritmo sea mas rápido.
Cargando los datos
Aun estoy adaptándomela a golang, quería hacer un simple bucle para que fuera todo más claro, pero mis limitaciones actuales, e optado por algo que no puede adaptar los lenguajes, las iteraciones recursivas.
Iteramos la palabra que queremos añadir en nuestro árbol, byte a byte, el cual es el nodo en si y decidimos si es una hoja o no cuando llegamos al final de la longitud .
También podéis ver que hice un método, el cual sino lo encuentra los añade cuando lo obtiene. Por otro lado hice el algoritmo «case insensitive», hacer lo contrario sería muy fácil.
Obtención del prefijo y construcción de resultados
Cómo siempre tengo presente el desarrollo de video juegos, lo he llamado engine, pero es un prank.
Aquí podemos ver el método FindByPrefix, que pasándole un prefijo obtiene el nodo que tiene el acumulado es el propio prefijo.
Si estamos buscando, «pe»;
Luego de obtener el nodo, se lo pasamos al método build, el cual obtiene todos los acumulados y cuando son hojas los añade para ser devueltos y acumulados en el array de resultados.
Lo he picado, tal cual se me ha ocurrido, cómo lo veis, os gusta ? algún error ?.