Du nicht. Eine relationale Datenbanktabelle ist keine geeignete Datenstruktur, um dieses Problem so effizient wie nötig zu lösen.
Stattdessen bauen Sie einen Trie Datenstruktur aus dem Wörterbuch (oder, wenn Sie wirklich muskulös sind, bauen Sie eine dawg -- ein gerichteter azyklischer Wortgraph -- der eine Art komprimierter Trie ist.)
Sobald Sie einen Trie/Dawg haben, wird es sehr kostengünstig, alle zu testen Wort im Wörterbuch gegen ein bestimmtes Rack, weil Sie ganze riesige Zweige des Wörterbuchs "ausschneiden" können, die das Rack unmöglich abgleichen kann.
Schauen wir uns ein kleines Beispiel an. Angenommen, Sie haben das Wörterbuch "OP, OPS, OPT, OPTS, POT, POTS, SOP, SOPS, STOP, STOPS". Daraus erstellen Sie diesen Trie:(Knoten mit einem $ sind diejenigen, die als "Wort kann hier enden" markiert sind. .
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ S$ T$ P$ O
| | | |
S$ S$ S$ P$
|
S$
und Sie haben das Rack "OPS" - was tun Sie?
Zuerst sagst du:"Kann ich den O-Zweig hinuntergehen?" Ja, du kannst. Das Problem besteht nun darin, "PS" mit dem O-Zweig abzugleichen. Können Sie den P-Unterzweig hinuntergehen? Ja. Hat es eine Wortende-Markierung? Ja, OP passt also. Jetzt besteht das Problem darin, "S" mit dem OP-Zweig abzugleichen. Kannst du den T-Zweig hinuntergehen? Nein. Können Sie den S-Zweig hinunterfahren? Ja. Jetzt haben Sie das leere Rack und müssen es mit dem OPS-Zweig abgleichen. Hat es eine Wortende-Markierung? Ja! OPS passt also auch. Gehen Sie jetzt zurück bis zur Wurzel.
Kannst du den P-Zweig hinuntergehen? Ja. Jetzt besteht das Problem darin, das Betriebssystem mit dem P-Zweig abzugleichen. Gehen Sie den PO-Zweig hinunter und passen Sie S an - das schlägt fehl. Zurück zur Wurzel.
Und wieder sehen Sie, wie das geht. Schließlich gehen wir den SOP-Zweig hinunter und finden ein Ende des Wortes auf SOP, also passt "SOP" zu diesem Rack. Wir gehen den ST-Zweig nicht hinunter, weil wir kein T haben.
Wir haben alle möglichen Wörter im Wörterbuch ausprobiert und festgestellt, dass OP, OPS und SOP übereinstimmen. Aber wir mussten OPTS, POTS, STOP oder STOPS nie untersuchen, weil wir kein T hatten.
Sehen Sie, wie diese Datenstruktur es sehr effizient macht? Sobald Sie festgestellt haben, dass Sie die Buchstaben nicht auf dem Ständer haben, um den Anfang zu machen Mit einem Wort, Sie müssen keine untersuchen Wörterbuchwörter, die mit diesem Anfang beginnen. Wenn Sie PO, aber kein T haben, müssen Sie POTSCHERD oder POTATO oder POTASH oder POTLATCH oder POTABLE nicht untersuchen; All diese teuren und erfolglosen Suchen verschwinden sehr schnell.
Die Anpassung des Systems an "wilde" Kacheln ist ziemlich einfach; Wenn Sie OPS haben?, dann führen Sie den Suchalgorithmus einfach 26 Mal aus, auf OPSA, OPSB, OPSC ... Es sollte schnell genug sein, dass es billig ist, es 26 Mal zu tun (oder es 26 x 26 Mal zu tun, wenn Sie zwei Leerzeichen haben. )
Dies ist der grundlegende Algorithmus, den professionelle Scrabble-KI-Programme verwenden, obwohl sie sich natürlich auch mit Dingen wie Platinenposition, Rack-Management und so weiter befassen müssen, was die Algorithmen etwas komplizierter macht. Diese einfache Version des Algorithmus ist schnell genug, um alle möglichen Wörter auf einem Regal zu generieren.
Vergessen Sie nicht, dass Sie den trie/dawg natürlich nur einmal berechnen müssen wenn sich das Wörterbuch im Laufe der Zeit nicht ändert. Es kann zeitaufwändig sein, den Trie aus dem Wörterbuch zu erstellen, daher sollten Sie dies einmal tun und finden Sie dann einen Weg, den Versuch auf der Festplatte in einer Form zu speichern, die für eine schnelle Wiederherstellung von der Festplatte geeignet ist.
Sie können die Speichernutzung optimieren, indem Sie aus dem Trie eine DAWG erstellen. Beachten Sie, dass es viele Wiederholungen gibt, weil im Englischen viele Wörter enden genauso, wie viele Wörter beginnen das gleiche. Der Trie leistet am Anfang großartige Arbeit beim Teilen von Knoten, aber am Ende ist es lausig, sie zu teilen. Sie können zum Beispiel feststellen, dass das Muster „S$ ohne Kinder“ sehr verbreitet ist, und den Trie umwandeln in:
^root^
/ | \
O P S
| | / \
P$ O O T
/ \ | | |
T$ | T$ P$ O
| \ | | |
\ \| / P$
\ |/ |
\ | /
\ | /
\ | /
\| /
|/
|
S$
Speichern eines ganzen Stapels von Knoten. Und dann stellen Sie vielleicht fest, dass zwei Wörter jetzt auf O-P$-S$ enden und zwei Wörter auf T$-S$ enden, sodass Sie es weiter komprimieren können zu:
^root^
/ | \
O P S
| | / \
P$ O \ T
/ \| \ |
| | \|
| | O
| T$ |
\ | P$
\ | /
\| /
| /
|/
S$
Und jetzt haben wir die minimale DAWG für dieses Wörterbuch.
Weiterführende Literatur:
http://dl.acm.org/citation.cfm?id=42420
http://archive.msdn.microsoft.com/dawg1
http://www.gtoal.com/wordgames/scrabble.html
