13

我正在寻找使用滚动散列函数，这样我就可以对一个非常大的字符串的 n-gram 进行散列。

例如：

“stackoverflow”，分成 5 克是：

“stack”、“tacko”、“ackov”、“ckove”、“kover”、“overf”、“verfl”、“erflo”、“rflow”

这对于滚动散列函数是理想的，因为在我计算了第一个 n-gram 散列之后，以下的计算相对便宜，因为我只需删除第一个散列的第一个字母并添加第二个散列的新的最后一个字母.

我知道通常这个哈希函数生成为：

H = c 1 a k - 1 + c 2 a k - 2 + c 3 a k - 3 + ... + c k 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 作为我的素数。我的哈希值是否会溢出有关系吗？我认为这是可取的，但我不确定。

这似乎是解决这个问题的正确方法吗？

4

3 回答 3

1

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

您使用模运算来防止您的整数在每次操作后溢出。

初始设置：

  • c = 文本（“堆栈溢出”）
  • M =“n-gram”的长度
  • d = 字母的大小 (256)
  • q = 一个大素数，这样 (d+1)*q 就不会溢出（8355967 可能是一个不错的选择）
  • dM = d M-1 mod q

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

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 的算法书籍之一以获取详细信息、更少的错误和更好的描述。:)

于 2010-02-22T23:44:04.500 回答
0

不确定您的目标是什么，但如果您想提高性能，使用 math.pow 的成本将远远超过计算滚动哈希值所节省的成本。

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

于 2010-02-24T21:14:00.917 回答
0

据我了解，这是一个功能最小化：

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

哪里maxchar = 62（对于A-Za-z0-9）。我刚刚通过 Excel 计算了它（确切地说是 OO Calc）:) 并且它找到的最大 A 是76, 或73, 对于素数。

于 2010-02-22T21:43:42.053 回答