ALGORTIMO PARA RESOLVER UNA SOPA DE LETRAS USANDO BACKTRACKING E INDICE INVERTIDO PARTE II

Hola a todos, que agradable es volver a compartir con ustedes otro pedazo de mi vida, gracias a Dios por esta oportunidad. Puesto que tengo una gran cantidad de información que tengo guardado en mi diario para mostrar, me ha tomado bastante tiempo poder organizar el contenido que aparece en este blog, es por esta razón, que tardo en la publicación de mis artículos, no obstante, es mi intención publicar información, pensando siempre en la relevancia y la utilidad de la misma. Siempre cargo con un cuaderno en donde hago mis anotaciones y expongo mis ideas. Cuando exponemos nuestro entendimiento por medio de palabras textuales, nuestra mente adquiere la habilidad de retenerla por más tiempo. Antes de comenzar a abarcar el tema concerniente a este artículo, también quisiera agradecer a mis amigos Jorge Tellez y Erick Estrada por su apoyo incondicional.

Bueno, ahora sí de vuelta al asunto. Para hacer un resumen de la entrega anterior, se trazó una investigación, con el fin de conocer a ciencia cierta en que consistía el problema a tratar y las posibles soluciones que se habían encontrado hasta ahora, lo que finalmente denominamos: análisis del dominio.

Volviendo a exponer la solución que vimos en la primera parte, (si no has revisado la primera parte de este tutorial, aquí les dejo un enlace para que le echen una ojeada PARTE I), en esta entrega presentamos una extensión a la solución propuesta por el backtracking, donde se aplica la técnica de índice invertido con el fin de ayudar y dar soporte a la búsqueda recursiva de las palabras claves.

Miremos ahora como aplicamos esta técnica para extender el algoritmo que vimos en la primera parte del tutorial, pero primero me gustaría explicar que es un índice invertido.

¿QUE ES UN INDICE INVERTIDO?

Un índice invertido es una estructura de datos para almacenamiento que mapea contenido tales como palabras o números con sus ubicaciones en un archivo de base de datos, en un documento o en un conjunto de documentos. Se que esta definición a lo mejor deja a algunos rascándose la cabeza, así que será mejor a través de un ejemplo, ilustrar su definición.

Digamos que tenemos los siguientes textos:
T1: "esa manzana es de color verde"
T2: “mira, esa pelota es de color azul”
T3: “eso es lo que es”

Una representación en índice invertido de lo anterior sería:

“esa”: {t1, t2}
“es”: {t1, t2, t3}
“color”: {t1, t2}
“manzana”: {t1}
“mira”: {t2}
“lo”:{t3}
etc.

La palabra que aparece en el lado izquierdo separado por los dos puntos y encerrada entre comillas, es una palabra que aparece en alguno de los 3 textos del ejemplo, llamada en el índice invertido como vocabulario. Las expresiones encerradas entre llaves que aparecen en la parte derecha, son los textos donde aparece la palabra de la izquierda, esta parte del índice invertido es llamada lista de posteo.

De lo anterior se puede concluir que:
Cada palabra que aparece en cada uno de los textos es asociada (mapeada) con el texto o los textos donde esta aparece. Así que, esta estructura tiene la obligación de permitir una búsqueda más rápida en una consulta, lo cual hace de esta técnica algo valioso para algunos de los motores de base de datos más famosos en el mundo. Creo que quedó más claro con este ejemplo que es un índice invertido.

¿Pero, por que el índice invertido servirá de apoyo o soporte al algoritmo de la sopa de letras?

Volviendo a nuestro pequeño problemita de la sopa de letras, al preguntarnos ¿por que necesito un índice invertido?, pues bien, la solución que proponíamos en la parte de nuestro análisis era inicialmente realizar una búsqueda secuencial, esto lo hacíamos Preguntando en cada letra de nuestra matriz si era igual a la primera letra de la palabra a buscar, y si era así, verificábamos en las direcciones validas donde se podía encontrar la solución, bueno eso no estaría mal, pero hablando en términos mayores, ¿que pasaría si existiese una matriz de 1000 X 1000, que da un total de 1.000.000 de letras y que al momento de buscar la solución a una palabra de 4 letras, dicha solución estuviera en la posición 999.996 y su dirección sea hacia la derecha?, ¿no se hubiese perdido bastante tiempo en comparaciones innecesarias con el resto de letras en la matriz? O en el caso en que hubiese en otra posición de la matriz, una letra parecida a la letra inicial de la palabra buscada pero no era la solución, entonces se hizo una búsqueda y verificación que no tenía que hacerse. Y esta situación solo está ocurriendo para buscar una sola palabra, ahora imagínate si tuvieses que buscar 5 o más palabras.

