0

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

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

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

4

2 回答 2

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中减去一个（模 65521）。因此，如果可以的话，这可能是一个不错的选择窗口大小。另请注意，如果n大于 65521，则您可以将x1乘以( n模 65521)。如果n是一个常数，您可以提前进行模运算。

（请注意，%C 和 PHP 中的运算符不是取模运算，而是取余运算。因此您需要注意负数。）

于 2015-06-15T03:14:30.667 回答
0

使用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
于 2021-09-03T09:47:09.113 回答