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

0:03 and then we'll do our break in the next section I want to briefly discuss the ren carp algorithm as the last example of string matching and uh slightly different type of algorithm I think it's interesting from many respects but again like the boy or more it's not part of the exam for us

0:25 uh but it has a few um it has a few other interesting characteristics um is worth knowing about okay where are we k mo brand has the best worst case that we've seen Bo Moore seems to be better on average at least for nonpathological text so what else really is there to hope for well both need uh extra space now I mean to be completely honest with you I don't think that's such a big deal because the extra space is as big as the pattern and we have to store the pattern while we're searching so it's if you if you ignore constant factors it's not such a big deal um but as a theoretical like I wish I had the little uh theoretician Professor on on the slide here uh at least theoretically speaking it would be nice if we can avoid that can we do efficient pattern matching more efficient than Brute Force without having this extra space and it turns out the answer is yes and the answer is interesting for other reasons it's the only point in the where we'll talk about hashing hashing in in principle is the idea that you take a complicated object and you reduce it to a single number an integer uh that's something used in computer science for

1:46 various things um it's usually introduced the context of hash tables as a data structure an alternative to binary search trees um and they have uh very interesting stories behind them that we won't get into but you can also use hashing more Loosely um to compute a kind of finger print and that's the sense uh that the Raben carp algorithm uses hashing for so roughly speaking the idea is we uh compute a fingerprint of our pattern and we compute Fingerprints of parts of the text and only compare the fingerprints first which supposedly is very cheap because they're all just short numbers um if the hashes agree if the fingerprints are the same then we check the actual pattern now I should I should comment on on the term fingerprint in this case if you think about human fingerprints then uh we think of them as unique and as far as I know they they are

3:08 yeah so fingerprints human human fingerprints are used as ID and and for authentication and all that uh I mean it's not so sci-fi anymore most phones have that so fingerprints for humans tend to be quite unique right if you take two humans their fingerprints are usually different unfortunately in computer science a fingerprint is not unique so our fingerprints it's it's a very standard um term where it comes from is instead of the entire human with all the complexities of your personality and whatnot I'll just take your fingerprint it's a short summary of what you are um that's the way in which fingerprint is understood

4:04 so don't think of authentication uh as in in in this section think of it as a short summary and now if um if you think of this from a from the perspective of of compression and retaining information if you have a really really long text and you condense that to a small number from a certain range there just too many texts for that number to be unique so you will have different texts maybe even of different length that both both get assigned the same

4:45 number so our hashes will necessarily have collisions which means uh there's different objects that get the same fingerprint and the whole story about hash tables is how to deal with those and so on but again um something we haven't got the time to

5:15 cover in this section it's convenient to assume that the the alphabet are just our standard digits then we can use as the fingerprint just numbers and and they have the natural meaning of numbers as writing digits one after the other um so here's an example of a text and a pattern and here's an example of a hash function that's what what is a hash function is what computes the fingerprint what computes the summary again in biological terms it doesn't make sense there's no function that takes you as an input and spits out a oh that sounds gross like chopping of fingers or so on uh let's delete that um in in the computer science terminology you have a way to input an complicated object and it computes a number for you and here we just take uh the number modulo a prime number like a

6:13 97 it's not necessarily Prime uh but no it is yeah okay um so we take our pattern now you have to take my word for it that 9,265 modulo 97 is indeed 95 not going to uh double check now but you're you're welcome to do it and uh what we do is we take portions of our text and also compute the hash so if you do this for 31415 modulo 97 gives 84 I

6:51 hope and if you take the next next digits 14,1 159 you get 94 and so so on and so forth um until at this point you indeed find ha the same that's an occurrence of the pattern so it has to have uh the same hash and once you find that the hashes of the pattern and this portion of the text agree then you have to do your character

7:26 comparisons at that level of abstraction the code for doing that is not not very complicated um we'll always restrict ourselves here to Hash functions that take a number and compute the remainder of division by a prime so I'll just leave it with find the suitable prime number um and the choice has has something to do with the performance guarantees at the end let me compute the hash of the pattern you take the entire pattern uh compute a number from it using essentially that scheme so you interpret the digits the letters as digits in a number of Base Sigma and compute the modules of that number with respect to M and then you iterate through all positions in the text you compute the hash of the appropriate portion of the text if the hash is agree then you still do the check of the pattern against the text and if it matches you return that position otherwise you continue so should yeah I should point out that this is not a constant time operation I'm I'm just writing equality on an entire string um assuming that this is is actually a loop over the characters that's just to keep the code a bit

