Video 5-4: §5.3 String matching with duels

0:00 <Untitled Chapter 1>

0:02 in the previous subsection we talked about periodicity and we noted that a periodic string is repetitive and this helps for string matching but aperiodic strings seem that fact seem not to help with string matching so in this subsection we will see how to make use of the fact that a string is aperiodic to also speed up or simplify the matching in in our application of string matching for that we need another definition and that is a witness for non-periodicity it's again it's a simple definition but it's a bit of a mind-boggling uh game with indices so i'll show an example in a second but uh try to digest it for the moment so we're given a pattern just a string and suppose it does not have a period p so p is p is some number um i mean it's uh clearly between 1 and n excluding n so it's a non-trivial period and we say p does not have this period so that means if i try to stick the two copies of p on each other where i shift here by p i must have some mismatch so these are not the same these two strings here they're not identical

0:32 Periods and Matching

1:33 so that means there's some place where i find a mismatch okay and this is this is my witness intuitively there's a witness there's one position that witnesses for the fact that these are not the same so it's a witness against periodicity p and formerly w is um

1:59 okay we want a picture here so uh w formally is this position in the in the shifted copy and then this is w plus p right in the pattern so uh it's a position where the omega sorry this is omega not w um it's the greek w but um to be consistent and fair to our great colleagues i should call it by omega because that's what it is um even though w would make sense because it stands for witness nevertheless just the name uh the omega character in p is not the same as the omega plus p character and these are exactly those two uh again a simple definition right whenever we have a non-period there must be a mismatch somewhere along here otherwise it would be a period so far so good how can we use this for string matching

3:04 okay again if a pattern does not have this period then suppose we try to align the pattern with the text and uh we try to guess there's a match at position i now we also shift the pattern along itself with distance p so here again this is p so there could be another match at position i plus p but if the pattern does not have period p we cannot possibly have both

3:40 either the position i is a starting index of a match or i plus p but not both because if both were a match we would have find we would have found p here and we would have found p another time here and that would mean these are all the same that would mean p has this period but we assume p does not have this period okay so simple observation again uh if you spell out the indices there's um a position if you check the the second potential occurrence there is some mismatch here at that omega respectively omega plus p within the pattern in the text i have to add the offset i plus p so that's this first part this one can be the same as p of omega if this were both a match starting at this then this omega character would be aligned with that position in the text but do you know because of non-periodicity because of this witness that this position the pattern is not the same as this position in the pattern and that again that would be this guy which is aligned with the position in the text at um i plus omega plus p but of course these two things are the same right these are this is the same position just written

5:06 in different ways so that cannot be the case these are equal but here's an unequal sign so that would be a contradiction so we can prove formally a proof by contradiction shows that if the pattern does not have a period p then at most one of those two positions can be an occurrence that's the notion of a dual we will uh let i and i plus p fight a dual and the duo will be comparing one position uh in the text and the outcome of the duel will only have one survivor only one of the two guesses is still alive and the other is definitely excluded not possible anymore it could be that both are non-matches by the way the duel only says one of them dies cruel duels that's that's how it is and uh yeah this is what i just said and i'll use this little figure later

6:15 i want to discuss this again on a concrete example because the concept is kind of clear but maybe you want to see this spell out in a bit more detail to see how it really works so the first step for string matching with duals is to compute the witness table so that's this

6:39 that is just for all possible non-periods i should say this we assume here appears a periodic if p is periodic then we don't have to go through this hassle we already know that it's it's repetitive and we can deal with this separately if p is um this is a capital p for pattern if the pattern is a periodic that means for all the periods from one up to half of the length of the pattern we find a witness against periodicity and this is what the witness table stores it just stores this omega that i introduced just before so let's uh briefly go through this here's my pattern and i shift it over by one position so here's the pattern shifted by one here's the original pattern

7:38 and we see that for example this position is a mismatch so this is not a period one is not a period because there's a witness against periodicity at position zero it's zero because here is the zero and we have to align this with the position omega plus p zero plus one okay

8:03 if we shift the pattern by two we again find there's a mismatch and uh there may be different mismatches but uh here's only one and uh this is at position three so our omega for the table is three if we shift the pattern one more over we actually have several mismatches but let's just pick one uh and uh one example is is to pick omega one so we put that in the table and uh well this would have already been enough we already passed uh half the length of the pattern but we can continue in this case also four is not a period so just uh for sake of of completeness here's another omega and even for five we find a mismatch um so we can fill one more table and three that's the first step given an aperiodic pattern you can compute all the witnesses against all the periods usually we only run this from 1 up to length of the pattern half rounded down but there's no harm in doing it further if you if you can

9:19 one one more remark if you wanted to do this for six you will see that actually p has the period six so there's no witness against periodicity six because it is periodic but we really only need it up to three in this example so these are not strictly necessary for what will come later

