1
$\begingroup$

The Rabin–Karp algorithm uses a rolling hash function to find a substring matching a pattern:

$$ H = c_1a^{k-1} + c_2 a^{k-2} + c_3 a^{k-3} + \cdots + c_k a^0, $$

where $a$ is a constant, $c_1\ldots c_k$ are the input characters, and $k$ is the number of characters there are in the pattern we are trying to find in the main string.

I know this function makes it easy to recompute the hash at the next character using the previous one. What is the basis for using this function which looks like we're converting to a number system - does that guarantee uniqueness? Maybe I'm asking an axiomatic question - is the expression of a number in a base unique given digits?

$\endgroup$
3
  • $\begingroup$ I'm unclear what you're asking. What do you mean by "the basis"? I'm not sure what you mean by "expression of a number in a base unique given digits". Can you formulate your question more precisely? $\endgroup$
    – D.W.
    Commented Dec 31, 2021 at 7:21
  • $\begingroup$ en.wikipedia.org/wiki/Rolling_hash#Polynomial_rolling_hash $\endgroup$
    – D.W.
    Commented Dec 31, 2021 at 7:23
  • 5
    $\begingroup$ There is no guarantee that the hash value (which is $H$ reduced modulo some $n$) identifies characters uniquely — indeed, in general this is impossible to guarantee, since the range of $H$ is finite. However, in practice it might perform well in most cases. $\endgroup$ Commented Dec 31, 2021 at 9:43

2 Answers 2

1
$\begingroup$

What is the basis for using this function which looks like we're converting to a number system - does that guarantee uniqueness?

No, it's not possible to guarantee uniqueness if H is of a fixed size and the needle is of unbounded length. But we want something "close" to uniqueness; different strings shouldn't have the same hash "more often than necessary", because every false match means extra work. To satisify that,

  1. Every character of the input should count towards H. No problem with the polynomial construction here.
  2. H should depend on ordering. If we let a = 1 then we would have a very cheap hash function, but H("santa") would equal H("satan"), resulting in excess false positives. By multiplying each position by a different power of a, permutations of a given string will (usually) have different hashes.
  3. The available hash space should be covered evenly. This function isn't perfect, but it's close enough as long as the base and modulus are chosen sensibly and the needle isn't too short (if the needle is very short, another algorithm would be better anyhow).

At the same time, the hash has to be cheap enough to compute that it's worth bothering with in the first place. That means it should have the rolling-hash property (the new hash can be computed given the previous hash and the next character) and it should use a small number of simple operations. For the given hash function, the update operation is a couple of multiplies and a couple of adds (and usually a modulus, which is missing from your description), which is about as cheap as you can possibly get and still have a suitable hash function. If updating the hash was too expensive, then it would be more efficient to just memcmp every possible offset.

$\endgroup$
0
$\begingroup$

The hash need not be unique. From wikipedia:

The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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