8:48 shorter we never miss a match if we do that because if there is An Occurrence in the text then uh the hashes at that position and of the pattern must be the same and then we do the explicit check um and if the hashes don't match then certainly also that position of the text and the pattern are are different the problem with this code or why why this code is not exactly useful is that Computing this hash value of a part of the text also takes time proportional to the length of the portion of the text so it takes M time roughly because you have to at least read that part of the text and and deal with the numbers so it would give us an overall running time of just the standard Brute Force algorithm so why

9:43 bother the reason is that we can modify how we do this part how we can how we compute the hash of each of the portions of the text to be much much faster and then it becomes interesting again the way to do this is to update the hashes instead of recomputing it from scratch and I'll just show you in an example why this is possible um we do some pre-computation then we have one hash of a portion of the text so you should imagine the text has these nine digits and then it continues with six we're currently have the hash of that part once we're done with that we want to shift one character over to that portion now these two numbers if you just look at the numbers they're very different but they have a long part in common namely all the middle digits so how do I get from 41592 to 15926 well I subtract 4 *

10:45 10,000 multiply the number by one by by 10 to shift everything one position over and add the six and uh the magic of modular arithmetic allows you to do all of those oper operations on the remainders with

11:03 97 so here's that spelled out um that's the new hash we like to uh compute with the one position shifted over what we have is the old hash so this number modul 97 is what we know we can get from that number to that number if we subtract 4 * 10,000 shift by 10 multiply by 10 to shift all the ditches and add six okay um and we do then compute modulo at the end but modular arithmetic allows you to shift the mod inside so we compute the mod here first and take our our known hash from the previous position then we take four times the hash of 10,000 which we pre-computed and the rest of the operations are all involving short numbers so the important bit imagine these five digits are a thousand digits the length of your pattern then these two numbers are really big but all numbers in the second line are very small they're at most M and so if you compute the the result from that you get the next hash and at least on the word Ram all of that can be done uh in constant time so more specifically uh here's the full code um we use a Radix for our numbers and by and large you can use the

12:33 size of the alphabet uh a power of two is convenient to do the shifts with uh just shifting digits instead of a multiplication but that's um it's a minor difference then you have to choose your Prime to be um a large enough a large enough Prime so uh something bigger than Sigma for sure um maybe not

12:59 much much bigger uh if you do that all the numbers are bounded by this by this value so you can do it on a word Ram in constant time to update the hash and the update of the hash is is spelled out in this in this line and the rest has remained the same right we we find the hash of the pattern up front we compute the first hash from scratch of the first portion of the text but from then on that's same code as before whenever we have to shift we compute the next hash of the portion of the text using this update

13:44 formula now um the the analysis is a little tricky because we have this part where um we sometimes have to do the M comparisons that should be double equals so this is the expens ensive part that takes M comparisons and it's not so obvious how often we have that case if somehow the universe conspires against us there could be many many parts in the text that hash to the same hash value as the pattern even though they're not equal and so we might have to do many comparisons even though there are few uh occurrences to report or we report the first one anyways

14:30 if if you randomize the choice of your of your prime or or randomize the text the expected uh running time of this algorithm is is best possible linear in both order M plus n like KMP uh but the worst case still is this n * m if as I said the universe conspires against you and you always have uh portions of the text that hash to the same value as the pattern with without being an actual match uh but if you put if you put your Prime large enough and add a bit of randomization this is very unlikely and so it's it's one of those cases as for uh random binary search trees and quick swort where we chose a random pivot by and large it's uh it's fine to use it even though the worst case is not as good you can prove strong guarantees on the expected running time and and high probability bounds uh with also useful this algorithm can be extended to other situations where you don't have just strings but 2D pictures for example um the kind of fingerprint can be extended to that whereas many of the other methods like KMP don't don't easily generalize to that and coming back to this initial initial motivation it only uses constant

15:49 space because all we need to store are these extra hashes so we pre-compute the hash of the pattern and the we maintain this hash of the text that's all it needs uh plus a few extra extra index variables so among all the string meth string matching methods we've seen that's the most space efficient one well apart from root

16:18 Force I again have a a clicker question like the same type but I'll skip this one and you can do it at home ask if you have questions and I'll I'll close with a little bit of an overview of all the methods we've seen in this in this unit and another one that we will see later uh just comparing their um the different performance characteristics probably would have been better to ask you to do it and and read through the chapters but there you go uh for