高效的'滚动/移动散列'计算（如移动平均）

我想优化一个程序，需要计算一个数据流中的每个位置（字节）的恒定大小的窗口散列。需要在磁盘文件中查找比可用RAM大得多的重复数据。目前，我为每个窗口计算单独的md5散列，但花费很多时间（窗口大小为几千字节，因此每个数据字节处理几千次）。我想知道是否存在一种方法来计算常量（窗口大小无关）时间内的每个后续散列（例如移动平均中1个元素的加减）？散列函数可以是任何东西，只要它不会产生很长的哈希（50-100位是确定的）并且其计算速度相当快。它也必须在多达数以万亿计的非随机窗口（数据TB）上进行实验 - 每次碰撞都意味着我的磁盘访问（crc32非常弱，md5在这方面没问题）。高效的'滚动/移动散列'计算（如移动平均）

如果您指出我现有的Linux上可用的库函数（如果有的话），我将非常感激。

这是我的第一个问题，所以如果我做错了，请耐心等待。

问候，的Bartosz

来源

2013-01-11 bzaborow

良好散列函数的特性之一（导致统计适量的冲突）是它们的最终值取决于混合/输入数据的所有位，即在每个处理步骤的计算中下一块数据的结果取决于迄今为止已处理的所有位。如果现在你想“只”省略前N位，这意味着所有后续计算步骤所依赖的数据是不同的，所以所有的步骤都必须重做。所以你必须至少放弃今天好的散列函数的这种强度。 – PlasmaHH

你描述的，是非常接近的重复数据删除存储使用的基本方法。

重复数据删除系统中，我们通常使用Rabin's fingerprinting方法作为快速滚动哈希函数。然而，虽然拉宾指纹是良好的和很好理解的碰撞特性，但它不是密码安全的，即有将是是碰撞。检查例如如何Bentley et al. used such a method in their compression method。问题是如果和多少碰撞你可以容忍。如果你能忍受偶尔的碰撞，一个好的拉宾指纹实现可能是一个好主意。好的实现可以为每个内核每秒处理超过200 MB的内存。

我不知道有任何方法几乎没有碰撞（又名密码保护）和滚动在同一时间。作为PlasmaHH，我非常怀疑这实际上是可能的。

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

来源

2013-01-11 15:33:12 dmeister

谢谢。我会尝试拉宾指纹方法，希望它会足够好。我真的不想错过比我更多的重复项目（因为大块大小）。但是，碰撞时磁盘访问的成本可能会低于哈希性能增益。 – bzaborow

Rabin-Karp方法确实执行得很好，并且在64位算法中实现时，对于此任务而言具有足够罕见的冲突。万分感谢！ – bzaborow

上rolling hashes维基百科文章具有ngramhashing链接它实现在C++中的几个不同的技术，包括：

随机卡普-拉宾（有时称为拉宾-卡普）
通过循环多项式哈希（也称为Buzhash）
通过不可约多项式哈希

（也可在GitHub）

来源

2013-01-11 15:06:41 Joni

有用的链接，至少我可以尝试现有的实现。谢谢！ – bzaborow

高效的'滚动/移动散列'计算（如移动平均）

回答

相关问题