Video 5-3: §5.3 String matching with duels

0:00 Intro

0:03 in the next sub section of this unit we'll put these two things together the ideas from simple methods of how to parallelize string matching and this new concept of of periodicity of strings and it will lead to something that's called string matching by duals if that doesn't sound exciting i don't know what uh let's see where that's where that comes from

0:23 Periods and Matching

0:30 another little consequence of having a a period is that you can align the strings on top of each other and if you don't have a period there must be a reason why you don't have one so uh let's assume that if we have a given given pattern that does not have a certain period p then that means there must be a witness position that shows us why there can't be this period p right um and well this is denoted uh by omega here little omega so it's just the position in the pattern where if you shift it over by p positions you have a mismatch that position then witnesses against the period is it against the period p right is it clear like when i have a non-period p some number that is not a period of the string there must be some position where there is a mismatch otherwise it would be a period

1:42 pictures if i shift this over by p and it's not a period well there must be one position here if these are all matches there must be one position where the two characters are not the same

1:59 up here in there otherwise it would be a period and so then this position is our omega this is omega plus p okay that's a fairly simple concept but it's quite quite interesting and useful because it allows you to exclude guesses and here's here's how if you have a pattern that does not have a certain period p then whenever you have two positions in the text that are p apart only one of them can be a match maybe none of them is a match but they cannot both be a match simply because that would mean a contradiction according to the witness so suppose both were a match then we would have the position starting at the second occurrence and omega positions into the pair into the pattern so that would be the same as

3:05 p of so that's the position in the text and that would be the corresponding position in the pattern but uh this is not the same as the position p shifted by the witness definition but this again would have to be uh the position in the text that that's using the same same any same equality here it's just uh using the second match and these two are the same so right the the parenthesis doesn't matter so these are not equal according to that

3:42 and that's a contradiction because i mean it's the same the same position in the text so again if we have a non-period p out of any two positions that are p apart in the text i and i plus p only one can be a match or maybe none another simple observation but again useful because now we can do something that's called a dual between those two positions we can we can take those two positions and say by checking the position uh for the witness character against the text i will either find a match with one or with the other characters so there's there's the two characters in the pattern the one at the witness position and the one p shifted and the text can at most be one of the two right so that's again spelled out what they're what's in the inequality above and so the other can't be a match so it can be excluded that's how we can get rid of guesses all right let's see an example um and uh note here that that p is a periodic

4:50 Dueling example

5:11 that's slightly better uh we will discuss this algorithm only for a periodic strings uh and the periodic strings because they can essentially be reduced to their period period the repeating part um they can be handled somewhere similar but we we won't discuss all the details here it's just um the the high level idea again uh but the example for now um works fine with this string because it is a periodic

5:42 and let's first compute the so-called witness table which is for all non-periods what is a witness against this periodicity and you can fill this intuitively uh like it's not the efficient way to compute it but it's the the manual um way to to see what's happening if we shift by one then we could potentially have period one but well we don't have period one because there's a mismatch at this position so there's a witness against period one namely the index zero in the pattern that's this index and if you shift by one you find a mismatch with the character at i plus p one zero plus p is one so that's what we compare with here okay so two things the string does not have period one and we have a witness for that none period

6:42 if we shift by one more the string could have had period two but actually it doesn't because at this position you find a witness against this period again the top number is the one that we take in the witness table and if you add two you get to a different character in the pattern i think the game becomes clear we find the same for shift by three so these are different so we put the one into the witness table and even even four doesn't work we still find a witness against that and five doesn't work either because of this c right it doesn't occur anywhere else

7:23 and that's it if you check six is actually a period of the string this is only one character matching but at least at least not not nothing so and we've proven that by just exhaustively checking all others and writing down the witness against them and now uh let's let's play the dual if we have this text and we try to find the occurrences of the pattern in this text now i know there's only one c and you can already kind of guess manually where the occurrence could be but that's not what we want uh we go strictly by these by these duals the first two is we can play position zero against position one so guess i equals zero against guess i equals one that means we have a potential period of one but we know it's a non-period and we have witness against it so we check um the the position t equals 1 is a b and that's not the position of that's not the character of the pattern at omega at which would be an a right

8:46 so we cannot have an occurrence at one we might still have an occurrence at zero we can't tell at this point but we've excluded from checking the witness position in the pattern against the corresponding one in the text for the two uh or the two potential matches for the two guesses that at least this one is excluded

9:11 let's play position zero against position two so remember after this first round zero was still in the game it could turn out to be a match from what we've learned so far so we now play zero against 2. again we have a witness against this periodicity so we won't have a match at 0 and 2. and in this case 2 says we check position 3 and if you compare the character at omega plus p with um so

9:50 let's show in the picture what's going on so this is one one potential match this is the other potential match and omega 3 means we're taking this character and this character

10:14 sorry we're taking the three and this one zero one two three so we take this one and okay sorry the pattern is longer that's two four seven seven that's why i didn't overlap so we take these two

10:43 um we pick the character in the pattern here which is the c and it's not a b so we can exclude the zero this time right the the character that's matched by by this guess to that position in the text corresponds to a mismatch so we can exclude the occurrence at zero no occurrence at zero potentially one at two still

11:15 so next one is we compare positions two and three so again this one seven characters this is surprisingly hard to do okay uh our witness is at zero so we take this one and this one now we find the occurrence in in this one in the further shifted pattern is an a which doesn't match the b so we can from that you will exclude the position three okay that's that's how you go through uh it's a little tiresome in the example to check but you you always do just a constant number of character comparisons between pattern and text at these positions of omega omega plus p and so after each dual you can exclude at least one of the potential guesses

