Fast implementation of Rolling hash

Question

I need a Rolling hash to search for patterns in a file. (I am trying to use the rabin-Karp string search algorithm).

I understand how a good hash works and how a good rolling hash should work but I am unable to figure out how to efficiently implement the 'divide' (or inverse multiplication) when rolling the hash. I also read rsync uses rolling version of adler32 but that doesn't looks like a random enough hash.

Ideally it will be great if you can point me to an optimized C/C++ implementation, but any pointers in the right direction will help.

Answer 1

I wrote this a while back. Its written in c# but that is very close to c, you will only have to add a couple of parameters. This should work but I haven't test this version, I removed a couple lines that would ignore case or non-word chars. I hope this helps

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;
}

Answer 2

Cipher's "prime base" idea should work decently - though the solution he posted looks a bit sketchy.

I don't think there's any need for inverse multiplication in this method. Here's my solution:

Say the string we currently have hashed is "abc", and we want to append "d" and remove "a".

Just like Cipher, my basic hash algorithm will be:

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;
}

Now, to implement sliding:

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

We'd like to add something at the end and remove the first value, so

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

First we can add the last letter:

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

Then simply subtract the first character:

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

An important note: you have to be careful about overflow. You can choose to just let it overflow unsigned int, but I think it's much more prone to collision (but also faster!)

Here's my implementation:

#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;
}

Answer 3

Some pointers for a fast implementation:

1. Avoid modulo n operation (% in C like languages) use mask n - 1, where n is 2^k, include the operations for the hash table lookup. Yes, it's possible to produce good hash with a non-prime moduli.
2. Pick multipliers and exponents with good figures of merit, see this paper for details.