任意の順序でサブセット文字を含む行を選択

Question

私は、与えられた文字列で作ることができるすべての単語を選択しようとしている英語の単語のリストを含むテーブルを持っています"hand"（ゲームスクラブルのように）

+--------+ 
| word | 
+--------+ 
| test | 
| father | 
| woman | 
| zebra | 
+--------+ 

これまでの質問では、手の中の文字が単語に存在するかどうかだけを確認します。

SELECT * FROM words WHERE word SIMILAR to '%e%|%z%|%h%'; 
/* returns test, father and zebra as they all contain either e,z or h */ 

しかし、これは言葉を文字に手がよりも多くの時間、私は言葉が有効

def isValidWord(word, hand): 
    """Return true or false can the word be made using the characters in the hand""" 
    for i in word: # for each character in word 
     if hand.count(i)<word.count(i): # is the character in the hand enough times 
      return False 
    return True # if every character in the word is present in the hand 

私の質問であるかどうかを確認するためにpythonで使用していたコードが含まれているかどうかを考慮していません単語の各文字をチェックし、その文字の出現回数が文字列の出現回数よりも大きくないようにするクエリを作成するにはどうすればよいですか？ これはデータベースの仕事ではありませんか？

ありがとうございます。

Answer 1

これは完全に率直であるために、（リレーショナル）データベースの仕事ではありません。

英語の数千語という言い方をすれば、たとえそれをすべての思慮深い言い分に吹き飛ばしても、100k単語を超えることはありません。なぜデータベースを使用するのか分かりません。 Pythonで、メモリ内の単語リストを使って書くだけで、単純に線形に進むことができます。

データの量を高速に検索する方法はいくつかありますが、リレーショナルデータベースではそれらを適用できません。また、文字が1バイトのデータであることを考慮すると、速度ゲインは無視してください。

あなたがパフォーマンスについて心配している場合：yes、これはPythonでこれを行うと、文字の数が非常に高速で高度に最適化されるため、かなりのランタイムオーバーヘッドがありますが、Python自体は複雑な言語であり、 。かなり小さくなるように処理されるデータの量を考えると

、私のアプローチは次のようになります。

1. は、ワードリストを準備します。アルファベット順に辞書で各単語の文字を並べ替えると、ソートされた文字列を使用します実際の単語のキーとして使用します。 1つのソートされた文字列が複数の単語にマップできることがわかります。
2. ソートあなたの単語リスト内のすべてのキーのためにあなたの手の手紙
3. を、それはあなたの手のサブセットだかどうかを確認してください。以前のソートでは重複チェックを避けることができます（つまり、単語リストの最初の単語がaで始まり、手紙がeの場合は、開始する最初の単語にスキップしますe）。

ツリー構造はアルゴリズム的には高速ですが、ほとんどのPCスタイルのプロセッサでは、きれいに書かれたCコードが非常に速いSIMDの文字列比較にコンパイルされます。