python - 用于字符串查找的集合与正则表达式，哪个更具可扩展性？

Question

假设我需要处理一个非常大的单词列表，并且我需要计算在我拥有的一段文本中找到这些单词的次数。就可扩展性而言，哪个是最佳选择？

选项 I（正则表达式）

>>> import re
>>> s = re.compile("|".join(big_list))
>>> len(s.find_all(sentence))

方案二（套）

>>> s = set(big_list)
>>> len([word for word in sentence.split(" ") if word in s]) # O(1) avg lookup time

示例：如果列表是 ["cat","dog","knee"] 并且文本是“狗跳过了猫，但是狗摔断了膝盖”，最终结果应该是：4

PS 欢迎任何其他选择

score 2 · Accepted Answer

如果你的话是字母数字，我可能会使用类似的东西：

s = set(big_list)
sum(1 for x in re.finditer(r'\b\w+\b',sentence) if x.group() in s)

由于集合的成员资格测试平均为 O(1)，因此该算法变为 O(N+M)，其中 N 是句子中的单词数，M 是 big_list 中的元素数。不是太寒酸。它在内存使用方面也做得很好。

score 0 · Accepted Answer

一种可扩展的方法是对输入字典和文本中的单词进行排序，然后使用两个迭代器进行匹配。您还可以使用 trie以获得更好的性能。我不知道该集合的内部表示，但是，使用大型正则表达式将是一种过度杀伤。

2 回答 2