12:17 and so that brings us to the following algorithm how you make use of this dualing process and as i said before uh for what i described here we'll assume the pattern is aperiodic and we'll cover the the periodic case only in passing by saying you can do it somehow similar uh we first pick a block size which is roughly half of the length of the pattern

12:46 we know that the pattern is a periodic so its smallest period is bigger than m m half and that means we can compute witnesses against all the periods up to this m half okay so a periodic means these exist

13:13 String Matching by Duels - Sequential

13:15 um [Music] and then we look at blocks of the text of new consecutive indices so we block the text up and this time non-overlapping and in each of these blocks we run duals to eliminate all but one guess so why do we pick the block size like this uh because that's that's the potentially largest p for which we have a witness against that period we only assume p is a periodic in the previous example we had a pattern of length seven and the longest the shortest period was six so we could go further up in general if we just assume a periodicity we can only assume that there's a witness table up to m half that's why we have to choose the block block size like this a little more conservative we run these duals as we've seen in the example so out of each block at most one guest can survive all others are eliminated in one of the duals

14:21 and that means out of every block we only have one guess left so we can check all of those roughly n divided by m guesses naively and still stay in in linear time the length of the text okay that's that's the idea this is all sequential for now we haven't touched on on parallelism yet i want to briefly go through the individual steps to convince you that it's another worst case linear time method uh the first step is just computing one number that's that's trivial uh the second step computing these witnesses i'll comment on very briefly later but it's essentially a twist on on kmp and if you've seen the connection between the shortest period and the failure function maybe this is not so surprising that the two can be reduced to each other the third step has n divided by m blocks roughly and we do m m duals in each so multiplying that out is linear order n and similarly in the last step we have n over m blocks and at most one guess survives well one one guess survives from each block and we have to check with m comparisons in each block in each guess that's another linear time where they're in so overall we have another efficient string matching method

15:48 it has this blemish that as stated it only works for these a periodic strings that's why in the previous section i didn't include it because uh it doesn't really have many advantages over the other methods except for what's coming now

16:05 String Matching by Duels - Parallel

16:08 and the big advantage that it does have is it works in parallel so this first step um i mean the all the steps basically stay the same but we have to see how we can parallelize things

16:22 so the first step there's nothing really to do the second step is possible to parallelize but it's very tricky i will only i will only tell you what is possible and a a reasonably complicated method gets it down from from from m to log m squared uh but this part will be beyond the scope of the course uh but what's nice to show is the other parts so for each of these blocks each block can be treated in parallel they're embarrassingly parallel right they don't depend on each other so that's that's great and the duals can be laid out as a binary tree like this if you were if you were to play the duals like in the example um always keep the surviving position and compete against the next free position you haven't tried then the next duel would always depend on the outcome of the previous and that's bad for parallelization but if you lay them out like this then these can all be independent the bottom row can all play in parallel and you don't need to know what was the winner of each to play the others so like a tournament and then you keep the winners playing against each other until in the final there's only one one guest coming out as a potential

17:42 match and well the parallel time is the height of the tree we've seen this in in unit 3. so that's where this log mu comes from rounded up to be precise that's the number of duals sorry that's the was the number of duals that have dependency on each other that's the parallel time

18:08 uh and for the last step we can do um [Music] one of the algorithms we've seen before in the in the first section for example the crew ram that again does a binary tree to do the parallel end

18:30 yeah unless this is uh maybe this is this is obvious to you but uh this way of reordering binary operations into a binary tree that's exactly what we did for the prefix sum problem in unit 3 that was the first problem we really looked at for parallelization and and you see that this similar idea is resurfacing in many ways here

18:58 um right so the matching part what i mean by this is is this one the part that does all the duals and checks the surviving guesses that's the matching part and that can be done in log m time parallel time and linear work order n work so that's pretty much as good as as possible the only slightly more complicated step is this second one so to compute the witnesses uh in in a sequential algorithm that is in would have been in scope of the class but since this is about parallel algorithms i wasn't sure if that adds much to it a similar algorithm to the computation of the kmp failure function can can do this sequentially in theta m time and the parallel algorithms unfortunately are much more complicated

19:26 Computing witnesses

19:59 and so i'll just state the results there but we won't look into those i want to finish that part and essentially string matching in the way we've seen it by briefly looking at what's what's known in theory how quick you can do a parallel string matching if you use this most fancy sophisticated way of computing the witnesses you get an order log m time parallel time and work efficient string matching algorithm that can run on on this crew ram that's pretty much the best you can do in this case you can prove you can't really can't really simplify or speed this up if you allow concurrent writes so again this letter is the important part you can do the matching part in constant time this is not obvious for the duals but it can be done and we've shown that the last step can be done in constant time that's the parallel end but it turns out that pre-processing finding the witnesses cannot be done in constant time you still need this this log log m curious time uh for computing the witnesses and you can't really improve upon this well that's more i mean that's for your curiosity say

20:05 Parallel Matching - State of the art

21:28 as you've noticed i haven't really told you anything about the details of these methods so that's just more of an outlook okay what you should keep is is all the things about the embarrassingly parallel tricks you can often get um a work inefficient but parallelly fast algorithm by just doing all the tasks in parallel in a simple way and then you can often get the work down by using blocks and using an efficient sequential algorithm inside the blocks but to get beyond that uh you often need problem-specific insight but that's it for some for many practical applications it might be good enough to do a combination of of blocking of the right size and some reasonable sequential algorithm inside the blocks

22:20 that brings me to the end of of section of unit 5 and pretty much the end of parallel processing for now