与 pjwerneck 的建议类似,您可以使用一棵树(或更具体地说是一棵树)trie https://en.wikipedia.org/wiki/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())
Running 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
这样常见的单词就可以快速查找,但你不会浪费内存来存储你从不查找的单词。)
- 该代码假设每个单词仅属于一个类别。 (如果没有,唯一的变化是
get_category
返回列表和相关部分PhraseTrie
循环遍历这个列表。)