Converting Monte Carlo to Las Vegas

It turns out that it’s possible to convert certain Monte Carlo algorithms into Las Vegas algorithms. Not all Monte Carlo algorithms can be transformed this way, but Rabin-Karp is an algorithm that can. As a quick reminder, while a Monte Carlo algorithm is an algorithm that is definitely fast with a small probability of being incorrect, a Las Vegas algorithm is definitely correct, with a small chance of being slow.

Currently, Rabin-Karp will definitely be fast, but may be incorrect. We will now tweak the Rabin-Karp algorithm so that it becomes definitely correct, but will have a small chance of being slow.

This tweak is simple. We’ll add one additional step to the algorithm. Specifically, each time our algorithm finds matching hash codes, the algorithm will then do a “sanity check”; it will check both strings the old-fashioned way, character by character, to see if they’re the same.

If our needle is "cafe", and the haystack window is "clzr", which both result in the hash code 345, the algorithm will next do a sanity check by comparing all the characters of these two strings. In this case, the strings are not the same, so the algorithm will know that it hasn’t yet found a true match and will move on and continue to search the rest of the haystack for our needle. By performing this extra check, the computer will never report a false match. Rabin-Karp is now a Las Vegas algorithm since it will definitely be correct. And as we’ll now see, the odds of it being slow are also slim.

Each time the computer performs a sanity check to see if two strings are the same, this is relatively slow, as it has to comb through each character of both the haystack window and the needle. And if the algorithm ends up finding numerous instances of matching hash codes, this will require numerous sanity checks and will slow down the entire algorithm.

But here’s what’s interesting. What are the odds that the computer will slow down?

It turns out that the odds that the computer will perform a sanity check (when the two strings are indeed not the same) are the very same odds as the Monte Carlo version of Rabin-Karp not being correct.

That is, we noted that if the prime number is 7841, then each haystack window has a 1 in 7,841 chance of producing a false match. Well, in the Las Vegas form of the Rabin-Karp algorithm, there’s that same 1 in 7,841 chance that the algorithm will encounter a false match at this point and perform that “slow” sanity check. Even if the algorithm has to perform a handful of sanity checks here and there, we likely wouldn’t notice a slowdown. The algorithm will only slow down significantly if it’s finding many false matches and performing sanity checks over and over again. But again, this is unlikely if each haystack window has only a 1 in 7,841 chance of being a false match.

This new version of the Rabin-Karp algorithm is truly a Las Vegas algorithm. It is definitely correct and has only a small chance of being slow.

The moral of this story is that when you do encounter a Monte Carlo algorithm, see if there’s a way to transform it into a Las Vegas algorithm. This transformation isn’t always possible, but if it is, it might be worth considering.

At this point, we’re almost through with everything we need to know about Rabin-Karp. The final item is to work out the math of the hash function so that it uses division hashing. I happen to think that the math that follows is pretty cool, but if you’ve had enough math for the day, I understand completely. You can skip ahead to the end of the chapter if you prefer.

Modulus Magic

Here’s a quick summary of where we’re at right now.

Previously, our Rabin-Karp hash function simply treated each string as a base 26 number and converted the number into base 10. In truth, this worked pretty well. It was guaranteed to be both accurate and fast and certainly got the job done. The only problem was that it would not perform well in cases where the needle length is very long; the hash function would produce large numbers, which would slow down the entire algorithm. If not for the possibility of long needle lengths, I could have ended the chapter at that point.

But if we want to make the Rabin-Karp algorithm production-ready, we want it to perform well for long needle lengths. That’s why we introduced division hashing, which takes large numbers and cuts them down to size. Specifically, it ensures that the hash code will never be larger than the prime number we use in our division.

However, to pull this off, we’ll need to employ some clever mathematical tricks, and here’s why.

With division hashing, we first compute a long hash code, and then divide it by a prime number (and grab the remainder). But if the needle is super long, it will also take a long time to compute that long hash code. In other words, we’ll encounter a slowdown before even getting a chance to perform our division!

To spell this out even further, recall that before division hashing, we hashed the needle this way:

In this case, we multiply the "e" by 1, the "f" by b² (with “b” being 26), the "a" by b³, and the "c" by b⁴.

Imagine, now, that a needle was 500 characters long. This means we’d have to continue to compute each subsequent character by b⁵ and b⁶ all the way up to b⁵⁰⁰! Those end up being some pretty large numbers; for example, 10⁵⁰⁰ is 1 followed by 500 zeroes.

And therein lies the problem. Although computers are fast, they have their limitations, and computing large numbers can be significantly slow. To resolve this issue, we’re going to use some ideas from the field of modular arithmetic (math having to do with modulus operations) that some very clever people figured out and applied to our situation.

