0

我目前正在阅读 Rabin Karp 算法，作为其中的一部分，我需要了解字符串多项式哈希。据我了解，字符串的哈希值由以下公式给出：

hash = ( char_0_val * p^0 + char_1_val * p^1 + ... + char_n_val ^ p^n ) mod m

在哪里：

  • char_i_val：是字符的整数值加 1string[i]-'a' + 1
  • p 是大于字符集的素数
  • m 是一个大素数

网站 cp-algorithms 有以下关于该主题的条目。他们说写上面的代码如下：

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
        p_pow = (p_pow * p) % m;
    }
    return hash_value;
}

我理解程序试图做什么，但我不明白为什么它是正确的。

我的问题

我无法理解为什么上面的代码是正确的。自从我做任何模块化数学以来已经有很长时间了。在网上搜索后，我看到我们有以下模加和模乘的公式：

a+b (mod m) = (a%m + b%m)%m
a*b (mod m) = (a%m * b%m)%m

基于以上内容，代码不应该如下吗？

long long compute_hash(string const& s) {
    const int p = 31;
    const int m = 1e9 + 9;
    long long hash_value = 0;
    long long p_pow = 1;
    for (char c : s) {
        int char_value = (c - 'a' + 1);
        hash_value = (hash_value%m + ((char_value%m * p_pow%m)%m)%m ) % m;
        p_pow = (p_pow%m * p%m) % m;
    }
    return hash_value;
}

我错过了什么？理想情况下，我正在寻求代码的细分以及为什么第一个版本是正确的解释。

4

1 回答 1

1

在数学上，没有理由减少中间结果模数m。

在操作上，有几个非常密切相关的原因要这样做：

  1. 保持数字足够小，以便可以有效地表示它们。
  2. 保持数字足够小，以使对它们的操作不会溢出。

所以让我们看看一些数量，看看是否需要减少它们。

  • p被定义为小于 的某个值m，所以p % m == p.
  • p_pow并且在计算时hash_value已经对m它们进行了模减，m再次对它们进行模减少将无济于事。
  • char_value最多为 26，这已经小于m.
  • char_value * p_pow最多26 * (m - 1)。这可以而且通常会超过m. 所以减少它模数m会做一些事情。但是还是可以延迟的，因为下一步还是“安全的”（没有溢出）
  • char_value * p_pow + hash_value仍然最多27 * (m - 1)仍然远小于 2 63 -1 （ a 的最大值long long，见下文为什么我假设 along long是 64 位），所以还没有问题。m 在加法后减少模数是可以的。

作为奖励，循环实际上可以在需要减少modulo之前执行 (2 63 -1) / (27 * (m - 1)) 迭代。那是超过 3.41 亿次迭代！因此，对于大多数实际目的，您可以删除第一个and 。hash_valuem% mreturn hash_value % m;

我在这个计算中使用了 2 63 -1 因为p_pow = (p_pow * p) % m要求long long是 64 位类型（或者，假设是 36 位或更高的奇异大小）。如果它是 32 位类型（这在技术上是允许的，但现在很少见），那么乘法可能会溢出，因为p_pow可能约为 10 亿，而 32 位类型不能容纳 310 亿。

顺便说一句，这个哈希函数专门用于只包含小写字母而没有其他内容的字符串。其他字符可能会导致负值，char_value这是一个坏消息，因为%C++ 中的余数运算符的工作方式是，对于负数，它不是“模运算符”（用词不当，C++ 规范没有这样称呼它）。可以编写一个非常相似的函数，它可以将任何字符串作为输入，这会稍微改变上面的分析，但不是定性的。

于 2022-01-19T13:17:14.173 回答