Rabin-Karp算法与重叠的关系

Question

许多重复库或应用程序应用Rabin滚动散列算法快速散列，从文件二进制文件中剪切块。

我的问题是，为什么Rabin算法会经常用于切割块呢？

我知道它是快速滚动散列算法，但我的问题更基本。

会有很多种方法来减少一小块。

例如，将一个字节(没有mod操作)与值进行比较，以减少一个块，这将导致平均256个字节块。

将9位进行比较，平均得到512字节块，等等。

如果没有散列结果，就像Rabin这样的滚动哈希算法，那么仅仅比较最后几个比特，会不会更快呢？

Answer 1

对于可变大小的分块处理，我们有两个步骤：

1. 块状
2. 索引

Rabin Karp滚动散列是一种将文件切割成不同大小片段的分块算法。然后，我们需要索引/查询数据块，因为我们做了dedupe。一般的方法是计算块的哈希值，并以哈希作为键存储块。利用Rabin Karp算法，由于我们同时得到了哈希和数据块，所以一切都是直接的。

您提到了比较最后几位的方法可以帮助将文件分割成几个部分，但是如果要对这些块进行索引，我们如何才能得到密钥呢？所以你必须计算哈希。

希望这能帮上忙。