Vous ne le faites pas. Une table de base de données relationnelle n'est pas une structure de données appropriée pour résoudre ce problème aussi efficacement que nécessaire.
Ce que vous faites à la place, c'est que vous construisez un trie structure de données hors du dictionnaire (ou, si vous êtes vraiment passionné, vous construisez un dawg -- un graphe de mots acyclique dirigé -- qui est une sorte de trie compressé.)
Une fois que vous avez un trie/dawg, il devient très peu coûteux de tester tous mot du dictionnaire par rapport à un rack donné, car vous pouvez "élaguer" des branches entières du dictionnaire auxquelles le rack ne peut pas correspondre.
Regardons un petit exemple. Supposons que vous ayez le dictionnaire "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS". .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
et vous avez le rack "OPS" -- que faites-vous ?
D'abord, vous dites "puis-je descendre la branche O ?" Oui, vous pouvez. Alors maintenant, le problème est de faire correspondre "PS" avec la branche O. Pouvez-vous descendre la sous-branche P ? Oui. Y a-t-il un marqueur de fin de mot ? Oui, donc OP est un match. Maintenant, le problème correspond à "S" avec la branche OP. Pouvez-vous descendre la branche T? Non. Pouvez-vous descendre la branche S ? Oui. Vous avez maintenant le rack vide et vous devez le faire correspondre à la branche OPS. Y a-t-il un marqueur de fin de mot ? Oui! Donc OPS correspond aussi. Revenez maintenant à la racine.
Pouvez-vous descendre la branche P ? Oui. Maintenant, le problème est de faire correspondre le système d'exploitation à la branche P. Descendez la branche PO et faites correspondre S - cela échoue. Revenir à la racine.
Et encore une fois, vous voyez comment cela se passe. Finalement, nous descendons dans la branche SOP et trouvons une fin de mot sur SOP, donc "SOP" correspond à ce rack. On ne descend pas la branche ST car on n'a pas de T.
Nous avons essayé tous les mots possibles du dictionnaire et avons découvert que OP, OPS et SOP correspondent tous. Mais nous n'avons jamais eu à enquêter sur OPTS, POTS, STOP ou STOPS parce que nous n'avions pas de T.
Vous voyez comment cette structure de données le rend très efficace ? Une fois que vous avez déterminé que vous n'avez pas les lettres sur le support pour faire le début d'un mot, vous n'avez pas à enquêter sur tout mots du dictionnaire qui commencent par ce début. Si vous avez du PO mais pas de T, vous n'avez pas besoin d'enquêter sur le TERSON DE POTS ou la POMME DE TERRE ou la POTASSE ou le POTLATCH ou le POTABLE ; toutes ces recherches coûteuses et infructueuses disparaissent très rapidement.
Adapter le système pour traiter les tuiles "sauvages" est assez simple; si vous avez OPS ?, exécutez simplement l'algorithme de recherche 26 fois, sur OPSA, OPSB, OPSC... Cela devrait être assez rapide pour que le faire 26 fois soit bon marché (ou le faire 26 x 26 fois si vous avez deux blancs. )
Il s'agit de l'algorithme de base utilisé par les programmes professionnels de Scrabble AI, bien qu'ils doivent bien sûr également gérer des éléments tels que la position de la carte, la gestion du rack, etc., ce qui complique quelque peu les algorithmes. Cette version simple de l'algorithme sera suffisamment rapide pour générer tous les mots possibles sur un rack.
N'oubliez pas que bien sûr vous n'avez qu'à calculer le trie/dawg une fois si le dictionnaire ne change pas avec le temps. Cela peut prendre du temps de construire le trie à partir du dictionnaire, donc vous voudrez peut-être le faire une fois puis trouver un moyen de stocker le trie sur le disque sous une forme permettant de le reconstruire rapidement à partir du disque.
Vous pouvez optimiser l'utilisation de la mémoire en créant un DAWG à partir du trie. Remarquez comme il y a beaucoup de répétitions car en anglais, beaucoup de mots end le même, tout comme beaucoup de mots commencent le même. Le trie fait un excellent travail de partage des nœuds au début mais un travail moche de les partager à la fin. Vous pouvez remarquer par exemple que le modèle "S$ sans enfant" est extrêmement courant, et transformer le trie en :
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Enregistrer tout un tas de nœuds. Et puis vous remarquerez peut-être que deux mots se terminent maintenant par O-P$-S$, et deux mots se terminent par T$-S$, vous pouvez donc le compresser davantage :
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
Et maintenant nous avons le DAWG minimal pour ce dictionnaire.
Lectures complémentaires :
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
