algorithm - rabin-karp 如何在变长分块中选择断点？

Question

我了解 rabin-karp 算法及其在字符串搜索中的用法。我不太明白的是它如何动态地将文件分割成可变长度的块。据说在每个字节偏移处计算一个小数据字节窗口（例如：48 字节）的散列，并且当散列的最后 N（例如：13）位为零时，块边界（称为断点）是零。这为您提供了 2^N = 2^13 = 8192 = 8 KB 的平均块大小。问题：

1. rabin-karp 滚动哈希是否从前 48 个字节开始，然后每次滚动一个字节。
2. 如果是这样，即使使用简单的哈希函数来计算大文件是否太多？
3. 给定不可预测的数据，如何在大块大小限制内使散列的 N 位为零？

Answer 1

1. 是的，滑动窗口是固定大小的，一个字节一个字节地向前移动。
2. 哈希函数具有 O(n) 复杂度，在每一步中它只添加（并且可能移位位）下一个字节并减去窗口中原来的第一个字节，这是 Rabin 哈希的核心方法。
3. 它实际上取决于哈希函数。卡盘尺寸的分布可能不同。为了减少块大小的可变性，提出了两个阈值，两个除数算法（TTTD）。您还可以从学术研究论文中找到该线程的一些进展。