2

我正在尝试优化一个程序，该程序需要在流的每个位置（字节）处为数据流中的恒定大小窗口计算哈希。在比可用 RAM 大得多的磁盘文件中查找重复项是必需的。目前我为每个窗口计算单独的 md5 哈希，但它花费大量时间（窗口大小为几千字节，因此每个字节的数据被处理几千次）。我想知道是否有一种方法可以在恒定（与窗口大小无关）时间内计算每个后续哈希（例如移动平均线中 1 个元素的加法和减法）？散列函数可以是任何东西，只要它不提供长散列（50-100 位就可以）并且它的计算速度相当快。

如果您指出 linux 上可用的现有库函数（如果有的话），我将不胜感激。

这是我在这里的第一个问题，所以如果我做错了什么，请多多包涵。

问候，巴托什

4

2 回答 2

3

关于滚动散列的维基百科文章有一个指向ngramhashing的链接，它在 C++ 中实现了一些不同的技术，包括：

  • 随机 Karp-Rabin（有时称为 Rabin-Karp）
  • 循环多项式哈希（也称为 Buzhash）
  • 通过不可约多项式散列

（也可以在GitHub上找到）

于 2013-01-11T15:06:41.123 回答
2

您所描述的与重复数据删除存储中使用的基本方法非常接近。

在重复数据删除系统中，我们通常使用Rabin 的指纹方法作为快速、滚动的哈希函数。然而，虽然 Rabin 指纹是良好且易于理解的碰撞特性，但它在密码学上并不安全，即会发生碰撞。检查例如Bentley 等人如何。在他们的压缩方法中使用了这种方法。问题是您是否可以容忍以及可以容忍多少冲突。如果您可以容忍偶尔的碰撞，那么一个好的 Rabin 指纹实现可能是一个好主意。好的实现每个核心每秒可以处理超过 200 MB。

我不知道有任何几乎没有冲突（又名加密安全）并且同时滚动的方法。作为 PlasmaHH，我非常怀疑这实际上是否可行。

想想你是否可以放松你的限制。也许你可以允许错过一些重复。在这些情况下，更快的方法是可能的。

于 2013-01-11T15:33:12.757 回答