私は約200,000語のSQLデータベースを持っています。私はアナグラムの種類を解決することができるクエリが必要です。違いは、入力された文字で可能なすべての単語が必要なことです。たとえば、ofdgを入力すると、do,go、dogのように出力されます。このようなクエリにかかる時間を見積もることはできますか？どのようにしてより迅速かつ効率的にすることができますか？また、一般的には、200000行のデータベースを解析するにはどのくらい時間がかかりますか？SQLアナグラムの効率とロジックは？
この問題を解決するには、まず、すべての単語をスクラブルプレイヤーがアルファグラムと呼ぶように減らします。つまり、単語内のすべての文字がアルファベット順に表示されます。従ってdo,go及びdogは、do,go及びdgoとなる。勿論、任意の所与のアルファグラムは2つ以上のワードに対応することができるので、例えば、dgoのアルファベットは、dogおよびgodの両方のワードに対応する。
あなたがする必要がある次のことは、キーalphagram-シーケンス番号と、単一の属性フィールド語でテーブルを構築しています。
単語リストは静的である傾向があります。例えば、英語を話す世界の2つのスクラブル単語リストは、約5年ごとに変化します。したがって、このルックアップテーブルをあらかじめ作成する必要があります。性能はO（n）であり、沈んでいます。つまり、一度だけ実行して保存するため、クエリのコストにはカウントされません。 にはがあります。クエリが入るたびにそのようなインデックスを素早く作成するのは絶対に意味がありません。
あなたは「スクラブルについては何ですか？」と疑問に思うかもしれません。答えは、英語圏の世界で2つの承認されたトーナメントの単語リストの間に200,000語の数字がきれいに収まるということです。米国ナショナルスクラブル協会の公式トーナメントおよびクラブワードリスト（2006）には178,691語が含まれており、世界英語スクラブルプレイヤー協会が管理する国際的なリストには246,691件が含まれています。
クエリを取得すると、指定された単語が一連のアルファグラムに縮小されます。入力odfgはodfogodfdgfgdfodgofgodfgdfgo alphagramsなります（純粋なSQLではかなりのプログラミングの問題ですので、私はあなたのためにそれを行うだろうPHPやPythonやJavaScriptフロントエンドがあると仮定する必要があります）。次に、データベース内でルックアップを行います。各クエリのコストは、約O（log2 n）である必要があります。そのようなクエリは、リレーショナルデータベースが優れているものです。
ご参考までに、出力例が悪いです。 Alphagram dfgo Scrabbleのプレイヤーが「ビルド」と呼ぶもの（すべての可能なサブセット）は、doodgodoggodfogです。
（私はこのリグマロールをする必要はありませんが、ハスブロの弁護士は敏感ですので、ScrabbleはHasbro、Inc。が米国に所有する登録商標、Hasbro Canada Corporationはカナダ、残りはJW Spearの世界&マテル社のSons
これは素晴らしい解説ですBoar Gules本当に助けてくれてありがとうございます。 –
まあ、長さがnという単語の可能な文字の組み合わせの数はn!です。どうやら短い単語がほしいと思うようにいくつかの選択肢がありますが、これはあまり一般的な変更ではありません。O(n!)の関係です。だから、すべての組み合わせを試し、データベースでそれを調べる単純なアルゴリズムは複雑さを持つでしょう。
アルゴリズムをより効率的にすることは、明らかに検索スペースを減らすことです。これにはいくつかのオプションがあります。
200.000行の表を検索するには、そこに格納されているデータの種類、形式、およびその表の索引によって異なります。
あなたのスキーマはどのように見えますか？何を試しましたか？これは私の宿題のようなにおいがする。 – Flimzy