pjwerneck の提案と同様に、ツリー (またはより具体的にはtrie ) を使用してリストを部分的に格納できますが、それを拡張してカテゴリを特別に扱うことができます。
# 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())
実行中python phrase_trie.py
:
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