Python有效的方法来检查非常大的字符串是否包含子字符串

Question

Python不是我最好的语言,所以我不是那么擅长为我的一些问题找到最有效的解决方案.我有一个非常大的字符串(来自一个30 MB的文件),我需要检查该文件是否包含一个较小的子字符串(此字符串只有几十个字符).我目前的做法是:

if small_string in large_string:
    # logic here

但这似乎效率很低,因为它会检查文件中每个可能的字符序列.我知道在换行符上只会有完全匹配,所以最好是以列表形式读取文件并遍历该列表以匹配？

编辑:为了澄清一些关于"仅在换行符上匹配"的混淆,这是一个例子:

small_string = "This is a line"
big_string = "This is a line\nThis is another line\nThis is yet another"

如果我没有错,in关键字将检查所有序列,而不仅仅是每一行.

Answer 1

这真的很慢吗？你说的是30MB字符串; 让我们尝试更大的字符串:

In [12]: string="agu82934u"*50*1024*1024+"string to be found"

In [13]: len(string)
Out[13]: 471859218

In [14]: %timeit "string to be found" in string
1 loops, best of 3: 335 ms per loop

In [15]: %timeit "string not to be found" in string
1 loops, best of 3: 200 ms per loop

我不会说335毫秒是很多时间寻找450MB字符串中的子字符串.

Answer 2

慢得多慢？我刚刚a in b在170 MB字符串的末尾对一个唯一的字符串进行了测试.它在我的手指离开Enter键之前完成.

Answer 3

您可以使用以下算法之一：

\n\n

\n

• Rabin\xe2\x80\x93Karp 字符串搜索算法

\n

• Knuth\xe2\x80\x93Morris\xe2\x80\x93Pratt 算法（又名 KMP）请参阅此处的实现

\n

\n\n

虽然我相信 KMP 更高效，但实现起来更复杂。第一个链接包含一些伪代码，应该很容易在 python 中实现。

\n\n

您可以在这里寻找替代方案：http ://en.wikipedia.org/wiki/String_searching_algorithm

\n