快速搜索1GB+数据字符串中模式首次出现的方法
这里有一个1GB大小的字符串，里面包含一些任意的数据，可以想象成类似于：
1_gb_string=os.urandom(1*gigabyte)
我们要在这个字符串1_gb_string中寻找无数个固定宽度的1KB模式1_kb_pattern。每次搜索的模式都会不同，所以没有明显的缓存机会。这个1GB的字符串会被反复搜索。下面是一个简单的生成器，来描述发生了什么：
def findit(1_gb_string):
1_kb_pattern=get_next_pattern()
yield 1_gb_string.find(1_kb_pattern)
注意，只需要找到模式的第一次出现。之后就不需要进行其他复杂的处理了。
有什么比Python内置的find()方法更快的方式，可以用来在1GB或更大的数据字符串中匹配1KB的模式，同时内存限制在16GB吗？
（我已经知道如何将字符串拆分并进行并行搜索，所以可以忽略这个基本的优化方法。）
11 个回答
一种高效但比较复杂的方法是使用Burrows-Wheeler变换进行全文索引。这个方法的步骤是先对你的源文本进行BWT处理，然后用一个小索引来快速找到文本中与输入模式匹配的任何子字符串。
这个算法的时间复杂度大约是O(n)，也就是说它的运行时间与要匹配的字符串长度有关，但与输入字符串的长度无关！而且，这个索引的大小并不会比输入数据大太多，通过压缩，甚至可以把它的大小缩小到比源文本还小。
既然你已经说明了长时间的预处理是可以接受的，我建议使用一种变体的 Rabin-Karp 算法，正如维基百科所说的那样：“这是一个适合多模式搜索的算法”。
首先，定义一个“滚动哈希”函数，也就是说，当你知道 haystack[x:x+N] 的哈希值时，计算 haystack[x+1:x+N+1] 的哈希值是 O(1) 的时间复杂度。
普通的哈希函数，比如 Python 内置的 hash，并不具备这个特性，这就是为什么你需要自己写一个，否则预处理的时间会变得非常非常长，而不仅仅是长而已;-)。
使用多项式的方法是有效的，你可以使用 30 位的哈希结果（如果需要的话可以进行掩码处理，也就是说，你可以用更高的精度进行计算，然后只存储选择的 30 位掩码）。
我们把这个滚动哈希函数称为 RH，为了简化。
接下来，计算 1 GB 的 RH 结果，随着你在 1 GB 的 haystack 字符串中滚动；如果你只是存储这些结果，就会得到一个包含 1 GB 30 位值的数组 H（总共 4 GB），这个数组将 haystack 中的索引映射到 RH 值。但你想要的是反向映射，所以可以使用一个包含 230 个条目的数组 A（1 GB 条目），这个数组对于每个 RH 值，给出在 haystack 中所有感兴趣的索引（该 RH 值出现的索引）；对于每个条目，你还需要将第一个可能感兴趣的 haystack 索引存储到另一个数组 B 中，这个数组包含 1 GB 的索引，并且是有序的，以便将所有具有相同 RH 值的 haystack 索引（在哈希术语中称为“碰撞”）放在一起。
H、A 和 B 都有 1 GB 的条目，每个条目占 4 字节，所以总共是 12 GB。
现在，对于每个传入的 1 KB 的 needle，计算它的 RH，称之为 k，然后用它作为 A 的索引；A[k] 会给你第一个索引 b，指向 B 中值得比较的位置。所以，执行以下操作：
ib = A[k]
b = B[ib]
while b < len(haystack) - 1024:
if H[b] != k: return "not found"
if needle == haystack[b:b+1024]: return "found at", b
ib += 1
b = B[ib]
如果 RH 做得好，你应该会有很少的碰撞，因此 while 循环应该执行很少的次数，直到返回结果。
所以每次搜索 needle 的速度应该非常非常快。