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

0:00 Introduction

0:05 in the last subsection of unit 4 i want to introduce a different algorithm again for string matching but it uses an entirely different idea that's the the ravencarp algorithm that uses hashing for string matching

0:22 one weakness of the current methods was the space that they use boy or more actually needed this sigma space at least for the last occurrence function and even knew the more spreads and boy more for other reasons they all need

0:41 they all need space at least as long as the pattern and for large patterns this might be a problem it's usually not such a big deal because you have to store the pattern itself but it's space on top of that and it's also a nice theoretical question if we can avoid that or if that is inevitable and uh yeah as it as it turns out this um this is very much uh avoidable and um so the idea for that is from a very different field we use fingerprinting uh it's otherwise known as as hashing and if you've done an undergraduate algorithms class data structures class you will definitely know about hashing i'd love to talk more about it maybe it should be part of of unit 2 but it was already quite full hashing is another way to realize unordered dictionaries and for that it's usually the choice in practice because it has just great average case behavior here we just use the main idea of hashing and do it in a slightly different way what we do is we compute a hash of the pattern so instead of this long string that could be hundreds and thousands of characters we compute a small number relatively small number maybe a one inch that represents this this pattern that

2:07 won't be without some loss of information but still it will be good enough in a in a well-defined sense then we also compute for each guess so each potential position in the text we compute a hash and if the hashes agree there might be a match so then we check character wise if if this is really a match there could be false positives in that the hashes match but the strings are different that's because it's just a fingerprint and that's not an identical representation of the entire thing maybe fingerprint is a bit of an unlucky name because people think of fingerprints to be unique for each human whereas here um hashing really is is not unique there are different patterns that hash to the same fingerprint so let's do an example here where to make the the presentation a bit nicer i'm assuming that the alphabet is just um the decimal digits

3:14 there's not really any um meaning to the numbers so these are just characters um and uh we interpret them for the hash function as numbers but that is only by convention and you can do this um with any other characters and you can do this also by not following the usual convention of what these digits mean you can reverse the order do whatever you want so here's a pattern here's the text this is also nice because it makes it a little tougher for humans to spot the pattern in the text but if you look closely you'll see there is actually an occurrence here and we'll use as a hash function five digits interpreted as a decimal number and then take that number modulo 97 why 97 uh because it's um it's a prime number and it works reasonably well to use such a number uh that's the only reason and usually you choose something like this at random

4:15 so here's here's our text the conceptual idea of ravencarp is to compute the hash value of five consecutive digits this one is not 95 which is the hash of the pattern and if you keep going you find all of these can be excluded by just looking at the hash because the hashes already don't match then the part of the text and the pattern cannot be the same but if you start here

4:46 five nine two six five that actually is the pattern and it has the same hatch so you found an occurrence here very simple idea very easy to put into code um if you've seen hashing before you might not be surprised that you want to suit start with a suitable prime number of a certain range i don't want to go into detail with this um we compute the hash of the pattern and then for every possible position in the text we compute the hash of the portion in the text and if the two match then we still have to do the character wise comparison as i as i told you the hash could be the same even though they are different but then we return the match if we actually found it and if not we return that there is no match now this is fine it never misses a match since if the hashes are different the text is different that's the core property of a hash function

5:51 the hash value that we compute in particular of the portion of the text it depends on the m characters in the text that was the idea the hash value the hash function we used was just interpret this part as it as a number and then take that number modulo prime um

6:08 yeah i was i was about to answer the the question i've seen your question on slido um so maybe this is a good point to address that part um just very briefly

6:23 yes we kind of always prefer um prime numbers um well there's not so many even prime there's only one and that's too small so what you really want is a prime number that has roughly the right size and then the size of the prime number um gives you uh controls the probability of of hash collisions so you want this to be as big as you can make it without taking a performance hit so maybe a prime number close to the size the largest integer you can represent is probably a good choice so um yeah we need we want prime numbers because then collisions are much less likely for more details on this you would have to study hashing in more detail and that's maybe for another time

7:16 now the worst case running time and actually uh the running time on any input for this code is still n times m and the reason for that is that uh we have to compute the um we have to compute the hash value for each position in the text and we do this n minus m times and it takes m time each so that's n times m so it looks like our great idea with the fingerprinting wasn't really worthwhile doing it because uh to just compute the fingerprint we already spent as much time as we spent previously to find to check if that is there is an occurrence of the pattern at this point uh so that's too bad uh but fortunately we can fix this uh the main insight of of raven and carb is that we can update hashes in constant time if we move from position i to position i plus 1. and that only works for specific hash functions exactly the one that i've had above interpret things as a decimal number or as a number with radix size of your alphabet and take it module or something so let me briefly sketch how this works this is sometimes called a rolling hash

8:00 Rolling hashes

8:39 we do some pre-computations basically the well the um largest possible value um plus one um then uh we take the previous hash and we would like to find the next hash so notice that these four characters are the same they're just shifted over by one position and you append a new one now if you look into what the new hash value is the the new number this this number is the old number subtracted four times uh was that ten thousand that's because you want to get rid of the first digit that subtraction would leave you with 1592 then you multiply by 10 to shift the number one over and you add the new digit that is how you get from this number in decimal to this number in decimal and uh well taking modulo uh doesn't make a difference here it's um it's the same number so you might as well do this the trick now is if you compute in modulo you can compute

