0

これまでのところ、データベースには27個のテーブルがあります。1つの単語テーブル（スクラブル単語リスト）、および26の関連付けテーブル。

Table  Fields
================
word   [id,word]
a      [word_id,count]
b      [word_id,count]
...
z      [word_id,count]

文字列を指定して一致する単語を見つけようとしています。

たとえば、指定された配列がa,n,t知りたい場合：ant, tan, at, ta, an, na。

私の現在の戦略は、文字列内の各文字を分解して、すべての文字に一致する関連する単語を見つけることです。

例えば：

SELECT word.word
FROM word, a, n, t
WHERE
    word.id = a.word_id OR
    word.id = n.word_id OR
    word.id = t.word_id

しかし、これは、それらに含まれるすべての単語を印刷することa,n or tになります。

そして、すべての演算子をANDに切り替えると、一致するものが1つだけになりますant。

この謎を解くのを手伝ってくれませんか。

文字列内の重複する文字を処理する方法にも関心があります。count文字連想表のフィールドがここで役立つと思います。単語がの場合、関連付けテーブルappのカウントは2になります。p

私は関連付けテーブルで正しい方向に進んでいますか、それとももっと良い方法がありますか？

私はこれをphp/mysqlでかなり効率的に処理しようとしています。以前にC、perl、javaなどでこの謎を解いたことがある人がいることを私は知っています。

4

1 に答える 1

1

正規化されたアプローチが必要な場合は、次のようになります。

wordLetters{
  INT wordID,
  CHAR[1] letter,
  INT count,
  PK(wordID, letter)
}

words{
  INT wordID PK,
  VARCHAR(255) word UNIQUE
}

しかし、このアプローチにはパフォーマンスの点で深刻な問題があります。つまり、ワードテーブルの全表スキャンが必要です。文字が多すぎないと仮定して、このアプローチを提案します。

words{
  INT wordID PK,
  VARCHAR(255) word UNIQUE,
  INT cA KEY,
  INT cB KEY,
  ...
  INT cZ KEY,
  KEY (cE, cT, cA, cO, cI, cN),
  ...
}

ルックアップクエリは長くなりますが、インデックスを効率的に使用し、とにかくPHPコードによって生成されます。

ユーザーが持っている場合は[a,n,t]、使用可能な単語を次のようにフェッチします。

SELECT word FROM words WHERE
   cA <= 1 AND cB = 0 AND cC = 0 AND ... AND cY = 0 AND cZ = 0

「E」を必要としない単語は多くないため、このクエリは（おそらく）「ETAOIN」インデックスを使用します。

この時点で、パフォーマンスはデータベースでのみ使用可能なインデックスの選択に依存し、有用と見なされるインデックスをいつでも追加できます（実行時でも）。

データベースインデックスの場合：

通常のインデックスは、リスト上に適切なツリーが構築されたアイテムのソートされたリストであり、効率的な範囲ルックアップを可能にします（xからyまでのすべての要素を取得します）。

通常のインデックスは、そのソート順によって定義されます。並べ替えの順序は次のとおりです。最初にある列、次に別の列、次に別の列で並べ替えます。

たとえば、[E,T,A,O,I,N]インデックスにはすべての単語が並べ替えられます。最初に、を必要としないすべての単語、次にE1つを必要とするEすべての単語、次に2つを必要とするすべての単語E...。同じ量のEsを必要とする単語がソートされます。最初に、を必要としないTすべての単語、次にそれを1回必要とするすべての単語、次に2つTのsを必要とするすべての単語...。同じ数のEsとTsを必要とする単語のうち、必要のない単語Aが最初に来ます。

Eデータベースが、またはaを必要とせず、多くても1つの「X」を必要としないすべての単語をフェッチするように求められた場合、データベースはTこのインデックスを使用して最初の2つの要件を満たし、範囲内のすべての単語をチェックできますE=0, T=0。

特定の選択は、英語で最も頻繁に使用される12文字を頻度で並べ替えるETAOIN SHRDLUETAOINというフレーズに基づいています。つまり、このインデックスを使用する場合は、可能な限り多くの単語を除外する必要があります。

例を使用しますRSTLNE。Rこのインデックスは、プレーヤーにsがない場合に使用されSます。ルックアップをベンチマークすると、特定の各インデックスを使用することでどれだけの時間が節約されたかがわかります。

クエリを使用EXPLAIN EXTENDEDして、特定のクエリごとに考慮され、その後使用されるインデックスと、除外されると予想される行数を確認できます。元。：

EXPLAIN EXTENDED
  SELECT word FROM words
  WHERE cA=0 AND cB<=1 AND cC=0 AND ...
于 2012-10-28T20:02:18.290 に答える