当列表包含特殊类别时，如何测试一个短语是否在一个大型 (650k) 短语列表中？
例如，我想测试短语 ["he", "had", "the", "nerve"] 是否在列表中。它是，但在 ["he", "had", "!DETERMINER", "nerve"] 下，其中 "!DETERMINER" 是包含的词类的名称几个选择 (a, an, the)。我有大约 350 个词类，其中一些相当长，所以我认为枚举列表中具有一个(或多个)词类的每个项目是不可行的。
我想使用一组这样的短语，而不是慢慢地浏览一个列表，但我不知道如何处理词类的可变性。速度非常重要，因为我每次需要进行数十万次这种比较。
请您参考如下方法:
与 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的调用，这样常用词可以快速查找，但您不会浪费内存来存储您从未查找过的词。) - 代码假定每个词只属于一个类别。 (如果没有，唯一的变化是
get_category返回一个列表，PhraseTrie的相关部分循环遍历此列表。)
