Learn how to implement the Rabin-Karp Algorithm in Python!

Implementing the Rabin-Karp Algorithm in Python

We saw a neat way to recover hashes using rolling hash, but unfortunately, we still ended up with a hashing collision in the case of palindromic strings. Simply multiplying primes will not make a good hash function. For this reason, the Rabin-Karp algorithm uses a Polynomial Hash Function. This is a combination of sums and products (as opposed to only products) to make the final output more unique and therefore almost entirely immune to hash values colliding.

In Python, a polynomial hash of a string `'ABCD'` can be calculated as follows:

```python
ord('A') * 26**3 + ord('B') * 26**2 + ord('C') * 26**1 + ord('D') * 26**0
```
In this exercise, we will implement the same idea but automate the process using `for` loops.


Polynomial Hash Function

We now have all the tools in place to complete the full implementation of the Rabin-Karp algorithm! All that is left is to compute the hash of the pattern and compare it with substrings of the same length in the text. If they hash to the same value, it is safe to assume a match has been found. Here is what the pseudocode might look like:

* Find the first substring in `text` equal in length to `pattern`.
* Compare its polynomial hash with that of `pattern`.
* If they are equal, increase `occurrences` by `1`.
* Iterate through remaining substrings in order
* If the polynomial hash of any substring matches that of `pattern`, increase `occurrences` by `1`.
* Return `occurrences`.

Rabin-Karp Algorithm

In trying to compute the hash values of all substrings, we can still bypass some of the calculations. That's right! We don't have to perform multiplication after multiplication to compute the hash of every substring.

You might have noticed that after calculating the hash of "ABCD" by multiplying the prime numbers, we don't necessarily have to calculate the hash of "BCDE" by yet again multiplying individual prime numbers. Instead, to recover the hash of "BCDE" from that of "ABCD", we can do something as follows:

* remove the hash of "A" from the hash of "ABCD" by dividing it out, which gives us the hash of "BCD"
* multiply the hash of "E" into the hash of "BCD" which gives us the hash of "BCDE"!

```python
prime_hash_ABCD = prime_hash('ABCD') # prime hash of 'ABCD'
rolling_hash_BCD = prime_hash_ABCD // prime_hash('A') #divide out the prime hash of 'A'
prime_hash_BCDE = prime_hash('E') * prime_hash_BCD #multiply in the prime hash of 'E'
```
Notice how we performed only a single division operation and a single multiplication operation to calculate the hash of `'BCDE'` instead of performing three multiplication operations as follows:

```python
prime_hash_BCDE = prime_hash('B') * prime_hash('C') * prime_hash('D') * prime_hash('E') #three multiplication operations
```
 We saved some computation time in the process! It might not seem like much, but imagine searching for a much larger substring, and we would be saving computation time in orders of magnitude.
 
This is the idea of rolling hashing.

Let's calculate the hash values of all substrings of length 4 in `uppercase` but this time using the idea of rolling hashing. We will now recover the hash value of each subsequent substring of length `4` from the previous one using the divide + multiply trick we showed above. 

But to begin this domino effect, we still have to start with the hash value of the first substring of length `4` that was calculated using multiplication via `prime_hash()`. We already have access to this value via `prime_hash('ABCD')`.

Rolling Hash

It seemed like we were making decent progress, but our hash function collided to the same value! Indeed, there is only a limited set of values that we can generate using ASCII values. This is a problem because our pattern-matching algorithm can erroneously produce a match between a pattern and a substring even when they are different from one another! In other words, our hash function is not that great at producing unique values for unique strings. Can we do better?

The collision occurred because even though the product of ASCII values seemed unique on the surface, it turned out to have the same prime factors, which resulted in the same value. What if we use prime numbers instead of ASCII values? This would guarantee that every pattern has its own unique prime factorization.

In other words, instead of assigning a unique ASCII value to each character, we assign a unique prime number in increasing order as follows:

```python
{'A': 2, 'B': 3, 'C': 5, ..., 'X': 89, 'Y': 97, 'Z': 101}
```
 Since `'A'` is the first character, we assign it the first prime number: `2`. Similarly, `'B'` takes on the next prime number, `3`, and so on. The complete list of the first twenty-six prime numbers is as follows:

```python
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]
```

Just like how we multiplied ASCII values for each character in a substring to get its ASCII Hash, we will multiply the prime-number values (or just prime values) for each character in a substring to get its prime hash. We've already defined the first twenty-six prime numbers in the code, so let's get started!

Hashing Collision

Congratulations! You have reached a significant milestone in your programming career &mdash; implementing an advanced string-matching algorithm from scratch! Here is a quick recap of what we accomplished together throughout this lesson:
 
