ワイルドカードを使用したスクラブルワードファインダー

あなたはそうしない。リレーショナルデータベーステーブルは、この問題を必要なだけ効率的に解決するための適切なデータ構造ではありません。

代わりに、 トライ を作成します。 辞書からのデータ構造（または、本当にマニアなら、 dawgを作成します -有向非巡回ワードグラフ-一種の圧縮されたトライです。）

トライ/ドーグを取得すると、すべてをテストするのが非常に安価になります。 ラックが一致しない可能性のある辞書の巨大なブランチ全体を「削除」できるため、特定のラックに対する辞書内の単語。

小さな例を見てみましょう。辞書「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$

そして、あなたはラック「OPS」を持っています-あなたは何をしますか？

まず、「Oブランチを下りてもいいですか？」と言います。はい、できます。したがって、問題は「PS」をOブランチと照合することです。 Pサブブランチを降りることができますか？はい。単語の終わりのマーカーはありますか？はい、OPは一致します。ここで、問題は「S」をOPブランチと照合することです。 Tブランチを下りてもらえますか？いいえ、Sブランチを下りてもらえますか？はい。これで空のラックができたので、OPSブランチと照合する必要があります。単語の終わりのマーカーはありますか？はい！したがって、OPSも一致します。次に、ルートに戻ります。

Pブランチを下りてもらえますか？はい。ここで問題となるのは、OSをPブランチと照合することです。 POブランチを下って、Sと一致します-失敗します。ルートに戻ります。

そして再び、これがどうなるかがわかります。最終的に、SOPブランチを下って、SOPで単語の終わりを見つけるので、「SOP」はこのラックに一致します。 Tがないので、STブランチを下りません。

辞書で考えられるすべての単語を試したところ、OP、OPS、SOPがすべて一致していることがわかりました。しかし、Tがなかったため、OPTS、POTS、STOP、またはSTOPSを調査する必要はありませんでした。

このデータ構造がどのようにそれを非常に効率的にするかわかりますか？ 最初のを作成するための文字がラックにないことを確認したら 一言で言えば、何かを調査する必要はありません。 その始まりで始まる辞書の単語。 POはあるがTがない場合は、POTSHERD、POTATO、POTASH、POTLATCH、POTABLEを調査する必要はありません。これらの高価で無駄な検索はすべてすぐになくなります。

「ワイルド」タイルを処理するようにシステムを適応させるのは非常に簡単です。 OPS？を使用している場合は、OPSA、OPSB、OPSCで検索アルゴリズムを26回実行するだけです。26回実行するのが安価であるほど高速である必要があります（または、ブランクが2つある場合は26x26回実行します。 ）

これは、プロのScrabble AIプログラムが使用する基本的なアルゴリズムですが、もちろん、ボードの位置やラックの管理なども処理する必要があるため、アルゴリズムが多少複雑になります。この単純なバージョンのアルゴリズムは、ラック上で可能なすべての単語を生成するのに十分な速度です。

もちろん、トライ/ドーグを1回計算するだけでよいことを忘れないでください。 辞書が時間の経過とともに変化しない場合。辞書からトライを作成するには時間がかかる可能性があるため、一度作成することをお勧めします。 次に、トライをディスクからすばやく再構築しやすい形式でディスクに保存する方法を見つけます。

トライからDAWGを構築することにより、メモリ使用量を最適化できます。英語では多くの単語が終了するため、繰り返しが多いことに注意してください。 同じように、たくさんの単語が始まる 同じ。トライは、最初はノードを共有するという素晴らしい仕事をしますが、最後にはノードを共有するというお粗末な仕事をします。たとえば、「子のないS $」パターンが非常に一般的であることに気付くと、トライは次のようになります。

           ^root^
          / |  \
        O   P    S
        |   |   / \
        P$  O  O   T   
       /  \ |  |   |
      T$  | T$ P$  O
      |    \ | |   |
       \    \| /   P$
        \    |/    |
         \   |    /
          \  |   /  
           \ |  /
            \| /  
             |/
             |       
             S$

ノードの山全体を保存します。そして、2つの単語がO-P $ -S $で終わり、2つの単語がT $ -S $で終わることに気付くかもしれません。そのため、さらに次のように圧縮できます。

           ^root^
           / | \
          O  P  S
          |  | / \
          P$ O \  T   
         /  \|  \ |
         |   |   \|
         |   |    O
         |   T$   |
          \  |    P$
           \ |   /
            \|  /  
             | /
             |/   
             S$

これで、この辞書の最小限のDAWGができました。

さらに読む：

http://dl.acm.org/citation.cfm?id=42420

http://archive.msdn.microsoft.com/dawg1

http://www.gtoal.com/wordgames/scrabble.html