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

0:00 Intro

0:02 in the last subsection i've promised the last string matching algorithm in this unit i want to talk about another one the raven carb algorithm which also has its pros and cons um and one of the big advantages of this algorithm is its space usage uh first of all well we've already seen just as a recap a voice case optimal algorithm and we've seen one that has slightly better typical performance whatever that means but maybe for english language text it's better what else could we hope for and one thing they all do is apart from storing the text and the pattern they at least need extra space as much as the pattern is long if you have really large patterns that is maybe not desirable and at least in theory you can ask is this necessary do we need extra space to do pattern matching remember that brute force does not need any extra space apart from these two variables i and j so you can definitely do pattern matching or string matching so string matching and pattern matching is the same so some people prefer one over the other i think string matching is slightly more telling so i'll try to stick with that we you can do string matching without extra space apart from these two

1:23 variables but then it needs n times m spay time can we somehow get the best of both worlds and raping carb is a essentially yes answer to that and it uses a lovely idea that doesn't pop otherwise doesn't pop up otherwise in this module which is a shame in itself so i want to at least tease her this that's the idea of hashing

1:31 Rabin-Karp Fingerprint Algorithm - Idea

1:52 the the idea is very simple conceptually you have this pattern string you can compute a hash of the pattern think of it as a fingerprint that is smaller than the pattern and then for each guess in the text you can compute this fingerprint and if the fingerprints are different there's definitely no match if the fingerprints are the same the way the fingerprints work in this case is there could be false positives with a hash you have collisions so it can happen that two things have the same hash the same fingerprint but they are not the same fingerprints for humans i guess tend to be fairly unique so if if it's different people they have different fingerprints and vice versa for hashes this is not quite the case you can have the same hash and still be different so if we uh if we find that the hashes agree of the pattern and the portion of the text then we have to still check all the characters if it's a real match or just a spurious false positive but hopefully we don't have these often

3:03 for the examples in in this section um i'll use numbers so you can think of the alphabet as being the digits uh just because then the the hash computations become more natural to write down but the same works for other alphabets uh just the math uses different numbers but you remember it's all binary at the end of the day so here's a text a long sequence of digits and here's a pattern can we somehow find where it occurs and with the idea of hashing we need a hash function so we need a way to reduce a pattern of a circuit size to a single number that we can quickly compare and one not completely stupid way to do this is to take the number modulo prime

3:52 and so here we just have x modulo 97 as an example if you take this for this pattern well take my word for it that the the remainder if you divide by 97 is 95. i don't think there's an easy way to check this other than doing the math um and now you can try to find this in here in the following way the first guess would be these five digits if you compute the hash of those it's 84 so definitely not a match if you shift this by one look at the second five characters compute the hash it's not 95 so it can't be the match and you keep going like this until at this position you compute 95 and in this case indeed it is the pattern so there is an occurrence starting here

4:57 and [Music] we could find this by just comparing the hashes i first attempt to write this into code which will work fine but it's slow for a reason i'll show you in a second is this so first we we need our hash function and we'll stick with the idea of using essentially the the number module over prime so we we pick some prime number without getting into the details how to do this it's not relevant for our discussion um

5:03 Rabin-Karp Fingerprint Algorithm - First Attempt

5:36 well i feel i can't not i can't leave this as this what you want is is a number that's not too big so that the result fits in one word but you don't want it too small otherwise you get many collisions so you probably want to pick a prime number that's just below 2 to the w and it's it's efficient to find these

5:58 and they can be pre-computed for once and for all then we can compute the hash of the pattern and store that in hp and then for each guess we compute the hash of the text at this position if the hashes agree we might have a match we still have to compare so we do a characterized comparison i just abbreviated this here by saying we compare the strings but really this is m individual character comparisons and if they match we return the position otherwise we keep going

6:32 now this is fine it's correct the algorithm as given because it uh it always checks if we have a collision of the if they have the same hash then it checks and if there's a different hash it definitely is not a match

6:49 the problem is that the computation of the hash itself takes linear time in the length of the pattern because the hash function depends on all the positions and so there's essentially no better way than computing this one step at a time walking through the string and we do this for each guess in the in the array here so

7:18 we have n minus m roughly n times m so that's the same worst case as for brute force and indeed here it's not it's not even worst case we do this every time we have to compute the hashes of all the guesses so that's not great

7:33 Rabin-Karp Fingerprint Algorithm - Fast Rehash

