tu no Una tabla de base de datos relacional no es una estructura de datos adecuada para resolver este problema con la eficacia necesaria.
Lo que haces en su lugar es construir un trie estructura de datos fuera del diccionario (o, si eres muy aficionado, construyes un dawg -- un gráfico de palabras acíclicas dirigidas -- que es una especie de trie comprimido.)
Una vez que tiene un trie/dawg, se vuelve muy económico probar todos palabra en el diccionario contra un estante dado, porque puede "cortar" ramas enormes enteras del diccionario que el estante no puede igualar.
Veamos un pequeño ejemplo. Supongamos que tiene el diccionario "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" A partir de ahí construye este trie:(Los nodos con $ son los que están marcados como "la palabra puede terminar aquí" .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
y tienes el estante "OPS", ¿qué haces?
Primero dices "¿puedo bajar por la rama O?" Sí tu puedes. Así que ahora el problema es hacer coincidir "PS" con la rama O. ¿Puedes bajar por la rama secundaria P? Sí. ¿Tiene un marcador de fin de palabra? Sí, entonces OP es una coincidencia. Ahora el problema es hacer coincidir "S" con la rama OP. ¿Puedes bajar por la rama T? No. ¿Puedes bajar por el ramal S? Sí. Ahora tiene el estante vacío y debe compararlo con la rama OPS. ¿Tiene un marcador de fin de palabra? ¡Sí! Así que los partidos de OPS también. Ahora retroceda hasta la raíz.
¿Puedes bajar por la rama P? Sí. Ahora el problema es hacer coincidir el sistema operativo con la rama P. Vaya a la sucursal de PO y haga coincidir S, eso falla. Vuelve a la raíz.
Y de nuevo, ya ves cómo va esto. Eventualmente bajamos por la rama SOP y encontramos un final de palabra en SOP, por lo que "SOP" coincide con este estante. No bajamos por la sucursal ST porque no tenemos una T.
Probamos todas las palabras posibles del diccionario y descubrimos que OP, OPS y SOP coinciden. Pero nunca tuvimos que investigar OPTS, POTS, STOP o STOPS porque no teníamos una T.
¿Ves cómo esta estructura de datos la hace muy eficiente? Una vez que haya determinado que no tiene las letras en el estante para hacer el comienzo de una palabra, no tienes que investigar ninguna palabras del diccionario que comienzan con ese comienzo. Si tiene PO pero no T, no tiene que investigar POTSHERD o PATATA o POTASH o POTLATCH o POTABLE; todas esas búsquedas costosas e infructuosas desaparecen muy rápido.
Adaptar el sistema para manejar mosaicos "salvajes" es bastante sencillo; si tiene OPS?, simplemente ejecute el algoritmo de búsqueda 26 veces, en OPSA, OPSB, OPSC... Debería ser lo suficientemente rápido como para que hacerlo 26 veces sea barato (o hacerlo 26 x 26 veces si tiene dos espacios en blanco. )
Este es el algoritmo básico que utilizan los programas profesionales de Scrabble AI, aunque, por supuesto, también tienen que lidiar con cosas como la posición del tablero, la gestión de estantes, etc., que complican un poco los algoritmos. Esta versión simple del algoritmo será lo suficientemente rápida como para generar todas las palabras posibles en un estante.
No olvide que, por supuesto, solo tiene que calcular el trie/dawg una vez si el diccionario no cambia con el tiempo. Puede llevar mucho tiempo crear el trie a partir del diccionario, por lo que es posible que desee hacerlo una vez y luego descubra alguna forma de almacenar el trie en el disco en una forma que sea adecuada para reconstruirlo rápidamente desde el disco.
Puede optimizar el uso de la memoria creando un DAWG a partir del trie. Fíjate cómo hay mucha repetición porque en inglés, muchas palabras end lo mismo, como muchas palabras comienzan lo mismo. El trie hace un gran trabajo al compartir nodos al principio, pero un pésimo trabajo al compartirlos al final. Puede notar, por ejemplo, que el patrón "S$ sin hijos" es extremadamente común y convertir el trie en:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Guardando un montón de nodos. Y luego puede notar que dos palabras ahora terminan en O-P$-S$, y dos palabras terminan en T$-S$, por lo que puede comprimirlo aún más a:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
Y ahora tenemos el DAWG mínimo para este diccionario.
Lectura adicional:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
