3

私は、文字のセットを受け入れ、それが作成できるすべての可能な単語を返すSQLを作成しようとしています。私の最初の考えは、次のような基本的な3つのテーブルデータベースを作成することでした。

Words -- contains 200k words in real life
------
1 | act
2 | cat

Letters -- contains the whole alphabet in real life
--------
1  | a
3  | c
20 | t

WordLetters --First column is the WordId and the second column is the LetterId
------------
1  | 1
1  | 3
1  | 20
2  | 3
2  | 1
2  | 20

しかし、渡されたすべての文字に対してWordLettersにエントリがある単語を返すクエリを作成する方法に少し固執しています。また、同じ文字が2つある単語も考慮する必要があります。私はこのクエリから始めましたが、明らかに機能しません：

SELECT DISTINCT w.Word 
FROM Words w
INNER JOIN WordLetters wl
ON wl.LetterId = 20 AND wl.LetterId = 3 AND wl.LetterId = 1

渡されたすべての文字を含み、重複した文字を考慮した単語のみを返すクエリを作成するにはどうすればよいですか？

他の情報：

私のWordテーブルには200,000近くの単語が含まれているため、コードではなくデータベース側でこれを実行しようとしています。誰かが気にかけているなら、私はenable1単語リストを使用しています。

4

3 に答える 3

5

今のところ、問題のSQL部分を無視すると、私が使用するアルゴリズムはかなり単純です。まず、辞書の各単語を取得し、並べ替えられた順序の文字と、戻るポインターを使用してバージョンを作成します。その単語の元のバージョンに。

これにより、次のようなエントリを含むテーブルが作成されます。

sorted_text word_id
act         123    /* we'll assume `act` was word number 123 in the original list */
act         321    /* we'll assume 'cat' was word number 321 in the original list */

次に、入力（たとえば、「tac」）を受け取ったら、その文字を並べ替え、元の単語のテーブルに結合された並べ替えられた文字のテーブルで検索します。これにより、から作成できる単語のリストが得られます。その入力。

これを実行している場合、SQLデータベースにそのテーブルがありますが、おそらく他の何かを使用して、単語リストを並べ替えられた形式に前処理します。同様に、フロントエンドの作成に使用していたものにユーザーの入力の文字を並べ替えたままにしておくので、SQLはリレーショナルデータベース管理という優れた機能を実行することになります。

于 2012-04-19T17:26:00.900 に答える
0

提供するソリューションを使用する場合は、WordLettersテーブルに注文列を追加する必要があります。これがないと、取得した行が挿入した順序と同じ順序で取得されるという保証はありません。

しかし、私にはもっと良い解決策があると思います。あなたの質問に基づいて、順序や出現回数に関係なく、同じ構成文字を持つすべての単語を検索したいようです。これは、可能性の数が限られていることを意味します。アルファベットの各文字を2の異なる累乗に変換すると、文字の組み合わせごとに一意の値（別名ビットマスク）を作成できます。次に、単語で見つかった各文字の値を単純に合計できます。これにより、同じ文字を持つすべての単語が同じ値にマップされるため、単語の一致は簡単になります。次に例を示します。

WITH letters
     AS (SELECT Cast('a' AS VARCHAR) AS Letter,
                1                    AS LetterValue,
                1                    AS LetterNumber
         UNION ALL
         SELECT Cast(Char(97 + LetterNumber) AS VARCHAR),
                Power(2, LetterNumber),
                LetterNumber + 1
         FROM   letters
         WHERE  LetterNumber < 26),
     words
     AS (SELECT 1 AS wordid, 'act' AS word
         UNION ALL SELECT 2, 'cat'
         UNION ALL SELECT 3, 'tom'
         UNION ALL SELECT 4, 'moot'
         UNION ALL SELECT 5, 'mote')
SELECT wordid,
       word,
       Sum(distinct LetterValue) as WordValue
FROM   letters
       JOIN words
         ON word LIKE '%' + letter + '%'
GROUP  BY wordid, word

このクエリを実行するとわかるように、文字数の違いにもかかわらず、「act」と「cat」は「tom」と「moot」と同じWordValueを持ちます。

これがあなたのソリューションよりも優れている理由は何ですか？あなたはそれらを取り除くために多くの非単語を構築する必要はありません。これにより、タスクの実行に必要なストレージと処理の両方が大幅に節約されます。

于 2012-04-19T17:38:45.053 に答える
0

SQLにはこれに対する解決策があります。これには、トリックを使用して、各文字が単語に出現する回数を数えることが含まれます。次の式は、「a」が出現する回数をカウントします。

select len(word) - len(replace(word, 'a', ''))

アイデアは、単語内のすべての文字の合計を数え、それが全長と一致するかどうかを確認することです。

select w.word, (LEN(w.word) - SUM(LettersInWord))
from 
(
  select w.word, (LEN(w.word) - LEN(replace(w.word, wl.letter))) as LettersInWord
  from word w 
  cross join wordletters wl
) wls
having (LEN(w.word) = SUM(LettersInWord))

この特定のソリューションでは、文字を複数回出現させることができます。これが元の質問で望まれていたかどうかはわかりません。特定の回数まで発生させたい場合は、次のようにします。

select w.word, (LEN(w.word) - SUM(LettersInWord))
from 
(
   select w.word,
     (case when (LEN(w.word) - LEN(replace(w.word, wl.letter))) <= maxcount 
         then (LEN(w.word) - LEN(replace(w.word, wl.letter))) 
         else maxcount end) as LettersInWord
   from word w 
   cross join
   (
      select letter, count(*) as maxcount
      from wordletters wl
      group by letter
   ) wl
) wls
having (LEN(w.word) = SUM(LettersInWord))

文字と完全に一致させたい場合は、." = maxcount"の代わりにcaseステートメントを使用する必要があり" <= maxcount"ます。

私の経験では、実際には小さなクロス結合でまともなパフォーマンスが見られました。これは実際にはサーバー側で機能する可能性があります。サーバーでこの作業を行うことには、2つの大きな利点があります。まず、ボックスの並列処理を利用します。次に、はるかに少ないデータセットをネットワーク経由で転送する必要があります。

于 2012-04-19T17:56:23.877 に答える