Let’s keep going with our "cafe" needle example. As we’ve seen, the initial hash code, before the prime number division, is 35286. To keep our examples simple, let’s continue to use a smallish prime number, namely, 613. When we compute 35286 % 613, we get 345.

But watch this amazing alternative way to compute the same result. It’s based on the mathematical properties of modulus operations. Here goes:

Here’s what’s going on in this computation. Instead of doing one single modular operation at the end of the hash function, we instead perform a modular operation for each and every character.

In this example, we start with the "c", grab its hash code (2), divide by the prime number, and grab the remainder. We then take that remainder (2), multiply it by the base (26), add the new character’s hash code (the hash code of "a" is 0), and perform the modulus operation again. We repeat this process for each character of our string.

Throughout this process, we never have to deal with any number larger than 613, and we still end up getting our desired result. Cool!

At this time, I’m not getting into why this modular arithmetic trick works. For now, let’s just marvel at the magic of math and take this at face value.

We can use the earlier trick as is to serve as our initial hash function. However, we do need to update our rolling hash function so that it incorporates this type of math magic as well.

Let’s go back to our example haystack. If we perform our modified initial hash function on the first haystack window of "deca", we get the hash code 314. We now need to perform our rolling hash function on the next window, which drops the initial "d" and introduces the character "f".

Here’s the math formula for the rolling hash function. I’ll admit, it’s a little involved. But it works! On the top, I show the actual formula, and on the bottom, I show how it applies to our example by plugging in all the numbers:

Here, we successfully compute the hash code for the new window "ecaf" based on the previous window of "deca". The result of 553 is the same result we’d get if we first converted "ecaf" to 71661 (by converting base 26 to base 10) and then dividing 71661 by our chosen prime number of 613. That is, 71661 % 613 = 553. However, with this fancy formula, we get the identical result without ever needing to first come up with the longish number of 71661.

Now, there’s one last bit of math that we need to perform. In the visual, take a look at the item shaped as a cloud. As you can see, this is a number computed by taking base^{(window_length-1)}, dividing by our prime number, and grabbing the remainder. I call the result of this computation the “drop place remainder.”

However, we once again run into a problem. If our window size is 500, this means that when we first compute base^{(window_length-1)}, we end up with a large number and a slow computation.

However, we can use modular math tricks to compute this number without ever having to wrangle with large numbers. Here’s how:

Here’s what the formula does:

We start with the number 1 and multiply it by the base (such as 26). We take the result, divide it by our chosen prime number, and grab the remainder. We then take this result and repeat the same process as many times as the length of the needle minus 1. (In this visual, we’re working with an example of where the needle length is 4.)

This computation produces the drop place remainder without ever producing a number larger than the prime number.

Whew! We’ve come to the conclusion of how Rabin-Karp works in all its gory detail. Let’s go ahead and code it all up.

Code Implementation: Las Vegas Rabin-Karp Substring Search with Division Hashing

Here’s the Python code for the Rabin-Karp algorithm with division hashing incorporated. Additionally, we’ve also transformed it into a Las Vegas algorithm:

The thrust of this code is similar to previous implementations. The difference, though, is that the hash functions themselves have now changed since they incorporate division hashing according to the formulas I described earlier.

Because the new hash formulas rely on a predetermined prime number, we set a global prime number variable at the top. I’ve set it to 613 to correspond to our previous examples, but in real life, this would likely be a larger number. In fact, you can also choose it randomly based on the Monte Carlo approach described in .

As part of the new division hashing approach, we precompute the drop_place_remainder within the find_needle function. Once we’ve computed the drop_place_remainder, we use it as part of the rolling_hash function. (The initial_hash function doesn’t need it.) As to the hash functions themselves, they’re more involved now, but track directly to the earlier formula descriptions.

The one final novelty of this implementation is that we transform the find_needle code into a Las Vegas algorithm with a single extra line of code. That is, if the needle and haystack window hash codes match, we do a sanity check and see if the two strings themselves are indeed identical:

The code haystack[i:(i + len(needle))] represents the haystack window. This sanity check takes the computer up to as many steps as there are characters in the strings. But again, the odds are low that we’ll have to perform many sanity checks.

Well, we’ve done it!

Division Hashing for Strings

In the previous chapter, I explained how division hashing works. However, I focused solely on hashing integers and held off on the discussion of applying division hashing to strings. (I did bring it up in the exercises, though—and of course, you knew that.)

It turns out that one of the most efficient ways to use division hashing for strings is the initial_hash method from our final implementation, which went like this:

Besides being fast, it also ensures that anagrams don’t necessarily produce the same hash codes as each other, something which is not the case if we simply convert each character to a number and multiply the numbers together.

So, in the DivisionHasher class we implemented in , we can swap out the hash method’s code and instead use the code from the initial_hash method. That’s the gist of it, anyway. I’ll leave the exact implementation to you, as an exercise to follow.