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

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

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查找更快的速度来匹配1KB模式与1GB或更大的数据字符串？

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

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

最佳答案

当您澄清长时间的预处理是可以接受的时，我建议使用Rabin-Karp的一种变体:就像Wikipedia所说的那样:“一种用于多模式搜索的选择算法”。

定义一个“滚动哈希”函数，即，这样，当您知道haystack[x:x+N]的哈希时，计算haystack[x+1:x+N+1]的哈希为O(1)。 (普通的哈希函数(例如Python的内置hash不具有此属性，这就是为什么您必须编写自己的哈希表的原因，否则预处理将耗费很长的时间，而不仅仅是冗长的时间；-)。多项式方法是富有成果的，您可以使用30位的哈希结果(如果需要，可以通过屏蔽，即，您可以进行更精确的计算并仅存储选择的30位屏蔽)。为了清楚起见，我们将此滚动哈希函数称为RH。

因此，沿着干草堆1GB字符串滚动时，计算1G的RH结果；如果您只是存储这些，它将为您提供一个数组H，其中包含1G 30位值(4GB)映射index-in-haystack-> RH值。但是，您需要反向映射，因此请使用2 ** 30个条目(1G条目)的数组A，它为每个RH值提供了大海捞针中所有感兴趣的索引(出现RH值的索引)；对于每个条目，您将第一个可能有趣的干草堆索引的索引存储到另一个1G索引数组B的干草堆中，该数组将被保存以使所有具有相同RH值(哈希中的“冲突”)相邻的干草堆索引保持相邻。 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]

在相对湿度较高的情况下，您应该不会有太多的碰撞，因此，一次碰撞应该执行几次，直到返回一种或另一种方式。因此，每次针刺搜索都应该真的非常快。