快速在列表中搜索字符串

Question

使用Python 3，我有一个包含超过100,000个字符串（list1）的列表，每个字符串长度最多为300个字符。我还有一个超过9百万个子字符串（list2）的列表——我想要计算出在list2中的子字符串在多少个元素中出现过。例如，

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

我希望这个函数返回 (映射到list2)：

[2, 2, 1]

通常情况下，这非常简单且需要很少的步骤。但是，由于列表的巨大大小，我遇到了效率问题。我希望找到最快的方法返回计数器列表。

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

- user1104160

Answer 1

我相信使用Aho Corasick字符串匹配算法，可以在线性时间内解决这个任务。 请参考this答案，以获取更多信息（也许你可以从其他回答中得到灵感，因为它们几乎是相同的任务，我认为Aho Corasick是理论上最快的解决方法）。

您需要修改字符串匹配机器，使其不返回匹配项，而是将每个匹配的子字符串计数器增加一。（这应该只是一个小修改）。

- tobigue

Answer 2

设 M = len(list1)，N = len(list2)

对于 list2 中的每一个条目，您需要对 list1 中的所有条目进行 M 次比较。这是最坏情况下的运行时间为 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'也不在其中。

请注意，最坏情况下的运行时间仍然相同。

- puk

---

这将需要大量的开销，但您可以尝试基于它们所拥有的字符对list1和list2进行索引，因此如果list1的一个条目是“abcd”，则您不会检查list2条目“efg”，而只会检查落在路径/分支下的“a”、“b”、“c”或“d”的list2条目。 - puk

稍等，我正在为您创建一个小例子……这可真是浪费周五的方式。 - puk

@user1104160 哇，你在做什么啊？我正在尝试创建900万个随机生成的字符串，已经花费了5分钟以上了。 - puk

基因组学。900万是比较小的规模。 - user1104160

奇怪的是，获取900万个序列非常快，只需要大约3分钟。 - user1104160

Answer 3

不确定如何避免使用某种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]

- hughdbrown