11
$\begingroup$

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations are module $2^w$, where $w$ is the width of a machine word). Why is it important for $b$ to be prime?

$\endgroup$
0
13
$\begingroup$

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring.

The efficiency of the algorithm depends on the ability to compute $h(S[r+1\ldots s+1])$ efficiently from $h(S[r\ldots s])$. This is called a "rolling hash". Note that any efficient rolling hash function will do, and it's still Rabin-Karp. The question that you're asking about is one particular choice of hash function, where you use:

$$h(S[r\ldots s]) = \sum_{i=r}^s S[i]\, p^{s-i} \bmod q$$

where $p$ is a prime number with roughly the same order of magnitude as the size of the character set, and $q$ is another prime number which defines the cardinality of the range of the hash function, typically of the same order of magnitude as a machine word divided by the character set size. If I'm reading it correctly, you're asking why $q$ has to be prime.

In fact, this is a more general question. In a lot of the old (and current) literature on hashing, the advice is that the hash function should be taken modulo a prime number (e.g. hash tables should have a prime size).

For a hash function to be as useful as possible, its range needs to be relatively uniform, even when its domain is not. Natural language text (say) doesn't have a uniform frequency distribution, but hash values should be.

If $q$ is a prime number, then a lot of other numbers are relatively prime to it, and in particular, the sum (especially if $p$ is also prime!). This makes the frequency distribution of the hash values more uniform, even though the hash function is relatively weak.

It's important to understand that we do this because the hash function is weak. If the hash function were stronger, taking the remainder when divided by a prime would not be necessary; you could, for example, take the remainder when divided by a power of two, which would be a much cheaper bit mask operation. However, it's hard to design strong rolling hash functions which are cheap enough to be done for every input character in the Rabin-Karp algorithm.

Something that's worth pointing out that this "remainder of a prime" technique used to be common in many hashing applications, but this advice is inadvisable on modern hardware. It advice made sense once upon a time, because while final integer division instruction was always expensive, so were the operations that you used to compute your hash function, such as integer multiplication. On modern CPUs, it is much more expensive to do an integer division even than an integer multiplication.

Modern carry-save adder multipliers are fully pipelined, so you can have several such instructions being executed at once. Modern dividers use the SPH or Goldschmidt algorithms, which are multi-cycle and impossible to pipeline. Goldschmidt dividers also tie up the multiplication unit, making the performance hit even greater.

I've had programs where this division instruction was the bottleneck, and the annoying part was that it was hidden inside the standard library.

On a modern CPU, it is worth using a more sophisticated hash function built out of fully pipelineable operations (e.g. multiplies or even table look-ups) and using hash tables which are powers of two, so the modulo operation is a bit mask. Do anything to avoid that division operation.

Just not for Rabin-Karp.

$\endgroup$
1
$\begingroup$

Pseudonym's answer is excellent, but there's some additional points worth mentioning. The generalized version of the hash algorithm used in the RabinKarp document is;

$$h(S[0…s])=\sum_{i=0}^{s}p^iS[i] \mod q$$

This is typically implemented as;

h = 0 # Sometimes initialized to a seed value instead.
for i in range(s):
  h = (p * h + S[i]) % q

Note that this algorithm has a lot in common with simple LCG random number generators, hence its surprisingly good almost randomly distributed output. The c "increment" part of the LCG is just replaced with S[i] byte value. This suggests that good values for p and q should probably match the criteria for good a and m values for an LCG generator, but the most important thing is that they are relatively prime, as this prevents $(p^i\mod q)$ from cycling/repeating values prematurely for different i values. When they are relatively prime, $p^i\mod q$ is a different value for every value of i in 0..q-1.

This is probably the core part of the answer to the original question; when mutiplying/dividing numbers, primes are less likely hit cycles/alignments. A number that has many prime factors can be evenly divided by many other different numbers; every different combination of its prime factors is another divisor, with a modulus result of zero. These lead to more repetitions/cycles/matches when operating with these numbers.

Although people often talk about making q prime, this reduces the effective range of the hash values for the number of bits used, and can require an expensive division operation. If you are lucky the largest prime in N bits is very close to $2^N$ so it doesn't waste much of the available hash-space, and the mod operation can be implemented cheaply using a combination of shifts and adds as is done in zlib's adler32 implementation. However, even adler32's small sacrifice of 15 values past the prime has been shown to be not worth the extra benefits of using a prime modulus value.

Another common value for q is $(2^N -1)$, which only wastes one hash value in $2^N$ bits and mod can be efficiently computed by just adding the carry-over bits past N back into the hash. It's not always prime, but it's often got very few prime factors so it's easy to find a p that is relatively prime. Importantly it's relatively prime to $2^N$, so it avoids many nasty alignments when working with binary numbers. The one omitted hash value (all 1's, or sometimes remapped as all 0's) can be used as a special sentinel value for "empty hash bucket". It turns out this is equivalent to 1's complement arithmetic, which is often used in hash algorithms like Fletcher for this reason.

The original question's variant of this is one where q is effectively $2^N$ for N bits of hash, and it's not usually explicitly mentioned because you get it for free when using N-bit arithmetic. In this case it's important that p be odd so it's relatively prime to $2^N$. It's not strictly necessary that p be a prime, but to avoid nasty degenerate cases in your data it's better if it has very few prime factors. The LCG recommendations also suggest $(p-1)$ be divisible by 4. In my experience it helps if it has a good distribution of 1'S over the full $2^N$ hash size to spread the bits widely over the hash each iteration. Note that most recommended LCG multiplier values are NOT prime, but they do have few prime factors.

In my experience 0x8104225 is good, but 0x41c64e6d is another widely used LCG multiplier that works well.

Note that Gear is also similar to this but defies the rule of "p should be odd for $q=2^N$" and actually uses $p=2$ implemented as a left-shift. It does this to intentionally take advantage of the property that this weakens the hash by "expiring the older bytes" out of the hash, since $2^iS[i]\mod 2^N=0$ for $i\geq N$, avoiding the need for keeping a sliding window to calculate the rolling sum of the last N bytes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.