Perfecting Rabin-Karp with Base 26

Let’s quickly review the problem we encountered earlier. The Rabin-Karp algorithm worked fine when we were dealing with an alphabet of 10 characters. This is because each character, when converted into an integer, would live by itself in its own digit place within a larger number. With such a scheme, it was impossible for any hash code to represent more than one string, which is a good thing.

But as soon as we introduce more than 10 characters into our alphabet, we now have characters that convert to two-digit numbers, such as k, l, and m, which convert to 10, 11, and 12, respectively. And two-digit numbers take up, well, two digit places. And when this happens, we can no longer know if a two-digit number represents a single character that corresponds to a two-digit number, or if it corresponds to two single characters that each correspond to a single-digit number.

Additionally, we saw how a single hash code (that is, 120) can represent both "lk" and "ma", even though they both have the same number of characters. What we need is some way to ensure that each character will only take up one digit place, even after we hash it. Fortunately, we can use what we learned about numerical base systems to help us.

The String Is a Number

Before we look at how base systems will make things better, let’s first take another look at strings, this time from an entirely different perspective.

If we chose to, we could look at any alphabetical string as if it were a number. Here’s what I mean.

Let’s work with our familiar scheme of a = 0, and b = 1, and so on. What hash code does the string "cab" convert to?

That’s right, the string "cab" is equivalent to the integer 201.

If we wanted to, we could say that the "cab" is the number 201. We happen to be using alphabetical “digits” rather than numerical digits to express this number. This may sound like mere semantics, but trust me, it’ll help.

Based on this perspective, we’d also say that until this point, our hash function has been viewing a string as a base 10 number and converting its digits from alphabetical ones into their numerical equivalents.

The problem, though, was that when our strings contained characters that came after the letter j, our strings made for terrible base 10 numbers. This is because when we represent a base 10 number using numerical digits, each numerical digit takes up one digit place. But when we use a string, many characters take up two digit places.

A New Base System for Strings

The trick to solving our problem is this: instead of treating a string as a base 10 number, we should treat it as a base 26 number. More generally speaking, the base system of a string should correspond to the number of characters in the alphabet we’re using.

Let me spell out what it means to treat a string as if it were a base 26 number.

In base 26, here’s what each digit place represents:

Let’s now take the string "bmm". (I know, it sounds pretty random, but wait for it …) If we treated this as a base 26 number, what number would it be? If you have the self-control of a yoga master, try to work this out for yourself before reading on.

Here’s how "bmm" breaks down as a base 26 number:

In this image, and those that will follow, I’ve placed the corresponding decimal value below the letter. So, in this example, there is one 676 (represented by the “b”), twelve 26s (represented by an “m”), and twelve ones (also represented by an “m”). This is the base 26 way to express the number one-thousand, since:

Now, if we treat our strings as base 26 numbers rather than base 10 numbers, we automatically solve the digit bleeding problem we struggled with before. A bleeding issue occurs when we have a character that needs more than one digit place to hold it. But because each digit place of a base 26 number can hold 26 different characters (such as a through z), and we only have 26 characters in our string’s alphabet, we’re guaranteed that each character can fit neatly into a single digit place.

A Base-26 Hash Function

Let’s incorporate these ideas into Rabin-Karp and see how everything plays out. We’ll go back to the beginning, starting with hashing our needle. In the example at the start of the chapter, the needle was "cafe". Let’s peek back at how we hashed "cafe" when we treated the string as a base 10 number:

We’re going to stick with this basic scheme, except that now we’ll treat our strings as base 26 numbers. That is, we’re going to view "cafe" as follows:

This is the number that, in English, we’d refer to as thirty-five thousand, two-hundred, eighty-six.

Recall that our ultimate goal is to convert strings into Python integers so that our code can compare them more quickly. The thing, though, is that Python integers are represented as base 10. (It’s binary under the hood, but when we write the code x = 11, Python interprets it as base 10, so x is eleven.)

This is what our hash function does: we treat the string as a base 26 number, and convert it into a base 10 number.

More specifically, instead of multiplying each digit by 1, 10, 100, or 1000 like we did originally, we multiply each digit by 1, 26, 676, and 17576. And so, our hash function will hash "cafe" in the following way:

As you can see, when we hash "cafe" it yields a result of thirty-five thousand, two-hundred, eighty-six—or what we write in decimal as 35286. Our problem is now solved. The string "cafe" can represent one and only one particular base 26 number. Our hash function simply converts that base 26 number to a base 10 number since that’s what Python understands.

