Video 4-8: §4.7 The Rabin-Karp algorithm

0:00 Intro

0:03 let me briefly show you uh one last string matching algorithm that brings in a different idea that's the Arabian carb algorithm I'll go through this in in much less detail in a way the only thing that's left open to improve on is is the space we had both KMP and and boy or more needed at least as much space as the pattern on top of the pattern so at least they needed Theta of m space beyond the pattern uh so what what could we improve um the question is can we somehow apart from storing the pattern in the text which we need can we somehow get away with even less space and the question the answer is yes um and it's it's a it's a neat idea that we haven't really touched on in this module but I think it's worth knowing for any computer scientist that's the idea of hashing uh we we will use this in this case in general a hash function is just take a complex object and map it down to a small number taking into account that because there's many complex big objects you may map several of them to the same hash code the same hash value so it's something like a it's like a fingerprint but we tend to think

0:47 Rabin-Karp Fingerprint Algorithm - Idea

1:21 fingerprints are unique for All Humans so it's not a good fit it's not a good name it's it's a it's a lossy fingerprint all right so what we'll do here is we'll we'll take a hash of the pattern and then take hashes of pieces of the text and if the hashes don't match then we know that there's no match that's the idea if the hash is matched we don't know for sure because there could be several strings that have the same hash so we still have to check in that case that's that's the gist of it the examples in this uh section in this subsection will be with numbers so digits as the alphabet just because that's a bit more natural for the hash functions that we'll use but it works without any change with characters remember that for computers characters are converted to numbers anyways so we could use a hash function like this one just take X modulo some prime number 97 so um the hash value of the pattern is is 95 how would we use this in pattern matching well we take the first five characters of the text and compute its hash that's not 95. and this is not 95 this is not 95 so for all of these shifts by just looking at

2:42 the hash I can conclude it is not a match so far so good at some point so it's a bit tough to trace but if you put in the dividing lines you see this is an occurrence of our pattern in this case uh the agreement of the hash is not a spurious hit it's an actual occurrence of the pattern

3:06 Rabin-Karp Fingerprint Algorithm - First Attempt

3:07 that's the idea all right if we directly implement this we might come up with something like this um so there's uh a black box that computes the hash for now I apply this once to the pattern initially and then for every guess I apply it to the portion of the text from I up to I plus n minus one so it's it's the portion of the text that could match the uh the pattern I guess this is a mistake here

3:42 and it's probably nicer if I would write this with round parenthesis but okay um we compute the hash if the hash agree I still have to check if there's an actual occurrence and otherwise I continue

3:59 the code is correct it does was it's what it's supposed to do unfortunately for the type of hash functions that uh I looked at this here for example you essentially would have to look at all the characters in the text to compute the hash so we compute the hash look at all the characters of the text portion then use the hash we might as well have just checked the text portion against the pattern with like before in The Brute Force algorithm so as given this is not really useful the trick comes in that there are some clever hash functions that are good enough for this purpose but can be computed more efficiently and that's um that's based on taking numbers like this and modulo Prime that's the hash functions we look at and these are good enough for that purpose I'm just claiming that now without proof if we had a hash before and we now want to get rid of the four and add a new character at the end we can compute that by taking the old hash subtracting the first digit in a way and then adding the six so in the obvious way in decimal notation you would do it like that that's the first line now because we're Computing everything

4:36 Rabin-Karp Fingerprint Algorithm - Fast Rehash

5:24 at the end modulo 97 you can pull the modulo 97 inwards that's um modular arithmetic 101 that you may remember so instead of doing this large multiplication here we can use a small one and uh include instead of doing this subtraction on the full pattern length we do it on its hash which we which we have from before so we can do all these computations with fairly small numbers in particular essentially independent of the length of this of the pattern it just depends on the size of this prime number and so that's that's the trick of fast rehash uh when you look at the code at the the key bit here is is this rehash computation and um it does what the example has shown in the previous slides in general it does a few multiplications subtractions but they all involve small numbers and by small I mean around the alphabet size and around this this prime number size but you can work it out so that they stay in a in a small range independent of M the length of the pattern

6:03 Rabin-Karp Fingerprint Algorithm - Code

6:47 if you Analyze This a bit more carefully then the expected running time is good it's n plus M like boy like like knuth more spread it's expected here because there's uh some some part is missing how do you choose a suitable prime number and the expectation here is is essentially over random random patterns or random texts so you have to make some assumption here otherwise the worst case is still M log is M times n you could have um just many many false positives from the hash

7:26 remember the standard time that I present here is just to find the first occurrence uh you also get this running time for reporting all matches some harder to avoid in this case other good things is that this kind of string matching can easily generalize to other more complicated scenarios like finding patterns in a in a picture in a 2d 2D array and it uses constant space at least independent of M which all the other methods couldn't do

7:59 Clicker Question

8:03 I have one last question to uh to check your understanding I don't know if we have time for it no one has stormed the room yet this is just to test your understanding if you have to run to another lecture then um

8:24 for those who happen minutes I'm I'm happy to discuss the the answers for that and now I ran through this subsection a bit too fast it will not occur on the exam if that helps you at least not not Beyond this superficial level that that we discussed

9:13 just turns out to make a really terrible choice for exam questions anyways obnoxious to mark two more one more all right so to quickly cover this uh we're talking about ravenclub without the extra check we just rely on the hashes um

10:17 the algorithm never misses An Occurrence because if there is a mismatch at a position um well if the only thing that can happen is that the hash is equal to the pattern hash but there's no occurrence but we never miss An Occurrence but we might report positions that are not hashes and not actual matches just because the hash is collided in this case we do get the best the best possible worst case run time just because we don't ever do the check so uh we just run through shift the to the recompute hash in each in each step and that's constant time uh it doesn't it it does depend on M though because you have to compute the hash of the pattern and you have to get the rolling hash started off so for that you need M time for the Absurd case that the pattern is much longer than the text uh that would make a difference all right see you on Wednesday