python - 在 Python 中第一次出现模式时搜索 1GB+ 数据字符串的最快方法

Question

有一个 1 GB 的任意数据字符串，您可以假设它等同于以下内容:

1_gb_string=os.urandom(1*gigabyte)

我们将在这个字符串 1_gb_string 中搜索无限数量的固定宽度、1 KB 模式 1_kb_pattern。每次我们搜索的模式都会不同。所以缓存机会并不明显。将一遍又一遍地搜索相同的 1 GB 字符串。这是一个简单的生成器来描述正在发生的事情:

def findit(1_gb_string):
    1_kb_pattern=get_next_pattern()
    yield 1_gb_string.find(1_kb_pattern)

请注意，只需找到该模式的第一次出现。之后就不要再做其他主要的处理了。

我可以使用比 python 的 bultin find 更快的方法来匹配 1KB 模式与 1GB 或更大的数据字符串？

(我已经知道如何拆分字符串并并行搜索它，因此您可以忽略该基本优化。)

更新:请将内存要求限制在 16GB。

Answer 1

当您澄清可以接受较长的预处理时，我建议使用 Rabin-Karp 的变体:“一种用于多模式搜索的算法”，正如维基百科所说。

定义一个“滚动散列”函数，即当您知道haystack[x:x+N] 的散列时，计算haystack[x+] 的散列1:x+N+1] 是 O(1)。 (普通的哈希函数，比如 Python 内置的 hash 没有这个属性，这就是为什么你必须自己写，否则预处理会变得令人筋疲力尽长，而不仅仅是很长;-)。多项式方法是富有成效的，您可以使用 30 位哈希结果(如果需要，可以通过屏蔽，即，您可以进行更精确的计算，并只存储选择的屏蔽 30 位)。为了清楚起见，我们将此滚动哈希函数称为 RH。

因此，当您沿着干草堆 1GB 字符串滚动时，计算 1G 的 RH 结果；如果你只是存储这些，它会给你一个 1G 30 位值 (4GB) 映射 index-in-haystack->RH 值的数组 H。但是您想要反向映射，因此请改用包含 2**30 个条目(1G 条目)的数组 A，对于每个 RH 值，它都会为您提供干草堆中所有感兴趣的索引(出现该 RH 值的索引)；对于每个条目，您将第一个可能感兴趣的 haystack 索引的索引存储到另一个 1G 索引的数组 B 中，该数组被命令将所有索引保存到具有相同 RH 值(哈希术语中的“冲突”)相邻的 haystack 中。 H、A 和 B 都有 1G 条目，每个 4 字节，所以总共 12GB。

现在对于每个传入的 1K 针，计算其 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 应该执行很少的次数，直到以一种或另一种方式返回。所以每次针头搜索都应该非常非常快。