文字のセットがどのような単語を見つけることができますか？

Question

私は、一連の文字を受け入れ可能なすべての可能な単語を返す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の表は、私はデータベース側ではなく、コードでこれを行うにしようとしています理由です20万言葉に近い含まれています。誰も気にしている場合はenable1 word listを使用しています。

Answer 1

問題のSQL部分を無視して、私が使用するアルゴリズムはかなり簡単です。辞書から各単語を取り出し、その文字をソート順に並べて作成します。その単語の元のバージョンにポインタを戻します。

これは、のようなエントリを持つテーブル与えるだろう：私たちは入力（たとえば、「TAC」）を受信したとき、我々は、ソート、それは手紙の当時

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 */ 

を、ソートされた手紙の私たちのテーブルにそれをルックアップするために参加しました元の単語の表であり、その入力から作成できる単語のリストが表示されます。

の場合は、SQLデータベースにそのテーブルがありますが、単語リストをソート済みのフォームに前処理するために他のものを使用している可能性があります。同様に、私はフロントエンドを作成するために使用していたものにユーザーの入力文字を並べ替えることを残したいので、SQLはそれがうまくいくように残されます：リレーショナルデータベース管理。

Answer 2

提供するソリューションを使用する場合は、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 

このクエリを実行する場合は、「トム」と「議論の余地」は、数の差にもかかわらず、そうであるように「行為」と「猫」は、同じWordValueを持って、わかるように文字。

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

Answer 3

SQLのこれに対する解決策があります。それは、各文字が単語に現れる回数を数えるためにトリックを使用することを含む。

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)) 

次の式では、「」表示された回数をカウントし

この特定の解決策は、複数の文字の出現を可能にする。私はこれが元の質問で望まれているかどうかわからない。私たちが出現一定数までしたい場合は、私たちは次のことを行う可能性があります：あなたは手紙に正確に一致する場合は、[case文が" = maxcount"代わりの" <= maxcount"を使用する必要があります

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)) 

。

私の経験では、実際には小さなクロスジョインでうまくいっています。実際にはサーバー側で動作する可能性があります。サーバー上でこの作業を行うことには2つの大きな利点があります。まず、ボックスの並列性を利用します。第2に、はるかに小さいデータセットをネットワークを介して転送する必要があります。