Tu no. Una tabella di database relazionale non è una struttura di dati adatta per risolvere questo problema in modo efficiente quanto necessario.
Quello che fai invece è creare un trie struttura dei dati fuori dal dizionario (o, se sei davvero un fanatico, costruisci un dawg -- un grafico di parole aciclico diretto -- che è una sorta di trie compresso.)
Una volta che hai un tentativo/dawg diventa molto poco costoso testare ogni parola nel dizionario rispetto a un determinato rack, perché puoi "potare" interi enormi rami del dizionario che il rack non può corrispondere.
Diamo un'occhiata a un piccolo esempio. Supponiamo di avere il dizionario "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" Da questo costruisci questo trie:(I nodi con $ sono quelli contrassegnati come "la parola può finire qui" .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
e hai il rack "OPS" -- cosa fai?
Per prima cosa dici "posso andare giù per il ramo O?" Si, puoi. Quindi ora il problema è abbinare "PS" al ramo O. Puoi scendere nel sottoramo P? Sì. Ha un marcatore di fine parola? Sì, quindi OP è una corrispondenza. Ora il problema è la corrispondenza di "S" con il ramo OP. Puoi scendere lungo il ramo a T? No. Puoi scendere il ramo S? Sì. Ora hai il rack vuoto e devi abbinarlo al ramo OPS. Ha un marcatore di fine parola? Sì! Quindi anche OPS corrisponde. Ora torna alla radice.
Puoi scendere lungo il ramo P? Sì. Ora il problema è abbinare il sistema operativo al ramo P. Scendi nel ramo PO e abbina S - fallisce. Torna alla radice.
E ancora, vedi come va. Alla fine scendiamo nel ramo SOP e troviamo un fine parola su SOP, quindi "SOP" corrisponde a questo rack. Non scendiamo dal ramo ST perché non abbiamo una T.
Abbiamo provato ogni possibile parola nel dizionario e abbiamo scoperto che OP, OPS e SOP corrispondono. Ma non abbiamo mai dovuto indagare su OPTS, POTS, STOP o STOPS perché non avevamo un T.
Vedi come questa struttura di dati lo rende molto efficiente? Una volta che hai determinato che non hai le lettere sul rack per fare l'inizio in una parola, non devi indagare nessuno parole del dizionario che iniziano con quell'inizio. Se hai PO ma non T, non devi investigare POTSHERD o POTATO o POTASH o POTLATCH o POTABLE; tutte quelle ricerche costose e infruttuose scompaiono molto rapidamente.
Adattare il sistema per gestire le tessere "selvagge" è piuttosto semplice; se hai OPS?, esegui semplicemente l'algoritmo di ricerca 26 volte, su OPSA, OPSB, OPSC... Dovrebbe essere abbastanza veloce che farlo 26 volte sia economico (o farlo 26 x 26 volte se hai due spazi vuoti. )
Questo è l'algoritmo di base utilizzato dai programmi Scrabble AI professionali, anche se ovviamente devono anche occuparsi di cose come la posizione della scheda, la gestione del rack e così via, che complicano un po' gli algoritmi. Questa semplice versione dell'algoritmo sarà abbastanza veloce da generare tutte le parole possibili su un rack.
Non dimenticare che ovviamente devi calcolare il trie/dawg una volta se il dizionario non cambia nel tempo. Può richiedere molto tempo costruire il trie dal dizionario, quindi potresti volerlo fare una volta e quindi trovare un modo per archiviare la prova su disco in un modulo che sia suscettibile di ricostruirla rapidamente dal disco.
È possibile ottimizzare l'utilizzo della memoria costruendo un DAWG dal trie. Nota come ci siano molte ripetizioni perché in inglese molte parole end lo stesso, proprio come molte parole iniziano lo stesso. Il trie fa un ottimo lavoro nel condividere i nodi all'inizio, ma un pessimo lavoro nel condividerli alla fine. Puoi notare, ad esempio, che il modello "S$ senza figli" è estremamente comune e trasformare il trie in:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Salvataggio di un intero mucchio di nodi. E poi potresti notare che ora due parole terminano in O-P$-S$ e due parole terminano in T$-S$, quindi puoi comprimerle ulteriormente in:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
E ora abbiamo il DAWG minimo per questo dizionario.
Ulteriori letture:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
