快速实现滚动哈希

Question

我需要一个滚动哈希来在文件中搜索模式（我正在尝试使用Rabin-Karp字符串搜索算法）。

我了解什么是好的哈希函数以及好的滚动哈希函数应该如何工作，但我不知道如何有效地实现除法运算（或逆乘法），以便在滚动哈希时进行操作。我也读到rsync使用滚动版本的adler32，但那似乎不够随机。

理想情况下，如果你能指向一个经过优化的C/C++实现就最好了，但任何指向正确方向的指针都将有所帮助。

- Sachin

---

对于那些通过搜索滚动哈希和乘法逆元到达这里的人，如果您的滚动哈希实现需要支持可变长度，则只需要进行除法运算（或使用乘法逆元），如果您想要执行Rabin-Karp，则可能不需要此操作。有关如何在此视频中使用逆元的一些指针以及我的Python尝试实现。 - Cedric

Answer 1

Cipher的“主要基础”想法应该能够很好地工作 - 尽管他发布的解决方案看起来有点可疑。

我认为这种方法不需要逆乘法。以下是我的解决方案：

假设我们当前已经哈希了字符串"abc"，我们想要添加"d"并删除"a"。

就像Cipher一样，我的基本哈希算法将是：

unsigned hash(const string& s)
{
    unsigned ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret *= PRIME_BASE; //shift over by one
        ret += s[i]; //add the current char
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

现在，为了实现滑动效果：

hash1 = [0]*base^(n-1) + [1]*base^(n-2) + ... + [n-1]

我们需要在末尾添加一些内容并删除第一个值，因此：

hash2 = [1]*base^(n-1) + [2]*base^(n-2) + ... + [n]

首先，我们可以添加最后一个字母：

hash2 = (hash1 * PRIME_BASE) + newchar;
=> [0]*base^n + [1]*base^(n-1) + ... + [n-1]*base + [n]

然后简单地减去第一个字符：

hash2 -= firstchar * pow(base, n);
=> [1]*base^(n-1) + ... + [n]

重要提示：您需要注意溢出问题。您可以选择让它溢出无符号整数，但我认为这更容易发生冲突（但速度更快！）

以下是我的实现：

#include <iostream>
#include <string>
using namespace std;

const unsigned PRIME_BASE = 257;
const unsigned PRIME_MOD = 1000000007;

unsigned hash(const string& s)
{
    long long ret = 0;
    for (int i = 0; i < s.size(); i++)
    {
        ret = ret*PRIME_BASE + s[i];
        ret %= PRIME_MOD; //don't overflow
    }
    return ret;
}

int rabin_karp(const string& needle, const string& haystack)
{
    //I'm using long longs to avoid overflow
    long long hash1 = hash(needle);
    long long hash2 = 0;

    //you could use exponentiation by squaring for extra speed
    long long power = 1;
    for (int i = 0; i < needle.size(); i++)
        power = (power * PRIME_BASE) % PRIME_MOD;

    for (int i = 0; i < haystack.size(); i++)
    {
        //add the last letter
        hash2 = hash2*PRIME_BASE + haystack[i];
        hash2 %= PRIME_MOD;

        //remove the first character, if needed
        if (i >= needle.size())
        {
            hash2 -= power * haystack[i-needle.size()] % PRIME_MOD;
            if (hash2 < 0) //negative can be made positive with mod
                hash2 += PRIME_MOD;
        }

        //match?
        if (i >= needle.size()-1 && hash1 == hash2)
            return i - (needle.size()-1);
    }

    return -1;
}

int main()
{
    cout << rabin_karp("waldo", "willy werther warhol wendy --> waldo <--") << endl;
}

- v3

---

@社区 为什么MOD应该是质数？你能否给我一些可以查阅的来源？因为在这里：http://stackoverflow.com/questions/5835946/how-to-reduce-a-bigger-string-in-smaller-string-in-c-probably-by-hashing/5836274#5836274 我们就这个话题进行了大量讨论，但是无法达成一致意见。 - Mihran Hovsepyan

Answer 2

快速实现的一些指针：

1. 避免使用模数 n 操作（C 语言中的 %），使用掩码 n - 1，其中n是2的k次方，包括哈希表查找操作。是的，可以使用非质数的模数产生良好的哈希。
2. 选择具有良好特性的乘数和指数，详见这篇论文。

- obecalp

Answer 3

我之前写过这个程序。它是用C#编写的，但是C#非常接近C语言，你只需要添加一些参数即可。这个应该可以工作，但我还没有测试过这个版本，我删除了一些忽略大小写或非单词字符的代码行。希望这可以帮到你。

private const int primeBase = 101;
//primeBase^2*[0]+primeBase^1*[1]+primeBase^0*[2]
//==
//primeBase*(primeBase*[0]+[1])+[2]
public static int primeRollingHash(String input, int start, int end)
{
    int acc = 0;
    for (int i = start; i <= end; i++)
    {
        char c = input[i];
        acc *= primeBase;
        acc += c;
    }
    return acc;
}

public static int primeRollingHash(String input)
{
    return primeRollingHash(input, 0, input.Length - 1);
}

public static int rollHashRight(int currentHashValue, String input, 
                                int start, int newEnd)
{
    if (newEnd == input.Length)
        return currentHashValue;
    int length = newEnd - start - 1;
    int multiplier = primeBase;
    char newChar = input[newEnd];
    int firstValue = input[start];
    if(length>0)
        firstValue *= length * primeBase;
    return (currentHashValue - firstValue) * multiplier + newChar;
}

- Cipher