9:55 you can compute modulo before you do the arithmetic operations and that's again something where it's important you're operating with a prime and so you can compute this modulo 97 first but that's the old hash so we already know this and we pre-computed this modulo 97 so we know that's the 9 and so now we have to compute only with very small numbers that's the point these uh the pattern itself or the portion of the text that can be very yet very large it depends on the size of the pattern you're given but modulo that prime that's something you have under your control you can choose the prime small enough so that the numbers are small enough for you to compute in constant time and so you can just do this computation instead of working with these humongous numbers and do one more modulo step and then you have the new hash all right that's a neat way to exploit this specific form of the hash function and doing that in code gives you the ravencurve algorithm so a few more comments you pick some some radix um we well it has to be bigger than the size of the alphabet it was 10 in our examples then we just had the usual decimal numbers but anything really works

11:17 a power of two is convenient then you could do the shifting with bitwise shifts but that's um that's minor optimizations that need not concern you for this class and you choose a huge prime number that's random but not not too big so that you can still work with these numbers efficiently and all numbers that you work with then remain bounded in terms of the radix so in our case if if r was 10 we have numbers of at most size 200 and you can choose r so that it it matches up with the word size of your word ram remember our machine model assumes that you can do arithmetic operations in constant time if the numbers are not too big and so you can do this this update in constant time how does that look in the code um not too complicated actually uh the only change is if you um if you update the hash here that's the only real change from the previous slide you do exactly that computation that we had you subtract the first digit shift it by the radix and add the new digit and do one one computation with the modulo modulo the prime that's that's ravencarp string matching with the with the rolling hash

12:52 how well does this work the worst case is still n times m which sounds maybe disappointing but this only comes from the fact that in a very very unfortunate situation you might have to always do the slow check if you find for some reason a text where you always have to go through this expensive computation so this one is a bit is hidden but this takes m time because we're comparing strings here this is a string of length m this is a string of length m in terms of simple comparisons that needs theta and time and if you have this for every possible guess then you will need n times m but this is very unlikely if if you have a non-maliciously chosen texted pattern and in particular if you're looking just for the first occurrence it's astronomically unlikely you will all never see this really happen in practice it's more probably more likely that your computer is dying from some some solar layer or whatever and the expected running time adidas is optimal uh linear in in the text length and the pattern length and it has some some other nice features first of all it only needs constant extra space we're only storing the fingerprints and not some pre-computed other information about the pattern and

14:14 uh secondly this this algorithm unlike all the previous ones is easier to generalize to other scenarios for example two 2d patterns uh which in in other words are images pixel images are

14:31 not far from a two-dimensional text where you have rows and columns and a symbol in each in each position so you can use ravencarp style algorithms to also find patterns in 2d or higher dimensions and this is something where the other algorithms um don't seem to generalize well

14:50 Another question

14:51 okay that was not what i wanted i have another question for you to see if you're following along that's what we've seen so similar to the previous question a little test if you follow this beyond the superficial statements i made

15:05 A test

15:18 so give the question a careful read it says we're only applying the hashing part of ravencarp but we skip the check and what what can be said about the method and again several of the answers are correct so check all of them

15:48 and um i'm i'm waiting for the usual 25 people at least maybe for this one i'll give you another minute to think about your answers because this is uh it needs a little thought to digest all the different possibilities

16:37 all right there we go um most of you figured this out but i caught you with uh one of the others i'll lock your answers in now um so briefly um

16:45 Problems

16:55 the the algorithm uh can miss occurrences that's wrong because um that would mean uh that we have a different hash for the same string that cannot possibly happen and you all agree with this so most of you it can report false false positives uh positions where the the hash is the same but we didn't do the check so we don't know for sure but in some applications maybe this is good enough um depends the worst case running time now actually is linear and the reason for that is that we skipped the only thing that was expensive okay all the rest is just zoom through the text and do constant time update to the rolling hash the last statement is not correct because you do have to initialize the first hash you have to first run through the pattern for the very first beginning you can do updates in constant time whenever you move through the text after that but for the first value you need to find the full hash of the pattern and that needs theta m time and now in a very stupid scenario a user might give you a longer pattern than your text is uh you could have a separate check to say hold on guy you're man you're you're looking for something that's longer than

18:14 the text there's no way you can find this here but if you're not special casing this um your running time would be like this and not that all right um with that um we come to the end of unit 4 on the the elementary string matching algorithms and i've prepared a nice slide that summarizes the different pros and cons of the different methods um yeah that just works if i move a little bit to the right so uh we've seen the brute force method the finite automata kmp boy or more ravencarp and we'll see suffix trees the week next week probably

19:02 and they have different they have different pros and cons in terms of pre-processing time brute force doesn't need any here uh but the other methods all do some sort of pre-processing to become efficient and um here the details really matter um i don't know why i didn't put sigma here so it's the same thing the little sigma is the size of the alphabet um the search time here is given in the expected or in the typical case not the worst case you have to look that up but this is this is more of the the punchline that you usually need uh we you can ignore the last column for now this is just uh for for your reference when we come back uh from unit 6.

19:57 and again along the extra space you see how we finally got to constant extra space that's all about the elementary string matching methods and we'll continue with unit 5 on how to parallelize string matching