9:43 all right uh how do we use this for excluding matches in a pad in a text so here's our example text now let's try to find matches of our pattern in this text initially if we know nothing about the text every possible position between one and whatever length of the text minus m but here um there are many possible positions in this text where an occurrence of the pattern is possible now we can make a dual we can fight the dual between two of these positions and one of the positions will necessarily die so we have reduced the number of possibilities by one and by continuing with the winner of the duel and compare it to another position we can always decide in one more dual uh which of the two candidates is currently the the possible one okay let's see how this goes uh we start with the first two positions so let's guess that the pattern starts either at position zero or position one we know that the pattern is not periodic with period one so not both will be possible how do we use this fact well the distance between those two is one so that's a p of one the period that we would need is one we don't have that period here's your

11:02 witness against that periodicity it's just the entry from that table and look here i aligned the text with the two potential matches and you see that uh here's our witness this is our omega and now we look in the text at this very position and the character at the position 1 is a b [Music] now it happens to be equal to this one but what's more relevant is it's not equal to a which is the uh omega character in p

11:38 so that means the later shift the one with the larger index the one here is not an occurrence so well rest in p is number one and we continue with zero so we can compare zero with the next possible um shift that's at 2. we do the same game this time we find that our witness is is further back in the text but we magically again know we only have to look at this one symbol in the text at position five it's again a b coincidence what's more important it's not a c which is what we find if we look at the pattern position omega plus p and you can check that the math works out in this case so this is again it's also position five so this means the earlier of the two proposed matches is not possible that's the zero so uh again there she goes

12:41 and uh the survivor is number two so we continue with number two and compare it say with um a potential match at three uh now we have to move the pattern a little bit so that the two positions are aligned potential match at two potential match at three again the distance between those two is the potential period but we know this is actually not a period so we have a witness against that the witness is here so we check this position in the text and uh that's a b most known for not being an a and that means the later potential match again dies so that's the three and again what remains from this is after three comparisons um out of the four potential uh matches that we checked at zero one two and three only one remains the one at two now if you check this here this is not actually a match but that's beside the point the important lesson here was with a single character comparison you only check uh one comparison here is enough you can exclude an entire potential match an entire guess okay so if you want to turn this into a more systematic algorithm here's here's what you do in all that follows i will assume that the pattern is aperiodic

13:56 String Matching by Duels - Sequential

14:08 so what you'll have to do is you will first compute this witness table and in the process of computing this witness table you will either find i found all the witnesses and then you know it's aperiodic by definition or you find in this process there is no witness against this periodicity because actually this is a period and then you know the pattern is periodic and you do something different you um recurse on the periodic part etc um that is beyond the scope for for us today uh we'll only focus on aperiodic patterns now uh let me start by setting this parameter that's just the length rounded down it occurs a couple of times so i wanted a shorthand then you compute all the witnesses for all these non-periods and then you do a clever thing um in the example we just randomly i well supposedly randomly just compared certain positions and let them fight a dual what you really do is you take blocks of size u of size mu in your text and these are just the adjacent mu positions and now you run mu minus 1 duals between those positions you can for example go just left to right for this for this simple version remember we're still i'm still talking about the sequential algorithm for now

15:39 we'll talk about how to make it parallel in a second okay in each of these blocks all the distances all the two positions if i'm if i'm in such a block

15:56 of size mu so this is zero up to mu minus one whatever two positions i pick uh the distance will be at most mu and that's important because that means we can use this distance and find a witness against periodicity okay we cannot use this with arbitrarily spaced apart positions because then we would need a witness against the period that's longer than the pattern and those can't possibly exist

16:28 but within this block we can fight the duals each duel eliminates one of the new potential guesses so after all these duels there's at most one left and for each of these blocks we then just use our sequential naive guess character by character we check if the potential match is an actual match that's similar to what we did with ravencarp

16:57 ah so need a bit space here um how long does this take well this first step is trivial this step um you can compute all the witnesses against periodicity or find that the pattern is actually periodic in linear time we'll talk about this in a second a little bit more the more interesting parts is steps three and four for step three we have n divided m blocks roughly it's actually n divided mu but mu is is m divided too so in in big o notation that factor of two doesn't make a difference so we have n divided by m blocks and we find m duals well actually mu minus one but let's be generous we find m duals in each block order m if you multiply that together you find that it's is actually linear in the length of the text right remember the important point here is that every dual just needs a single comparison a single character comparison between text and pattern so every dual can be implemented in constant time we fight m duals per block and have n divided by n blocks that's a total of order n symbol comparisons and

18:18 what remains is to do this check so we have again n divided by m blocks but checking an occurrence in the trivial way just needs m comparisons so that's another order n comparisons for the step number four so um one outcome of this of this of this unit is another worst case efficient string matching algorithm essentially is the same guarantees as knuth morris pratt achieved in a slightly different way now there's a slight catch to this in that uh we do have to compute uh we do have to compute the witnesses against periodicity and as you'll see in a second we actually use something like kmp for that so it wouldn't be possible to simply use this and not know about kmp you have at some at some point or another you have to fight the game and dive through the details of knuthmore spread

