Buscar palabras completas usando un hashmap es sencillo. Pero cuando has de buscar por parte de la palabra la cosa se complica. ¿Como buscar todas las palabras que empiezan o terminan por una cadena dada?.

La solución es usar un trie. Un tipo de estructura de datos en la que básicamente creamos un árbol donde cada letra es un nodo. Por ejemplo el trie formado por las palabras: cardo, cardos y carne sería:

Las terminaciones «end» indican que ahí termina una palabra. Si se toma desde esa terminación y se asciende por los padres se forma la palabra almacenada. Por ejemplo: end2 O D R A C representa la palabra CARDO.

Para buscar las palabras que empiezan por un conjunto de letras se recorre en el trie ese conjunto de letras y a partir del último nodo del conjunto se recorren todas las ramas reconstruyendo las palabras cuando encuentra un indicador de fin de palabra.

Por ejemplo si buscamos palabras que empiezan por «card«:

• CARD O S end
• CARD O end

Para buscar palabras que terminan el método es el mismo solo que hemos de meter la palabra al revés en el trie. En lugar de guardar cardo guardamos odrac. Al recuperarla del trie le volvemos a dar la vuelta y listo.

Al buscar es necesario invertir la cadena de búsqueda. Es decir si se buscan palabras terminadas en do hay que buscar la cadena od

Hasta aquí la teoría, ahora veamos la diferencia con la realidad. El principal problema son las tildes y las diéresis. Cuando buscas bru esperás que aparezca tanto bruja como brújula pero el trie no distingue entre u/ú ¿Cómo solucionamos ésto? Haciendo un proceso de limpieza de las palabras al introducirlas en el trie.

Para que la palabra correcta no se pierda se almacenará junto con el indicador de palabra completa. En nuestro ejemplo:

• End1 – Cardos
• End2 – Cardo
• End3 – Carne

Con esto ganamos velocidad ya que nos ahorramos el proceso de reconstruir la palabra, a cambio ocupa más espacio en memoria.

Hay que tener en cuenta que en una misma rama puede haber varias palabras como medico y medicó, por lo que hay que almacenar un listado de palabras.