在 PHP 中快速实现滚动哈希

Question

我已经在 PHP 中实现了 Adler32 滚动哈希，但由于ord非常慢（在我的开发机器上每秒大约 1MB）来获取字符串中吟唱者的整数值，这个解决方案不适用于 100MB+ 文件。

PHP 的 mhash 函数可以非常快速地计算 adler32（在我的开发机器上每秒 120MB）。然而，mhash似乎不支持adler32的滚动性质，所以你必须在滚动窗口移动时计算一个全新的adler32，而不仅仅是重新计算实际更改的两个字节的哈希。

我不依赖于 adler32 算法，我只需要一个非常快速的 PHP 滚动哈希。

Answer 1

调用 Adler-32 A 的低两个字节和高两个字节 B，其中这是序列 {x1， x2， ...， xn} 的 Adler-32。

要得到 {x2， ...， xn} 的 Adler-32，请从 A 中减去 x1，模 65521，然后从 B 中减去 n * x1 + 1，再次取模 65521。

请注意，如果您的窗口大小 n 恰好是 65521 的倍数，那么您可以从 B 中减去 1（模 65521）。 因此，如果可以的话，这可能是一个不错的窗口大小。 另请注意，如果 n 大于 65521，则可以将 x1 乘以 （n 模 65521）。 如果 n 是一个常数，则可以提前执行该模运算。

（请注意，C 和 PHP 中的%运算符不是模运算，而是余数运算。 所以你需要注意负数。

Answer 2

使用 unpack，您可以获取一个字符的整数值数组作为数组。请注意，索引从 1 开始，而不是从 0 开始。

例：

$contents = "addadda";
$ords = array_values(unpack("C*", $contents)); // make 0-based array 
$a = 1; $b = 0; // hash low and high words
$len = 4; // the window length
foreach ($ords as $i => $ord) {
    if ($i < $len) {
        $a = ($a + $ord) % 65521;
        $b = ($b + $a) % 65521;
    } else {
        $removed = $ords[$i - $len];
        $a = ($a + $ord - $removed + 65521) % 65521;
        $b = ($b + $a - 1 - $len * $removed + 65521) % 65521;
    }
    if ($i >= $len - 1) {
        echo $i - $len + 1, "..", $i, ": ",
            substr($contents, $i - $len + 1, $len), " => ",
            $b * 65536 + $a, "n";
    }
}

结果：

0..3: adda => 64815499
1..4: ddad => 65405326
2..5: dadd => 65208718
3..6: adda => 64815499