快速列表中字符串搜索

Question

我在用Python 3，手里有一个包含超过10万个字符串的列表（list1），每个字符串最多300个字符。另外，我还有一个包含超过900万个子字符串的列表（list2）——我想统计list2中的每个子字符串在list1中出现的次数。比如，

list1 = ['cat', 'caa', 'doa', 'oat']
list2 = ['at', 'ca', 'do']

我希望这个函数能返回（对应到list2）：

[2, 2, 1]

通常来说，这个任务很简单，所需的代码也不多。但是，由于这两个列表的规模太大，我遇到了效率问题。我想找到最快的方法来返回这个计数列表。

我尝试过列表推导式、生成器、映射、各种循环，但还没有找到一个快速的方法来完成这个简单的任务。理论上，完成这个目标的最快方法是什么？最好能在O(len(list2))的时间内快速完成。

Answer 1

不太确定你怎么能避免出现某种O(n**2)的算法。这里有一个简单的实现。

>>> def some_sort_of_count(list1, list2):
>>>     return [sum(x in y for y in list1) for x in list2]
>>> 
>>> list1 = ['cat', 'caa', 'doa', 'oat']
>>> list2 = ['at', 'ca', 'do']
>>> some_sort_of_count(list1, list2)
[2, 2, 1]

Answer 2

我觉得这个任务可以用一种叫做Aho Corasick 字符串匹配的机器在线性时间内解决。可以查看这个回答，获取更多信息（也许你能从那个问题的其他回答中得到一些灵感，因为任务几乎是一样的，我认为 Aho Corasick 是理论上最快的解决方案）。

你需要对这个字符串匹配机器进行一些修改，让它在找到匹配时，不是返回匹配的结果，而是把每个匹配的子字符串的计数器加一。（这应该只是一个小改动）。

Answer 3

首先，设定 M = len(list1) 和 N = len(list2)，也就是说，M 是 list1 的长度，N 是 list2 的长度。

对于 list2 中的每一个条目，你都需要和 list1 中的每一个条目进行比较。这种情况下，最坏的情况运行时间是 O(M x N)。如果我们进一步分析，假设 list2 中的每个条目长度为 1，而 list1 中的每个条目长度为 300，那么运行时间就是 O(300M x N)。

如果性能真的很重要，可以尝试动态规划。这里有个开始的思路：

1) 将 list2 按照长度从小到大排序，像这样：

['scorch', 'scorching', 'dump', 'dumpster', 'dumpsters']

2) 将它们分成子列表，使得每个前面的条目都是后面条目的子集，像这样：

[['scorch', 'scorching'] , ['dump', 'dumpster', 'dumpsters']]

3) 现在，如果你在比较 list1 时发现 'scorch' 不在里面，那么你也不需要去找 'scorching'。同样的，如果 'dump' 不在里面，那么 'dumpster' 和 'dumpsters' 也不可能在里面。

注意，最坏情况下的运行时间仍然是一样的。