* Quick recap of naive pattern-matching and its limits - using a brute-force sequential approach to check for a pattern match against all substrings that performed reasonably well until we ran into a rather large input.
* Looked for ways to speed up pattern-matching by revisiting hashing &mdash; assigning a somewhat random and unique value to a pattern to find it in a given text quickly.
* Explored various ideas involving hashing, starting off with assigning ASCII values to characters, which quickly led to problems when different strings collided to the same hash value.
* Improved on the previous idea so that characters are assigned prime numbers instead of ASCII values which gave a unique prime factorization that led to a unique hash value for most strings (except palindromes).
* Implemented the key idea of rolling hashing where we recovered the hash value of the next substring from that of the previous substring by dividing out the hash of the old character and multiplying in the hash of the new character, thereby performing way fewer calculations in the process!
* Implemented the idea of a Polynomial Hash which takes the best of both addition and multiplication (including higher powers of a number) to create a much better hash function for pattern-matching.
* Combined the ideas of rolling hashing and polynomial hashing to implement the Polynomial Rolling Hash, which allowed us to quickly calculate the hash values of subsequent substrings from that of previous substrings, thereby allowing faster pattern-matching.
* Brought all these ideas together to implement the Rabin-Karp Algorithm and tested it on large hidden inputs where naive pattern-matching would have simply timed out.
* Counted occurrences of a large pattern in an even larger text significantly faster using the Rabin-Karp algorithm on the same input that Naive Pattern-Matching wasn't able to handle so well, and also explored the limits of Rabin-Karp.
 
We hope you learned a lot from this lesson and have deepened your understanding of an advanced string algorithm while also improving your ability to think algorithmically. This isn't the end of the road though! Next up is content the Knuth-Morris Pratt algorithm, an even more advanced pattern-matching algorithm that can find a pattern even faster!


Summary

Great job so far! You are certainly an expert when it comes to searching for patterns using brute force. But judging from how long it took the last program to run, naive pattern-matching seems to be approaching the limits of its abilities. Fortunately, we can do better with a bit of help from an old friend of ours &mdash; hashing.

Let’s create a simple hash function to calculate the hash values of strings involving only the uppercase alphabet. Of course, not all strings where we want to find patterns will consist of well-arranged characters from `A-Z`, but this is a good way to get some practice before dealing with all kinds of strings.

To calculate unique hash values for a given string of uppercase letters, we must first calculate a unique value for each character somehow. How can we do this?

One idea is to map each character in the string to its corresponding ASCII value and take the product of the ASCII values. We will call this the ASCII hash. Let’s calculate the ASCII hash of some strings using this approach.



Hashing Review

You are probably wondering why we didn't make use of any "rolling" property of the polynomial hash function and just calculated the hash values for all substrings by adding up the individual contributions of all the characters each time. And you are correct! As we saw in an earlier exercise, we can exploit this "rolling" property here as well to reduce the number of operations and speed up our computation time!

Instead of calculating the hash values of all substrings using the polynomial hash function definition every time, let's try to recover the hash values of subsequent substrings just like we did with prime rolling hashing.

For example, we could recover the same polynomial hash of `'BCDE'` using fewer computations from the polynomial hash of `'ABCD'` as follows:

```python
polynomial_hash_ABCD = polynomial_hash('ABCD')
rolling_hash_BCDE = hash_ABCD - polynomial_hash('A') + polynomial_hash('E')
```
This seems plausible. After all, we used a similar divide + multiply trick for prime rolling hashing and are now using a subtract + add trick for polynomial rolling hashing. What could go wrong? Let's find out!


Exploiting the “Rolling” Property Again!

To get a handle on a more advanced string-search algorithm like Rabin-Karp, it is a good idea to be comfortable with naive pattern-matching on a given string. In this exercise, we will refresh our understanding of the straightforward brute-force approach so that we can really appreciate what motivates the improvements in speed-up of the Rabin-Karp algorithm!
 
To quickly recap, this is how naive pattern-matching on a given string works:
* Iterate over the entire string to find all substrings equal in length to the pattern that we are trying to match.
* Iterate over each substring, and check to see if this matches the pattern.

Revisiting Naive Pattern-Matching

In this lesson, we will implement the Rabin-Karp algorithm discussed in the previous article using Python. We assume that you are familiar with most of the common data structures and algorithms by now, so this lesson will be a step towards delving into somewhat advanced algorithmic territory!

We can use the Rabin-Karp algorithm to find all occurrences of a pattern in a given text. We can implement this in several ways but the core idea of the algorithm remains the same &mdash; instead of matching the pattern against a substring in the text character-by-character, we will use string hashing to compare them almost instantly. To bring the algorithm to life, here is what we will do in the exercises that follow:

* Quickly recap naive pattern-matching by implementing a brute-force algorithm to locate a pattern in a given string.
* Refresh our understanding of hashing by performing some hashing operations on strings.
* Explore different hash functions to increase efficiency in pattern-matching.
* Optimize the Rabin-Karp algorithm for peak performance.

Let's get started with tackling each of these steps.