19:29 but so much for the sequential algorithm on string matching by duals as always if you have questions on this or anything else please use the lecture back channel or slido to ask your questions

19:51 if there are no questions about the sequential part then let's look what we have to change to make this a parallel algorithm and uh well let's flip back and forth just one more time you see i made the font a bit smaller so that we have space to fit the the second part on the slide but the algorithm is really exactly the same and there's there's not not really anything that uh i had to change here so we do the same steps uh of course we will have to talk about how to do these steps in parallel but the core algorithm is still the same and so how do we parallelize this and uh well i'm coming to the picture in a second but let's uh first talk about the simple things the first steps trivial again just compute a number but the second step um is actually not trivial it's actually very complicated uh i'll come back a little bit to this it turns out you can do this in time log squared m and on some models of our machines maybe even faster how can we parallelize the duals within a single block that is the the main innovation of the main observation here previously we would have to do uh one dual after the other

20:15 String Matching by Duels - Parallel

21:12 so we needed order mu time in total in the sequential model but it turns out that you can do a lot of these duals independently suppose that your mu is so this would be mu is equal to eight and uh suppose these are your positions in the text there's uh position one two etc you can have zero and one fight the dual against each other and at the same time two and three and four and five and six and 7 they're all independent there's no data dependency remember this is what i said many times before strong dependency in the data between one step and another is what kills parallelism but here we don't have that the duals that talk about different positions can run independently and nothing nothing has to wait for the result of the others

22:10 and then we have one of the winners so here say zero has one and here two has one and here five and uh here's seven and then you find another duel between the winners of this first round and here the same and again these two are independent there's nothing that uh these two depend on each other so here is say zero one and here five and then uh as a last round here you fight another duel uh with the winners of these two so it's it's just fighting a tournament and here 5 is the only one that remains but that's just an example i made up so the important part is this is a complete binary tree and we know the height of a binary tree is log of the number of leaves so this has log mu height

23:07 and you might recognize this conceptually this idea of doing something that used to be sequential linear and now becomes logarithmic that's very much the same as we used it for computing the sum of an array or the prefix sums then as the second step there we also went from an unbalanced tree to this balanced binary search tree and used all the data independence so that is um how we get the third step in log mu parallel time and their work stayed the same just as when we computed sums

23:46 the fourth step uh is actually fairly simple you can check all the anno review guesses in parallel and for that you can use what you did in the tutorials

24:03 we will talk about the tutorials later today in in tutorial 4 you actually explored exactly this step how to check if a certain guess in the text is a match of the pattern in parallel and well as you as you will remember it depends on the machine model what the exact result here is

24:30 okay so the final parallel time is log m for the matching part that comes it's just again uh mu and m are the same in terms of big o here and because it's inside the log it's really even even without it's just a constant difference and linear work so this is this is all perfect um it's perfectly fine up to uh the matching part um the pre-processing though uh we still have to talk about and um if we do this sequentially you can do something similar to the kmp failure array and maybe this is not very surprising if you think about it we've already noticed this very very close relation between periods and the kmp failure function now the only thing that you would need here is to find these witnesses but modifying the kmp failure function algorithm a little bit actually produces these these witnesses so you can do this in in the optimal sequential time in parallel it becomes more complicated and there have been substantial improvements over the first more more simple method and then using more sophisticated techniques you can get also the preprocessing in parallel log m time and work efficient but that technique is is beyond the scope of this class so uh what what you're supposed to know is

24:59 Computing witnesses

26:03 Parallel Matching - State of the art

26:04 just that this is possible so the state of the art for parallel string matching is you can do log m time and work efficient and this is in fact the best you can hope for on the crew ram or standard model where you allow concurrent reads but you don't allow concurrent writes they have to be exclusive

26:31 the lower bound essentially comes from similar arguments like for the prefix sum there is indeed if you go to a different machine model if you go to the concurrent write model even in the the weak form that all the concurrent writes have to write the same value you can do the matching part in order one time again this is exactly what you do in the tutorials but the pre-processing doesn't work in constant time the best well it's i think it's also known that this is the best possible so you need this log log n time but that again uh so this is just um for your curiosity

27:14 uh i will not expect you to know this and uh i will not be able to talk about um about these results okay that brings me to the end of of unit 5 on

27:34 on parallel string matching we've seen that this method this notion of periodicity helps us to break things into two parts we had essentially two different algorithms one for periodic patterns that i didn't talk about in detail and one for aperiodic parts where we did the how to parallelize things apart from the preprocessing and this this brought you not only a new sequential algorithm but also the best possible parallel string matching algorithm and i hope this this teaches you that sometimes you have to look at the problem from an entirely different perspective and then suddenly you notice something like these duals help you approach a problem very differently and then suddenly achieve achieve results that didn't seem possible before