12

有一个 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。

4

10 回答 10

12

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

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

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

使用良好的 RH，您应该很少发生碰撞，因此 while 应该执行很少几次，直到以一种或另一种方式返回。所以每个针搜索应该非常非常快。

于 2009-11-17T18:19:04.323 回答
5

在遗传学领域有许多字符串匹配算法用于查找子字符串。你可以试试这篇论文或这篇论文

于 2009-11-17T17:19:38.933 回答
1

您愿意花大量时间预处理字符串吗？

如果你是，你可以做的是建立一个带有偏移量的 n-gram 列表。

假设您的字母表是十六进制字节并且您使用的是 1-gram。

然后对于 00-ff，您可以创建一个看起来像这样的字典（perlese，抱歉）

$offset_list{00} = @array_of_offsets
$offset_list{01} = #...etc

您沿着字符串向下走并从发生字节的所有点构建@array_of_offsets。您可以对任意 n-gram 执行此操作。

这提供了一个可用于步行的“搜索起点”。

当然，缺点是您必须对字符串进行预处理，所以这是您的权衡。

编辑：

这里的基本思想是匹配前缀。如果信息非常相似，这可能会很糟糕，但如果 n-gram 之间存在相当大的差异，您应该能够很好地匹配前缀。

让我们量化分歧，因为您尚未讨论您正在分析的信息类型。出于该算法的目的，我们可以将散度描述为距离函数：您需要相当高的汉明距离。如果 n-gram 之间的汉明距离为 1，则上述想法将行不通。但是如果是n-1，上面的算法会简单很多。

为了改进我的算法，让我们构建一个连续消除可能性的算法：

我们可以调用香农熵来定义给定 n-gram 的信息。获取您的搜索字符串并根据前 m 个字符连续构建一个前缀。当 m 前缀的熵“足够高”时，稍后再使用它。

  1. 将 p 定义为搜索字符串的 m 前缀
  2. 搜索您的 1 GB 字符串并创建与 p 匹配的偏移量数组。
  3. 将 m-prefix 扩展为某个 k-prefix，k > m，k-prefix 的熵高于 m-prefix。
  4. 保留上面定义的元素偏移数组，以使它们与 k 前缀字符串匹配。丢弃不匹配的元素。
  5. 转到 4，直到满足整个搜索字符串。

从某种意义上说，这就像反转霍夫曼编码。

于 2009-11-17T17:23:04.903 回答
1

据我所知，标准查找算法是具有 n*m 比较复杂性的简单算法，因为它针对每个可能的偏移量检查模式。有一些更有效的算法，需要大约 n+m 次比较。如果您的字符串不是自然语言字符串，您可以尝试 Knuth–Morris–Pratt 算法。Boyer-Moore 搜索算法也足够快速和简单。

于 2009-11-17T17:41:25.993 回答
0

如果模式相当随机，您可以预先计算字符串的 n 个前缀的位置。

无需查看 n 前缀的所有选项，只需使用 1GB 字符串中的实际选项 - 其中少于 1Gig。使用尽可能大的前缀以适合您的内存，我没有 16GB 的 RAM 可以检查，但前缀 4 可以工作（至少在内存高效的数据结构中），如果不尝试 3 甚至 2。

对于随机 1GB 字符串和随机 1KB 模式，如果使用 3 字节前缀，每个前缀应该得到几十个位置，但是 4 字节前缀应该得到平均 0 或 1 ，因此查找应该很快。

预计算位置

def find_all(pattern, string):
  cur_loc = 0
  while True:
     next_loc = string.find(pattern, cur_loc)
     if next_loc < 0: return
     yield next_loc
     cur_loc = next_loc+1

big_string = ...
CHUNK_SIZE = 1024
PREFIX_SIZE = 4
precomputed_indices = {}
for i in xrange(len(big_string)-CHUNK_SIZE):
  prefix = big_string[i:i+PREFIX_SIZE]
  if prefix not in precomputed_indices:
    precomputed_indices[prefix] = tuple(find_all(prefix, big_string))

