Быстрое внедрение скользящего хэша в PHP

Question

Я реализовал хэш Adler32 в PHP, но потому что ord Это настолько медленно (около 1 МБ в секунду на моем компьютере разработчика), чтобы получить целочисленные значения чантеров в строке, это решение не работает для файлов размером более 100 МБ.

Функция PHP mhash может очень быстро вычислить adler32 (120 МБ в секунду на моем компьютере разработчика). Однако mhash, похоже, не поддерживает скользящую природу adler32, поэтому вам нужно рассчитать совершенно новый adler32 по мере перемещения скользящего окна, а не просто пересчитать хеш для двух байтов, которые фактически изменились.

Я не привязан к алгоритму adler32, мне просто нужен очень быстрый скользящий хеш в PHP.

Answer 1

Вызовите два младших байта Adler-32 A и старшие два байта B, где это Adler-32 последовательности {x1, x2,..., xn}.

Чтобы получить Adler-32 из {x2,..., xn}, вычтите x1 из A, по модулю 65521 и вычтите n * x1 + 1 из B, снова по модулю 65521.

Обратите внимание: если размер окна n кратен 65521, вы можете просто вычесть одно из B (по модулю 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