Login Form

En este artículo describiremos un proyecto pequeño, más bien una prueba de concepto, de un solucionador de puzzles que funciona utilizando un árbol Trie para almacenar las palabras de un diccionario y realizar una búsqueda dirigida a través del puzzle.

La ventaja de este tipo de enfoque, es que permite realizar búsquedas eficientes de manera dirigida a través del espacio de soluciones sin necesidad de aplicar búsquedas exhaustivas que intenten abarcar todas las posibles combinaciones, las cuales podrian crecer de manera exponencial, si no es que factorial.

 A continuación daremos una breve introducción a los Árboles Trie (también conocidos como Prefix Trees) y después explicaremos de qué trata el problema seguido de un link a una pequeña implementación en Java

 

Árboles Trie

 

Un árbole Trie, es una estructura de tipo árbol que como tal, contiene un nodo raíz con una serie de nodos hijos, representando ramas, los cuales pueden tener a su vez más hijos. Los hijos que se encuentran en el último nivel del árbol se llaman hojas. A diferencia de los árboles regulares donde cada nodo contiene una llave que tiene por sí misma un valor, las llaves de cada nodo en un árbol Trie representan parte de un prefijo el cuál es compartido por todos sus hijos y por lo general cada nodo puede tener una bandera para indicar si es parte del prefijo o representa el final de una entrada completa que a su vez puede ser prefijo de una entrada más grande. 

 

En síntesis, un Trie es una estructura de datos para una recuperación eficiente de información donde el tiempo de búsqueda de una llave dada con longitud M se reduce a  O(M).

Este tipo de árbol es muy utilizado para representar entradas en diccionarios donde cada nodo contiene un arreglo de nodos hijos de longuitud igual al posible número de entradas en el alfabeto, por ejemplo; para español sería un arreglo de 27 entradas donde la primer entrada del arreglo se usaría para las palabras que comiencen con "A", la segunda con "B" y así sucesivamente hasta la "Z". Si el diccionario no tiene palabras que comiencen con "A", la primer entrada estaría vacía. 

Del mismo modo, los hijos del nodo "A", representarían la segunda letra de las posibles palabras que compartan el prefijo "A" donde la primera entrada sería utilizada para la letra "A", la segunda para la "B" y así sucesivamente hasta la última letra del alfabeto.

 La siguiente imagen ilustra el concepto usando las palabras "DIA", "DIME", "MAMA" y "MIA":

 

trie tree

 

El primer nodo es el nodo raíz el cuál solo contiene apuntadores a cada una de las entradas existentes del árbol (en este caso sólo "D" y "M") y cada rama del árbol expande y completa cada una de las entradas precedidas por el prefijo contenido en la parte superior del árbol.

 Para los interesados, se puede encontrar en línea mucho más acerca del fundamento teórico detrás de este tipo de árboles; sus orígenes, su análisis temporal-espacial y demás, sin embargo, al no ser realmente un tema que me apasione, me limitaré a describir el pequeño proyecto que implementé como prueba de concepto.

 

Solucionador de puzzles en Java


El proyecto se trata de una aplicación Java que tiene como entrada una matriz de letras y un diccionario y debe encontrar todas las palabras del diccionario que se encuentren en la matriz. Se considera que una palabra se encuentra en la matriz si se puede ligar de manera continua una seria de letras , sin repetirlas, que formen dicha palabra. Por ejemplo, dado el diccionario formado por las palabras:

  • AÑO
  • LAPIZ
  • LUIS
  • LAURA

Y teniendo como entrada la siguiente matriz:

 

trie tree matrix

 

El programa debería ser capaz de encontrar las palabras "LAPIZ" y "AÑO":

 

trie tree matrix results

 

El funcionamiento del programa es muy simple:

  • Por cada entrada en el puzzle, verifica si el nodo raíz contiene la letra, esto es, verifica si el diccionario tiene palabras que comiencen con esa letra. Si no tiene, no hay necesidad de seguir explorando combinaciones que comiencen con dicha letra por lo que continua con la siguiente sin tomar ninguna otra acción.
  • Si encuentra la entrada, busca cada una de las letras de las posiciones vecinas en los hijos de la entrada actual. Para las letras que no encuentra, detiene la búsqueda y para las que sí, lanza una búsqueda recursiva tomando ahora como entrada actual la letra recién encontrada para poder explorar sus vecinos.

El mecanismo es en extremo sencillo y lo único en lo que hay que tener cuidado es en "recordar" las ramas ya exploradas para no recorrerlas dos veces y no ciclar la aplicación. Para conseguir esto, la aplicación mantiene un Set de nodos ya visitados los cuales va actualizando y utiliza para decidir qué vecinos debería continuar explorando para cada nueva entrada encontrada. De igual manera, por su naturaleza, la aplicación puede funcionar en paralelo, por lo que se utilizaron futuros (Futures) para la implementación en paralelo. 

 El proyecto se puede encontrar y descargar de mi repositorio en Git.

For the English speakers, please find the described project under my Git repository. 

Add comment


Security code
Refresh

contacts Contactanos

 

bugs Reportar bugs

about Acerca de www.tecnohobby.net

Go to top