7:34 fortunately we can do this slightly faster slightly smarter by exploiting the exact form of the hash function that we used here and the idea is that we always go from one position in the text to the position one later

7:57 so it's not like we need the hash of two completely unrelated positions in the text almost all the characters stay the same it's just a little inconvenient that they are shifted around there's the first character deleted a new one added at the end

8:12 but with a little trick you can actually update the hash for this specific hash function in constant time for that kind of operation and the trick is you pre-compute or for our pattern length you pre-compute this number which is just the number of number of digits 10 to the number of positions in in the pattern the old hash say for this number is known and now we would like the next hash and i mean i just point out again these are all the same we deleted the four and we added the six at the back so how can you compute this using what we already know the new hash is the old number where we subtract the first digit so we just have to shift the first digit by as many zeros to the left as as needed then we get one five nine two we multiply that by ten that shifts the one to the left and then we add the six okay and um one convenient one convenient property of modular arithmetic is you can take the modulus first and then do the arithmetic they commute as you may remember and so we know the result of this one modulo 97 that's 9 that's what we pre-computed and we know this one modulo 97

9:40 so that's the previous hash right so we can reduce these big numbers where the computation would be slow to the small numbers that fit in one word and are computable in constant time and the rest is just a little bit of arithmetic but it all involves small numbers they're independent of the size of this of the pattern that's the important bit that's why we pre-compute these recompute this number and and just use the hash here instead of the full pattern the full number okay

10:16 Rabin-Karp Fingerprint Algorithm - Code

10:18 i spelled this out in code but there's no surprises it's doing exactly what i explained in the general case you want to pick a radix that's not necessarily 10 but some number that's at least as big as the alphabet you can use it as slightly bigger and why would you sometimes want to use a bigger radix it's convenient to have a power of two then the multiplications become shifts and so it's it's even slightly faster even though it doesn't affect the theoretical runtime the modulus should be some some large prime but so that things fit still into one word um and you can you can show that all the numbers are never bigger than this and here that's that's the computation i explained in the last slide just neatly written up in in one formula the rest of the code is unchanged right we go through all the guesses if the hash is match then we check all the occurrences and before we go to the next match we update the hash so that it is the hash of the next position

11:30 how good is this uh the expected running time is as good as we can hope for in the worst case m plus n again there is a worst case in if you're very very unlucky and your hash function produces lots of false positives you always have to check all the characters now um if our prime number is deterministically fixed if you pick this once and for all then some nasty person could work through your hash function and produce a text and a pattern that always gives you false positives uh but if you pick this slightly randomly so you have a certain range for the prime numbers and you pick a random one you can turn this worst case into something that is astronomically unlikely we had the same discussion for quicksort where you can pick a random pivot and make enforce that the average case becomes the usual case and it's not dependent on the input anymore

12:18 Rabin-Karp - Discussion

12:38 we achieved what we wanted initially we only need constant space if you check the algorithms the only thing that is stored is a few extra numbers and the hash of the current position and the pattern and these are all these all fit into one word so it's a constant number of x constant amount of extra space in total and another cool thing about this is it extends to other situations it's not just for strings you can use this for finding certain 2d patterns in in pixel images and things like that just because this fingerprinting idea is very versatile and same the hash function can also be updated if you shift a segment of a matrix around

13:22 let's do one more of these same kind of principle just reiterating what's good and what's bad about the algorithm um and be precise about what the guarantees are i've only one more slide to show up to this question

14:37 all right seems most everyone's done three two one locked seems seems pretty clear so let me so if we drop the check right if we don't do this extra check we only rely on the hashes

14:52 Clicker Question

15:10 then we might report positions that are not real matches we will never overlook matches so maybe this is still useful and then if we do this if we omit the check then the worst case running time is n plus m so that's why maybe this is useful depending on what you want to do with it sometimes it's fine if you if you report all the correct matches and some extra ones and you can later deal with them it's just something to point out so you might run ravencard without the check if you don't need it to be always correct then it's always fast but sometimes gives additional results if you want it to be always correct then it's sometimes slow

15:53 String Matching Conclusion

15:56 and that brings me to this last slide that just summarizes the algorithms we've seen for string matching in terms of different categories how much time they need for pre-processing how much time they need during the searching space the searching phase and how much extra space they use the last column we haven't seen yet but we will see and it's probably fair to say that there's no algorithm that completely dominates all the others it depends a little bit on the on the circumstances which one is good volume or tends to be well used in in practice because it is a strike's a good balance and ravencarp is liked for its extendability extendability to other settings