Handling Long Needles

Armed with our new, shiny implementation of the Rabin-Karp algorithm, we’re ready to tackle substring search for an alphabet of any size. This could include uppercase letters, lowercase letters, the numbers 0 through 9, punctuation marks, and various other characters. For our discussion, though, we’ll continue to use the 26 lowercase letters of the English alphabet.

But there’s a problem.

In our example, we had used a pretty short needle. After all, "cafe" only contains four characters. But it’s not uncommon to search for longer needles. If we’re searching a document for plagiarism, for example, we might use an entire sentence as a needle.

Now, say that our needle is the 28-character word "antidisestablishmentarianism". If we hash this from base 26 to base 10 (using our scheme a=0, b=1, and so on), we get the number: 84602278762307761469177551207947970504. That’s pretty long. As our needle length increases, our hash codes will grow longer and longer. Imagine if we had a needle with a length of 500. Yikes!

The reason this is problematic is that the entire reason we’ve been hashing words into numbers was so that a computer can compare two numbers quickly. However, this is, in fact, only true when the numbers are relatively small. When numbers are extremely large, computation speeds go down, and memory consumption goes up. Python is better than some other programming languages at processing large numbers, but even Python has its limitations.

Now, if your application is not going to be dealing with long needles, our current Rabin-Karp implementation is perfect, and there’s no need to adjust it. The remainder of this chapter is all about optimizing Rabin-Karp to handle both long and short needles efficiently.

Division Hashing

Fortunately, we can solve this issue with the technique of division hashing described in . Specifically, we’ll update our hash functions to not only convert numbers from base 26 to base 10, but also divide that result by some prime number. Let me show you what I mean.

The Basic Division Approach

The basic approach is that we’ll tweak our hash function ever so slightly. Currently, our hash function is simply to convert base 26 to base 10. But again, the problem is that if our string is very long, the hash code will be very long as well.

Our trick is to perform one more computation after converting from base 26 to base 10. That is, after we do the base-26-to-base-10 computation, we then divide the result by a predesignated prime number and grab the remainder. This remainder is now our hash code. Later, I’ll discuss how we’ll go about choosing our prime number. But whatever prime number we choose, this will be the one we use throughout our entire substring search algorithm.

Let’s walk through an example.

Say that our prime number is 613. When we divide a number by 613, the remainder will be some number from 0 up through 612.

Let’s now hash our needle, "cafe". Earlier, our hash code of converting base 26 to base 10 gave us a result of 35286. We can now update our hash code so that we then take the 35286 and perform one more computation of:

With this update, the hash code of "cafe" is now the shorter 345 rather than the longer 35286. What’s nice about this is that even if our needle was much longer, such as "antidisestablishmentarianism", the hash code will never be larger than 612. Indeed, the hash code of "antidisestablishmentarianism" is now:

Computer scientists like to refer to this concept as fingerprinting. A detective can use a fingerprint to determine which person touched the doorknob, even though the fingerprint is much smaller than the actual person. Similarly, we can use a small piece of data (such as 230) to represent a larger piece of data (such as 84602278762307761469177551207947970504).

So far, we’ve updated the initial hash function that computes the hash code of the needle and the first haystack window. But we’re going to use this same general division approach for our rolling hash function as well. That is, we’ll be dividing various results by the same prime number of 613. Later, I’ll explain how precisely to perform this math, but let’s take this general approach at face value.

Because we’re applying the same hash function—including the division—to our needle as well as the haystack windows, we can still perform an effective substring search. That is, if the needle’s hash code is the same as the haystack window’s hash code, we’ve found our match. Otherwise, the two strings are definitely not the same.

Collision Ahead

This is where things get interesting and is, in fact, the impetus for discussing the Rabin-Karp algorithm at this point in the book.

Before we introduced division hashing into our Rabin-Karp algorithm, the hash function guaranteed that two strings must be identical if they have the same hash code. But now that we started shortening numbers with division hashing, it’s possible for two different strings to end up with the same hash code. As we’ve seen, all numbers, no matter how large they are, will end up having a hash code in the range of 0 through 612. If you take, say, 614 different strings and hash them, it’s guaranteed that at least two of them will end up with the same hash code. Likely, many more strings will share hash codes as well.

We saw this same idea when developing hash functions for hash tables. There’s always a possibility that more than one value will end up within the same hash table slot.

Now, for hash tables, this may not be the biggest deal since we can handle collisions with separate chaining and other techniques. But it is a real problem for substring search. That is, our code might mistakenly think that it found the needle in the haystack even when it didn’t!

Here’s a quick example. We already know that our needle "cafe" hashes to 345. Now, if our algorithm encounters the haystack window "clzr", the computer will hash it by converting it from base 26 to base 10, which yields 43255. Then, the computer will divide it by 613 and grab the remainder, which is ... 345! The computer will then report that it successfully found "cafe" when this couldn’t be farther from the truth.

It’s worth pointing out that the opposite type of bug cannot occur. That is, the computer will never encounter a match and erroneously report that it’s not a match. If two strings are, in fact, identical, they most certainly will have the same hash code. But we do have the potential error in the direction of the computer thinking that it’s found a match when it actually hasn’t.

However, let’s analyze the likelihood of this error happening.