いくつかのワイルドカードを含む大きなリストのメンバーシップテスト

Question

特殊なカテゴリが含まれているフレーズが大きい（650k）フレーズリストに含まれているかどうかをテストするにはどうすればよいですか？

たとえば、フレーズ["he", "had", "the", "nerve"]がリストに含まれているかどうかをテストしたいとします。それはありますが、["he", "had", "!DETERMINER", "nerve"]の下にあります。"!DETERMINER"は、いくつかの選択を含む単語クラスの名前です(a, an, the)。私は約350の単語クラスを持っていて、そのうちのいくつかはかなり長いので、リスト内の各単語クラスが1つ（またはそれ以上）の単語クラスを列挙することは実現可能ではないと思います。

ゆっくりリストの中で作業する代わりに、これらのフレーズのセットを使用したいと思いますが、ワードクラスのばらつきにどう対処するかわかりません。私はこの比較を毎回数十回行う必要があるので、スピードはかなり重要です。スタートとして

Answer 1

、ツリー（またはより具体的に使用することができますtrie）を使用してリストをパーツに格納しますが、カテゴリを特別に扱うために拡張します。

python phrase_trie.pyを実行

# phrase_trie.py 

from collections import defaultdict 

CATEGORIES = {"!DETERMINER": set(["a","an","the"]), 
       "!VERB": set(["walked","talked","had"])} 

def get_category(word): 
    for name,words in CATEGORIES.items(): 
     if word in words: 
      return name 
    return None 

class PhraseTrie(object): 
    def __init__(self): 
     self.children = defaultdict(PhraseTrie) 
     self.categories = defaultdict(PhraseTrie) 

    def insert(self, phrase): 
     if not phrase: # nothing to insert 
      return 

     this=phrase[0] 
     rest=phrase[1:] 

     if this in CATEGORIES: # it's a category name 
      self.categories[this].insert(rest) 
     else: 
      self.children[this].insert(rest) 

    def contains(self, phrase): 
     if not phrase: 
      return True # the empty phrase is in everything 

     this=phrase[0] 
     rest=phrase[1:] 

     test = False 

     # the `if not test` are because if the phrase satisfies one of the 
     # previous tests we don't need to bother searching more 

     # allow search for ["!DETERMINER", "cat"] 
     if this in self.categories: 
      test = self.categories[this].contains(rest) 

     # the word is literally contained 
     if not test and this in self.children: 
      test = self.children[this].contains(rest) 

     if not test: 
      # check for the word being in a category class like "a" in 
      # "!DETERMINER" 
      cat = get_category(this) 
      if cat in self.categories: 
       test = self.categories[cat].contains(rest) 
     return test 

    def __str__(self): 
     return '(%s,%s)' % (dict(self.children), dict(self.categories)) 
    def __repr__(self): 
     return str(self) 

if __name__ == '__main__': 
    words = PhraseTrie() 
    words.insert(["he", "had", "!DETERMINER", "nerve"]) 
    words.insert(["he", "had", "the", "evren"]) 
    words.insert(["she", "!VERB", "the", "nerve"]) 
    words.insert(["no","categories","here"]) 

    for phrase in ("he had the nerve", 
        "he had the evren", 
        "she had the nerve", 
        "no categories here", 
        "he didn't have the nerve", 
        "she had the nerve more"): 
     print '%25s =>' % phrase, words.contains(phrase.split()) 

：

  he had the nerve => True 
     he had the evren => True 
     she had the nerve => True 
     no categories here => True 
he didn't have the nerve => False 
    she had the nerve more => False 

コードについていくつかのポイント：

• defaultdictの使用は、そのサブ・トライはinsertを呼び出す前に存在しているかどうかを確認することを避けるためです。必要に応じて自動的に作成され、初期化されます。
• get_categoryへの呼び出しがたくさんある場合は、速度のために逆引きルックアップ辞書を構築する価値があります。 （普通の言葉では検索が速いが、検索しない単語を格納するメモリは無駄にならないように、get_categoryへの呼び出しをメモしてください）
• このコードでは、各単語が1つのカテゴリにのみ含まれていると仮定しています。 （ない場合は、変更のみがget_categoryは、リストと、このリストをループPhraseTrieの関連セクションを戻ってきている。）

Answer 2

、2つのdictの作成：これはすべき

partOfSpeech = {'a':'!DETERMINER', 'an':'!DETERMINER', 'the':'!DETERMINER'} 
words = {'!DETERMINER': set(['a', 'an', 'the'])} 

を - 非常に少なくとも、 - あなたにいくつかのスピードアップを取得します。スピードアップがどれほどのものか、コメントが残っているかどうか、コメントを残してみるとよいでしょうか（またはSOコミュニティの他の人が私のソリューションを改善したり、より良いものを提供することさえできるかもしれません）。

Answer 3

スピードが重要で、ワードクラスを処理する必要がある場合は、フレーズとワードクラスのリストを格納する代わりに、単語のツリーとして格納することを考慮する必要があります。こうすることで、各レベルを簡単に照会でき、上に行くほど検索が絞り込まれます。単語が見つからないと、そのフレーズがリストにないことがわかります。

これはあなたのための例のように、非常に素朴な実装です。あなたも、このようなネストされたdictsとしてそれを実装するかもしれませんが、あなたのデータは、大規模かつ動的である場合、あなたはおそらく、データベースを使用する必要があります。

tree = {'he': 
     {'had': 
     {'the': {'nerve': {}, 'power': {}, 'gift': {}}, 
      'a': {'car': {}, 'bike': {}}, 
      'an': {'airplane': {}, 'awful': {'smell': {}}} 
      } 
     } 
     } 


def find_phrase(phrase, root):  
    if not phrase: 
     return True 

    try: 
     next = root[phrase[0]] 
     return find_phrase(phrase[1:], next) 
    except KeyError: 
     return False 

    return False 


assert find_phrase(['he', 'had', 'the', 'nerve'], tree) is True 
assert find_phrase(['he', 'had', 'the', 'power'], tree) is True 
assert find_phrase(['he', 'had', 'the', 'car'], tree) is False 
assert find_phrase(['he', 'had', 'an', 'awful', 'smell'], tree) is True 
assert find_phrase(['he', 'had', 'an', 'awful', 'wife'], tree) is False 

pjwerneckの提案と同様に