rabin-karp 如何在可变长度分块中选择断点？
how does rabin-karp choose breakpoint in variable-length chunking?
我了解 rabin-karp 算法及其在字符串搜索中的用法。我不太明白的是它如何动态地将文件分割成可变长度的块。
据说在每个字节偏移量处计算一小 window 个数据字节（例如：48 字节）的散列，并且块边界（称为断点）是数据块的最后 N（例如：13）位哈希为零。这为您提供了 2^N = 2^13 = 8192 = 8 KB 的平均块大小。
问题：
- rabin-karp 滚动哈希是否从前 48 个字节开始，然后每次滚动一个字节。
- 如果是这样，即使使用简单的散列函数计算大文件是否太多？
- 给定不可预测的数据，如何在大块大小限制内使 N 位哈希为零？
- 是的，滑动window是固定大小的，逐字节向前移动。
- 散列函数的复杂度为O(n)，在window中每一步只添加（并可能移位）下一个字节和减去原来的第一个字节，这是散列函数的核心方法拉宾散列。
- 这实际上取决于哈希函数。卡盘尺寸的分布可能不同。为了减少块大小的可变性，the Two Thresholds, Two Divisors Algorithm (TTTD) 被提出。您还可以从学术研究论文中找到此主题的一些进展。
我了解 rabin-karp 算法及其在字符串搜索中的用法。我不太明白的是它如何动态地将文件分割成可变长度的块。 据说在每个字节偏移量处计算一小 window 个数据字节（例如：48 字节）的散列，并且块边界（称为断点）是数据块的最后 N（例如：13）位哈希为零。这为您提供了 2^N = 2^13 = 8192 = 8 KB 的平均块大小。 问题：
- rabin-karp 滚动哈希是否从前 48 个字节开始，然后每次滚动一个字节。
- 如果是这样，即使使用简单的散列函数计算大文件是否太多？
- 给定不可预测的数据，如何在大块大小限制内使 N 位哈希为零？
- 是的，滑动window是固定大小的，逐字节向前移动。
- 散列函数的复杂度为O(n)，在window中每一步只添加（并可能移位）下一个字节和减去原来的第一个字节，这是散列函数的核心方法拉宾散列。
- 这实际上取决于哈希函数。卡盘尺寸的分布可能不同。为了减少块大小的可变性，the Two Thresholds, Two Divisors Algorithm (TTTD) 被提出。您还可以从学术研究论文中找到此主题的一些进展。