Conversely, we also know with certainty that the base 10 number 35286 can only represent the letters "cafe" and no other string. For when we convert a number from one base system to another, we’re merely expressing the same number in different ways. And so, if we’d convert 35286 from base 10 to base 26, and use our scheme of a = 0...z = 25, we’d come up with the string "cafe".

In our code, however, we’re only going to be doing this conversion in one direction. That is, we never need to take a base 10 number and convert it back into base 26. The modus operandi of Rabin-Karp is that we convert both the needle and haystack window from base 26 to base 10 and see if they match.

Rolling with Base 26

At this point, we’ve successfully adapted our initial hash function to handle alphabets of 26 characters. However, we’ve only addressed the initial hash function, that is, the one that hashes an entire string at once. We now have to modify our rolling hash function as well. Luckily, it’s going to be a quick and easy modification.

As a reminder, here’s what our rolling hash function did when working with base 10:

Again, this updates the hash code from the previous haystack window and converts it to match the current haystack window. With this math, we effectively remove the old first digit and tack a new one at the end. In this example, the 3420 lost the left-most 3 and gained a new 5 at the end, turning into 4205.

To get this hash function to work with base 26, all we have to do is change the formula so that wherever we’ve been multiplying by 10, we multiply by 26 instead. With our haystack of "decafcafeahead", the first window is "deca", which in base 26 hashes to 55484, as you can see here:

Now, the next character in our haystack is an "f", which corresponds with the digit 5. Here’s how our rolling hash formula will execute:

This gives us a new hash code of 71661, which indeed is the base 26 representation of the new haystack window "ecaf".

In other words, our old rolling hash function multiplied things by 10 because we were working with base 10 numbers. Since we are now working with base 26 numbers, we multiply by 26 instead. Let’s walk through the example line by line to make it super clear.

We start with the previous window’s hash code. Our immediate goal is to delete the old "d" that our new window is dropping. Because the "d" in base 26 is in the 17,576s place, this computes to 52728. So, by subtracting this from the previous hash code, we effectively delete that initial "d".

Then, we shift all the digits to the left by multiplying our current result by 26. When we worked with base 10, we multiplied by 10 to shift the digits. But now that we’re working with base 26, we need to multiply by 26 to shift the digits. This might be intuitive to some, but I always like spelling things out (if you haven’t noticed). In the next section, I’ll elaborate further as to why this works.

Shifting Places

Back when we were dealing with base 10, by multiplying a number by 10, we were able to shift each of its digits one place to the left. For example, we multiplied 420 by 10, which effectively shifted each digit one place leftward:

Essentially, when we multiply 420 by 10, we are saying to take the 4 hundreds and multiply them by 10, and to take the 2 tens and multiply them by 10. This gives us 4200.

Now, here’s the thing. To shift any number from any base in this way, we simply need to multiply the number by the base itself. So, because the previous 420 example was a base 10 number, we multiplied it by 10 to shift the numbers leftward.

To shift the digits of a base 2 number, we multiply the number by 2. And if our number is in base 16, we’d multiply the number by 16. This shifting process works no matter what the base is. The reason for this is outlined in the chart from earlier:

Each digit place is equivalent to its right neighbor multiplied by the base. For example, the b³ is the b² multiplied by the base (b² * b = b³.) So when we multiply a number by its base, we multiply each digit in each place by the base, and thereby shift each digit to the left. And so, now that our hash functions work with base 26 numbers, we can shift such numbers by multiplying them by 26.

Let’s look at this in action with our example. After subtracting out the initial "d", we had a resulting code of 2756. Here’s the breakdown of what happens when we multiply 2756 by 26:

This visual shows how multiplying 2756 by the base of 26 effectively shifts each “digit” one place to the left.

Getting back to our rolling hash function, after we perform this shifting step, the final step is to tack on the current window’s new character at the end. We do this simply by adding the new character’s hash code to the result of our previous computations.

We can now generalize our rolling hash function for any base, as follows:

Whew! I think we’ve made Mrs. Wilson proud.

Code Implementation: Rabin-Karp for Any Base

Let’s modify our Rabin-Karp code so it handles base 26. Even better, let’s make it handle any base:

This code is almost identical to the previous implementation, with the only difference being that we’ve made the base flexible instead of hardcoding it as 10. To do this, we declare a global base variable, which is then used within our hash functions.

Currently, base is set to 26 since we’re working with an alphabet containing 26 characters. If you were working with, say, the entire range of ASCII characters, you’d set base to 256.