查找模式

def find_pattern(pattern):
  prefix = pattern[:PREFIX_SIZE]
  # optimization - big prefixes will result in many misses
  if prefix not in precomputed_indices:
    return -1
  for loc in precomputed_indices[prefix]:
    if big_string[loc:loc+CHUNK_SIZE] == pattern:
        return loc
  return -1
于 2009-11-17T18:07:16.723 回答
0

如果你有足够的 RAM（甚至可能是磁盘/交换）可用，有人暗示了一种可能的方法来索引这个东西。

想象一下，如果您对从原始 Gig 字符串中的每个字符扩展的 1K 块执行简单的 32 位 CRC。这将导致从数据开头偏移的每个字节偏移 4 字节的校验和数据。

就其本身而言，这可能会适度提高搜索速度。每个 1K 搜索目标的校验和可以根据每个 CRC 进行检查……每次碰撞都测试了一个真正的匹配。这仍然应该比正常的线性搜索快几个数量级。

显然，CRC 数组需要我们 4GB 的 RAM（加上原始数据的原始 Gig 以及环境和我们的程序的更多开销）。

如果我们有大约 16GB，我们可以对校验和进行排序并存储找到每个偏移量的列表。这变成了一个索引搜索（每个目标搜索平均大约 16 个探测器……最坏的情况是大约 32 或 33 个（可能是那里的栅栏）。

16BG 文件索引可能仍会比线性校验和搜索提供更好的性能，并且几乎肯定会比线性原始搜索更好（除非您的文件系统/存储速度极慢）。

（补充）：我应该澄清一下，这种策略只有在您描述了需要对同一个千兆字节数据块进行多次搜索的情况下才有用。

您可以使用线程方法来构建索引（同时读取它以及让多个线程执行校验和）。您还可以将索引卸载到单独的进程或节点集群（特别是如果您使用基于文件的索引 --- 上述 ~16GB 选项）。使用简单的 32 位 CRC，您可能能够以读取器线程获取数据的速度执行校验和/索引（但我们谈论的是每 1K 数据有 1024 个校验和，所以可能不是）。

您可以通过在 C 中编写一个 Python 模块来进一步提高性能，以便实际执行搜索……和/或可能执行校验和/索引。

显然，此类 C 扩展的开发和测试需要进行其他权衡。听起来这将具有几乎为零的可重用性。

于 2009-11-17T18:39:26.503 回答
0

一种有效但复杂的方法是使用 Burrows-Wheeler 变换进行全文索引。它涉及对您的源文本执行 BWT，然后在其上使用一个小索引来快速找到文本中与您的输入模式匹配的任何子字符串。

该算法的时间复杂度大约为 O(n) 与您匹配的字符串的长度 - 并且与输入字符串的长度无关！此外，索引的大小不会比输入数据大多少，并且通过压缩甚至可以减小到源文本大小以下。

于 2009-11-19T10:19:50.970 回答
0

使用无限内存，您可以散列每个 1k 字符串及其在 1 GB 文件中的位置。

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

于 2009-11-17T17:18:54.863 回答
0

我不确定find()字符串的方法是否比search()Python 的re（正则表达式）模块提供的方法更快，但只有一种方法可以找出答案。

如果你只是搜索一个字符串，你想要的是：

import re
def findit(1_gb_string):
    yield re.search(1_kb_pattern, 1_gb_string)

但是，如果您真的只想要第一个匹配项，则最好使用finditer()返回迭代器的 ，并且使用如此大的操作实际上可能会更好。

于 2009-11-17T17:28:52.633 回答
0

http://www.youtube.com/watch?v=V5hZoJ6uK-s 对您最有价值。它是关于动态编程的麻省理工学院讲座

于 2009-11-17T17:30:12.127 回答