Anda tidak. Tabel database relasional bukanlah struktur data yang cocok untuk memecahkan masalah ini seefisien yang Anda butuhkan.
Yang Anda lakukan adalah membuat trie struktur data dari kamus (atau, jika Anda benar-benar penggemar, Anda membuat dawg -- grafik kata asiklik terarah -- yang merupakan semacam trie terkompresi.)
Setelah Anda memiliki trie/dawg, menjadi sangat murah untuk menguji setiap kata dalam kamus terhadap rak tertentu, karena Anda dapat "memangkas" seluruh cabang besar kamus yang tidak mungkin cocok dengan rak.
Mari kita lihat contoh kecil. Misalkan Anda memiliki kamus "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" Dari situ Anda membuat trie ini:(Node dengan $ adalah yang ditandai sebagai "word can end here" .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
dan Anda memiliki rak "OPS" -- apa yang Anda lakukan?
Pertama Anda mengatakan "bisakah saya pergi ke cabang O?" Ya kamu bisa. Jadi sekarang masalahnya adalah mencocokkan "PS" dengan cabang O. Bisakah Anda turun ke cabang P? Ya. Apakah ada penanda akhir kata? Ya, jadi OP cocok. Sekarang masalahnya adalah mencocokkan "S" dengan cabang OP. Bisakah Anda turun ke cabang T? Tidak. Bisakah kamu turun ke cabang S? Ya. Sekarang Anda memiliki rak kosong dan Anda harus mencocokkannya dengan cabang OPS. Apakah ada penanda akhir kata? Ya! Jadi OPS cocok juga. Sekarang lacak kembali ke root.
Bisakah Anda turun ke cabang P? Ya. Sekarang masalahnya adalah mencocokkan OS dengan cabang P. Turun ke cabang PO dan cocokkan S -- itu gagal. Mundur ke akar.
Dan sekali lagi, Anda melihat bagaimana ini berjalan. Akhirnya kami turun ke cabang SOP dan menemukan akhir kata pada SOP, jadi "SOP" cocok dengan rak ini. Kami tidak turun cabang ST karena kami tidak punya T.
Kami telah mencoba setiap kemungkinan kata dalam kamus dan menemukan bahwa OP, OPS, dan SOP semuanya cocok. Tapi kami tidak pernah harus menyelidiki OPTS, POTS, STOP atau STOP karena kami tidak memiliki T.
Anda lihat bagaimana struktur data ini membuatnya sangat efisien? Setelah Anda menentukan bahwa Anda tidak memiliki huruf di rak untuk membuat awal sepatah kata pun, Anda tidak perlu menyelidiki apa pun kata kamus yang dimulai dengan awal itu. Jika Anda memiliki PO tetapi tidak memiliki T, Anda tidak perlu menyelidiki POTSHERD atau KENTANG atau KENTANG atau POTLATCH atau POTABLE; semua pencarian yang mahal dan sia-sia itu hilang dengan sangat cepat.
Mengadaptasi sistem untuk menangani ubin "liar" cukup mudah; jika Anda memiliki OPS?, maka jalankan saja algoritma pencarian 26 kali, pada OPSA, OPSB, OPSC ... Itu harus cukup cepat sehingga melakukannya 26 kali itu murah (atau melakukannya 26 x 26 kali jika Anda memiliki dua kosong. )
Ini adalah algoritme dasar yang digunakan oleh program AI Scrabble profesional, meskipun tentu saja mereka juga harus berurusan dengan hal-hal seperti posisi papan, manajemen rak, dan sebagainya, yang agak memperumit algoritme. Versi sederhana dari algoritme ini akan cukup cepat untuk menghasilkan semua kemungkinan kata di rak.
Jangan lupa bahwa tentu saja Anda hanya perlu menghitung trie/dawg sekali jika kamus tidak berubah seiring waktu. Mungkin memakan waktu lama untuk membuat percobaan dari kamus, jadi Anda mungkin ingin melakukannya sekali dan kemudian mencari cara untuk menyimpan trie pada disk dalam bentuk yang dapat diterima untuk membangunnya kembali dengan cepat dari disk.
Anda dapat mengoptimalkan penggunaan memori dengan membangun DAWG dari trie. Perhatikan bagaimana ada banyak pengulangan karena dalam bahasa Inggris, banyak kata akhir sama, sama seperti banyak kata dimulai sama. Trie melakukan pekerjaan yang bagus untuk berbagi node di awal tetapi pekerjaan yang buruk untuk membagikannya di akhir. Anda dapat melihat misalnya bahwa pola "S$ tanpa anak" sangat umum, dan ubah trie menjadi:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Menyimpan seluruh tumpukan node. Kemudian Anda mungkin memperhatikan bahwa dua kata sekarang diakhiri dengan O-P$-S$, dan dua kata diakhiri dengan T$-S$, sehingga Anda dapat mengompresnya lebih lanjut menjadi:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
Dan sekarang kami memiliki DAWG minimal untuk kamus ini.
Bacaan lebih lanjut:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
