Ty ne. Tabulka relační databáze není vhodnou datovou strukturou pro řešení tohoto problému tak efektivně, jak potřebujete.
Místo toho vytvoříte trie datová struktura mimo slovník (nebo, pokud jste opravdu buff, vytvoříte dawg -- řízený acyklický slovní graf -- což je druh komprimovaného trie.)
Jakmile budete mít trie/dawg, stane se velmi levné testovat každý slovo ve slovníku proti danému racku, protože můžete "ořezat" celé obrovské větve slovníku, kterým se rack nemůže rovnat.
Podívejme se na malý příklad. Předpokládejme, že máte slovník "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS" Z toho vytvoříte tento pokus:(Uzly s $ jsou ty, které jsou označeny jako "slovo může končit zde" .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
a máte rack "OPS" -- co děláte?
Nejprve řeknete "mohu jít dolů po větvi O?" Ano můžeš. Takže teď je problém porovnat "PS" s větví O. Můžete jít dolů po vedlejší větvi P? Ano. Má značku konce slova? Ano, takže OP je zápas. Nyní je problém porovnat "S" s větví OP. Můžete jít dolů po větvi T? Ne. Můžete jít dolů po větvi S? Ano. Nyní máte prázdný stojan a musíte jej porovnat s větví OPS. Má značku konce slova? Ano! Takže zápasy OPS také. Nyní se vraťte do kořenového adresáře.
Můžete jít dolů po větvi P? Ano. Nyní je problém porovnat OS s větví P. Jděte dolů po větvi PO a spojte S -- to selže. Zpět ke kořenu.
A zase vidíte, jak to jde. Nakonec půjdeme po větvi SOP a najdeme konec slova na SOP, takže "SOP" odpovídá tomuto stojanu. Nescházíme po větvi ST, protože nemáme T.
Vyzkoušeli jsme všechna možná slova ve slovníku a zjistili jsme, že OP, OPS a SOP se shodují. Ale nikdy jsme nemuseli zkoumat OPTS, POTS, STOP nebo STOPS, protože jsme neměli T.
Vidíte, jak je tato datová struktura velmi efektivní? Jakmile zjistíte, že na stojanu nemáte písmena, abyste mohli udělat začátek slova, nemusíte žádné zkoumat slova ze slovníku, která začínají tímto začátkem. Pokud máte PO, ale ne T, nemusíte zkoumat POTSHERD nebo POTATO nebo POTASH nebo POTLATCH nebo POTABLE; všechna ta drahá a neplodná hledání mizí velmi rychle.
Přizpůsobení systému, aby se vypořádal s "divokými" dlaždicemi, je docela jednoduché; pokud máte OPS?, pak stačí spustit vyhledávací algoritmus 26krát, na OPSA, OPSB, OPSC... Mělo by to být dostatečně rychlé, aby to bylo levné 26krát (nebo to udělat 26 x 26krát, pokud máte dvě prázdné stránky. )
Toto je základní algoritmus, který používají profesionální programy Scrabble AI, i když se samozřejmě také musí vypořádat s věcmi, jako je pozice desky, správa stojanu a tak dále, což algoritmy poněkud komplikuje. Tato jednoduchá verze algoritmu bude dostatečně rychlá, aby vygenerovala všechna možná slova na stojanu.
Nezapomeňte, že samozřejmě stačí vypočítat trie/dawg jednou pokud se slovník v průběhu času nemění. Sestavení pokusu ze slovníku může být časově náročné, takže to možná budete chtít udělat jednou a pak vymyslet nějaký způsob, jak uložit pokus na disk ve formě, která umožňuje jeho rychlé sestavení z disku.
Využití paměti můžete optimalizovat vytvořením DAWG z pokusu. Všimněte si, jak se hodně opakuje, protože v angličtině je spousta slov end totéž, stejně jako mnoho slov začíná stejný. Trie dělá skvělou práci při sdílení uzlů na začátku, ale mizernou práci při jejich sdílení na konci. Můžete si například všimnout, že vzor "S$ bez potomků" je extrémně běžný a přeměňte pokus na:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Uložení celé hromady uzlů. A pak si můžete všimnout, že dvě slova nyní končí O-P$-S$ a dvě slova končí T$-S$, takže to můžete dále zkomprimovat na:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
A nyní máme minimální DAWG pro tento slovník.
Další čtení:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html