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

Question

有一个1千兆字节的任意数据字符串,你可以认为它等同于:

1_gb_string=os.urandom(1*gigabyte)

我们将搜索此字符串,1_gb_string以获得无限数量的固定宽度,1千字节模式,1_kb_pattern.每次我们搜索模式都会有所不同.所以缓存机会并不明显.将反复搜索相同的1千兆字节的字符串.这是一个简单的生成器来描述正在发生的事情:

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

请注意,只需要找到第一次出现的模式.之后,不应该进行其他主要处理.

我能用什么比python的bultin找到更快的匹配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)的数组H映射index-in-haystack-> RH值.但是你想要反向映射,所以请使用2**30个条目(1G条目)的数组A,每个RH值为你提供干草堆中所有感兴趣的指数(RH值出现的指数); 对于每个条目,您将第一个可能有趣的干草堆索引的索引存储到另一个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应该执行很少次,直到以某种方式返回.因此,每次针搜索都应该非常快.

Answer 2

在遗传学领域中有许多字符串匹配算法用于查找子字符串.您可以尝试本文或本文

Answer 3

借助无限内存，您可以对每个 1k 字符串及其在 1 GB 文件中的位置进行哈希处理。

如果内存小于无限，您将受到搜索时接触的内存页面数量的限制。