Monte-Carlo Rabin-Karp

When we hash a value by dividing it by a number, the resulting hash code will be some number from 0 up to (but excluding) that number itself. So if our chosen prime number is 613, the hash code will be some number from 0 through 612. Put another way, there are 613 possibilities as to what the final hash code will be.

It turns out that when a haystack window does not match the needle, there’s still a 1 out of 613 chance that their hash codes will match. If we choose a larger prime number, such as 7841, then each haystack window has a 1 in 7,841 chance of being incorrectly identified as a match to the needle.

Now, if our haystack is small relative to our needle so that we only have a few haystack windows, we’re unlikely to encounter any mistaken matches. For example, if each haystack window has a 1 in 7,841 chance of being a mistaken match, if we have 3 haystack windows to check, there will be a 3 in 7,841 chance that we’ll encounter a mistaken match over the course of our entire search.

As our haystack grows, though, the odds of a mistake increase. If we have, say, 8,000 haystack windows, then there’s a decent chance that we will come across an incorrectly identified match at some point in our search.

The trick for keeping the probability of a mistake low is to select a high prime number. If we could pull off the math to select an ideal prime number like this, it becomes significantly improbable that a mistake will occur.

And this, my friends, is what makes Rabin-Karp a Monte Carlo algorithm. Recall that the whole point of Rabin-Karp was to make substring search much faster than the brute-force approach. To accomplish this, though, we end up accepting a small possibility that the algorithm will not produce an accurate result. This is precisely what Monte Carlo algorithms do: they sacrifice accuracy for the sake of increasing speed. If we ensure that our prime number is high enough, we’ll end up with a speedy substring search with a low chance of error.

It emerges that if our app isn’t going to handle long needles, we can avoid collisions altogether if we use base 26 and do not use division hashing. It’s only if we need to be concerned with long needles that end up in this situation where two different strings may end up with the same hash code.

As things stand now, the current variant of Rabin-Karp is a clever Monte Carlo algorithm. But there’s a plot twist.