Lo que propongo con el uso del índice invertido, es conocer de antemano, en que posiciones están las letras candidatas a ser evaluadas y luego hacer uso del backtracking para verificar la solución a la palabra buscada.

Lo primero que haríamos para resolver la sopa de letra anterior, es crear nuestro índice invertido, tomando como vocabulario la primera letra de cada palabra a buscar y como lista de posteo las posiciones de esa letra en la matriz de letras, de esta forma tendríamos los siguientes datos:


“A”: {(0,5), (0,8), (6,6)}
“E”: {(0,0), (9,0), (9,9)}

El par ordenado que se encuentra en la lista de posteo corresponde a la expresión (fila, columna) en la matriz de letras. Así, por ejemplo, la letra “A” con la que comienza la palabra “AULA”, se encuentra en la matriz, en las posiciones (0,5) (0,8) y (6,6). La letra “E” que corresponde a la palabra “ESTUDIANTE”, se encuentra en las posiciones (0,0) (9,0) y (9,9). En el caso de la palabra “ÉXITO”, si nos damos cuenta la letra inicial es la misma que la de “ESTUDIANTE” por lo tanto ya tenemos esa referencia guardada previamente en el índice invertido.

La idea general para armar esta estructura, es:
1 - recorrer una sola vez la matriz, preguntando en cada letra si se parece a algunas de las letras con que comienzan las palabras que se quieren buscar,
2- si se parecen, preguntar si ya existe en el índice invertido. Si ya existe ir al paso 4 sino ir al paso 3.
3- almacenar la letra como vocabulario y asignar una referencia de la fila y la columna.
4 – si la posición no existe en la lista de posteo, guardar la posición de la forma (fila, columna).

Una vez tengamos el índice invertido construido, será más fácil encontrar la solución de las palabras buscada, ya que tenemos una mayor precisión en la búsqueda. Entonces, el algoritmo que teníamos anteriormente en la primera parte de nuestro tutorial, lo podemos ajustar a la siguiente forma:


1-Crear un índice invertido para la sopa de letras.

2-Tomar como entrada la primera palabra a buscar y la lista de posteo asociada a esta.

3-Se toma como pivote la letra de la matriz en la posición del par ordenado que se encuentra en la lista de posteo.

4-Seleccionar una de las direcciones: (ABAJO, ARRIBA, DERECHA, IZQUIERDA, DIAGONAL_INFERIOR_IZQUIERDA, DIAGONAL_INFERIOR_DERECHA, DIAGONAL_SUPERIOR_DERECHA, DIAGONAL_SUPERIOR_IZQUIERDA).

5-verificar la siguiente letra de la palabra buscada en una de las direcciones seleccionada.

6-Si es igual entonces: ir al paso 5.

7-No es igual entonces: ir al paso 4.

8-Si ya no hay mas letras que buscar en la palabra buscada, entonces la palabra ha sido encontrada en la dirección seleccionada y en la posición de letra de la matriz comparada. ir al paso 10.

9-Si ya no hay mas direcciones en donde buscar la solución entonces ir al paso 3.

10-Pasar a la siguiente palabra buscada.

11-No existen más palabras por buscar, entonces debemos mostrar las soluciones encontradas.


Con esto estamos listo para pasar a nuestra siguiente etapa, creo que todo luce bien y parece ser una solución bastante buena, la etapa de diseño y codificación nos presenta nuevos retos  pero ya teniendo claro lo que tenemos que hacer, nuestra implementación será muy sencilla.
En el siguiente enlace he publicado el código fuente de la solución planteada.  Utilicé Java para el desarrollo del mismo con apoyo de la técnica de programación TDD y del IDE Eclipse.

. Espero que te haya gustado este tutorial, nos veremos pronto.