Rabin-Karp字符串搜索算法中使用的滚动哈希函数是否有可用的实现？

Question

我想使用滚动哈希函数来获取一个非常大字符串的n-gram哈希值。

例如:

"stackoverflow"，分成5个字母组合，则为：

"stack", "tacko", "ackov", "ckove", "kover", "overf", "verfl", "erflo", "rflow"

这种方法对于滚动哈希函数非常理想，因为在计算第一个n-gram哈希值之后，接下来的哈希值相对便宜，只需要删除第一个哈希值的第一个字符并添加第二个哈希值的新的最后一个字符即可。

我知道一般来说这个哈希函数是生成为：

H = c1a^(k − 1) + c2a^(k − 2) + c3a^(k − 3) + ... + ck*a^0

其中a是一个常数，c1, …, ck是输入字符。

如果您在Rabin-Karp字符串搜索算法上跟随此链接，则说明"a"通常是某个大质数。

我希望我的哈希值存储在32位整数中，那么“a”应该有多大的质数才能避免整数溢出？

是否存在我可以使用的此哈希函数的现有实现？

---

这是我创建的一个实现：

public class hash2
{

    public int prime = 101;

    public int hash(String text)
    {
        int hash = 0;

        for(int i = 0; i < text.length(); i++)
        {
            char c = text.charAt(i);
            hash += c * (int) (Math.pow(prime, text.length() - 1 - i));
        }

        return hash;
    }

    public int rollHash(int previousHash, String previousText, String currentText)
    {

        char firstChar = previousText.charAt(0);
        char lastChar = currentText.charAt(currentText.length() - 1);

        int firstCharHash = firstChar * (int) (Math.pow(prime, previousText.length() - 1));
        int hash = (previousHash - firstCharHash) * prime + lastChar;

        return hash;
    }

    public static void main(String[] args)
    {
        hash2 hashify = new hash2();

        int firstHash = hashify.hash("mydog");
        System.out.println(firstHash);
        System.out.println(hashify.hash("ydogr"));
        System.out.println(hashify.rollHash(firstHash, "mydog", "ydogr"));
    }

}

我使用101作为我的质数。如果我的哈希值溢出，是否会有影响？我觉得这是可取的，但我不确定。

这样做是否正确？

- c14ppy

---

为什么这个应用程序的质数与“正常”的字符串哈希码生成有所不同？ - CPerkins

这个算法非常简单，从伪代码实现起来相当容易。你尝试过自己编码吗？ - MAK

Answer 1

我记得有一个稍微不同的实现，似乎来自Sedgewick的算法书之一（它还包含示例代码-尝试查找）。这里是一个调整为32位整数的摘要：

您可以使用模算术来防止每次操作后整数溢出。

最初设置：

• c = 文本（“stackoverflow”）
• M = “n-gram”的长度
• d = 您的字母表大小（256）
• q = 一个大质数，使得（d + 1）* q不会溢出（8355967可能是一个不错的选择）
• dM = d ^M-1 mod q

首先计算第一个n-gram的哈希值：

h = 0
for i from 1 to M:
  h = (h*d + c[i]) mod q

对于每个接下来的n-gram：

for i from 1 to lenght(c)-M:
  // first subtract the oldest character
  h = (h + d*q - c[i]*dM) mod q

  // then add the next character
  h = (h*d + c[i+M]) mod q

你必须在减去最旧字符之前添加d*q的原因是，由于先前的模操作引起的小值可能导致负值。

错误可能存在，但我认为你应该理解了。尝试查找Sedgewick的算法书以获取详细信息、更少的错误和更好的描述。 :)

- stmax

---

什么是包含错误？如果我这样做，会遇到“负值”吗？如何防止它？ - Nitish Upreti

@Myth17：我是说你应该小心使用我的（伪）代码，因为它可能包含错误/我还没有进行全面测试。 - stmax

Rabin-Karp字符串搜索算法中使用的滚动哈希应该允许计算下一个哈希值：**s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]**。您提供的算法无法用于此目的。 - Thomas C. G. de Vilhena

Answer 2

据我理解，这是一个函数最小化问题：

2^31 - sum (maxchar) * A^kx

其中maxchar = 62（对于A-Za-z0-9）。我刚刚通过Excel（确切地说是OO Calc）计算出来的，最大的A值是76，或者是一个质数的73。

- Igor Artamonov

Answer 3

不确定你在这里的目的是什么，但如果你想提高性能，使用math.pow会比计算滚动哈希值节省的更多。

我建议你从简单和高效的方法开始，很可能会发现它已经足够快了。

- Peter Lawrey

---

计算幂的最快方法？ - Nitish Upreti

这取决于情况。通常来说，普通乘法更快。 - Peter Lawrey