Video 5-2: §5.2 Periodicity

0:00 <Untitled Chapter 1>

0:01 in the next subsection i want to introduce a notion on strings that at first seems unrelated to our task but it will be the the key ingredient to a different way of string matching that then is is more useful for for parallel execution and that's that's periodicity so let's first start with the definition and i'll walk you through the example then if we're given a string as always and characters let me say it has a period p so p is a number um and it has a period p if for all positions if you start at the i position and you add p you find the same character all right there's some boring consequences uh p equals 0 is always a period but none that tells us anything and any number bigger than n is is a period just because then this for all statement is empty this iterates over all numbers in this range and if that range is empty it's an empty statement so again uh these these are technically fulfilling the definition but will not really regard them as as periods there are trivial periods if you want so we'll we'll exclude those from the discussion but strings can have non-trivial periods and here's an example so if you if you take this this string

0:20 Periodicity of Strings

1:26 written down here and you take a copy of that shift it over by six positions so you match position zero right so let me maybe write down the indices just once i know is this

1:50 and up here as well then you see you match position zero with position six that's a shift of six and if you do that all the characters match up and that's the condition that we need for a period

2:08 there's another string and that has a smaller period and so you see a small period means there's a lot of repetitiveness going on in the string and in particular we'll come back to this but if if this period is bigger than half of the string then as in this picture you have some overlap between between prefix and suffix but that's about it if the period is substantially smaller then you see there's a a certain range this this aba that repeats over and over in this string and we'll we'll use this fact in a second

2:50 um i want to connect this if you if you've seen the picture of the previous slide maybe this already sprang to your mind we've seen something like this before uh and indeed we have um so in other words if you have a period and this p is the shortest is the smallest number p that is a period apart from p equals zero uh then this is also uh if you take the first n minus p characters that's the longest prefix that is also a suffix of this of this string so i guess um

3:34 we want to have the picture for this if the minimal period is p then that means if you take the first so in so many characters they're down here and minus p that is also a suffix of this part okay so

3:58 this string here is our s 0 up to n minus p and this here is the suffix starting at p okay sorry this should be a little clearer because the square brackets are different

4:23 uh i guess i should have said here these are equal right what's also true is that the the longest prefix that's also a suffix of s has length and minus p and that's something i told you in last unit please memorize you remember the red box that's exactly the the failure function of the kmp algorithm so in short the statement here is if a string has a minimal period p then you can get this p from the last entry in the failure function it's the failure link of the last state in the automaton okay just because if if you had matched the entire pattern and you now find something you want to continue you have to shift this over exactly as much as as the period is

5:26 a second small observation about periods is this lemma uh if you have a string that has two different periods p and q and they're not um too large so their sum is less than n then you also have a period for the greatest common divisor of the two and for that

5:51 i just want to give you a proof by pick by example now this is not in general a valid proof and the formal proof used to be part of the tutorials but it was never really very insightful and we're not using dilemma massively

6:07 that is okay this is not working let's do it this way i might have made this a bit short let's do a small example so let's suppose the string has period um it's boring let me make the example a little bigger

6:51 otherwise we don't see the interesting part of the statement i want to have two numbers whose greatest common denominator divisor is is not just one but also i need them to be in some less than n so the example has to be a little bigger so let's take a period of six

7:32 and so the implication here is these are all the same uh and suppose we have another one so i'll just put this in the same as as the other one let's say we also have a period of four

8:10 which first of all just means that these are the same but of course equality is transitive so it's also these are the same and so let's let's suppose we put an arbitrary letter in the first position say this is an a now if that's an a of course this is the same a and so by these equalities it immediately implies that this is an a and this is an a and look what happened so if you put this a in the fourth position into

8:52 this one then you get an a here so a also must be at the second position and so you see how you can you can fill um with these games you can feel every other letter which means that the string actually has a period too so you could do the same if you put an arbitrary letter in the second position it is inherited here and here but also here because it's also the second position so it gets into here and here so that means it goes into the fourth position so after fixing the two letters the first two the equalities that are implied by these two periods four and six imply all the letters are filled and that's another way of saying the period is two

9:42 as i said this is not a proper proof of this statement because it's it's only shown on this example but that's the essence of what's happening and i don't think the formal proof in this case is really insightful

9:59 Periodic strings

10:03 so now after introducing these are this idea of periods and the idea of shortest periods and the previous lemma is just an acute way of finding the shortest period you can try to look at the string and guess what periods you find and if you found two you can always jump to their greatest common divisor and get a smaller period potentially so that's a way to find periods by hand the important notion here now is that of a periodic string

10:39 and we call the string periodic if its smallest period is less than half of the string and remember that means you shift the string over by less than half of it that means it has to repeat at least another time um

11:00 maybe repeat the little picture again just conceptually then that breaks the string into these blocks this must be the same as this because it's the same string oh come on

11:30 and then because of equality you have the same block here and that copies to here so the string consists of the same block repeated until at some point it stops in the middle of a repetition

11:57 and so we can say this is a case where s is highly repetitive the more precise statement is stated here s is determined by some smaller string of length p and you keep repeating this until you've filled enough characters and the other case is an aperiodic string and in a sense the periodic strings they're kind of redundant in that they are not really n characters worth they are determined by much fewer characters but the aperiodic strings cannot be written in this way and so the formal definition is shortest period is is bigger than n half

12:36 all right time to wake up and see if this notion is is clear enough okay 24 let me get up to 30. a couple of people still typing all right seems all done

13:38 i wanted to click on log in this case it's not periodic which might be surprising the thing is this string definitely looks boring right it has lots of repetition uh but it's not periodic according to the definition we've just seen and the reason is that if you take this string many a's but then a b at the end there's no way you can overlap this with itself without creating this okay i didn't switch the thanks

14:14 Clicker Question

14:18 um so correct answers no as i said um the reason is that uh whenever you shift the string by any amount over to the to the try to overlap with itself you will always place the b on top of an a so you can never have this match so the what's the period the shortest period of this string it seems any p doesn't work but there is always a shortest period which is n if you shift the string entirely behind itself then by definition it's a match because there's nothing to to align anymore

14:57 so shortest period is n which is definitely bigger than n half and so it's a periodic so don't be tricked into thinking that periodic necessarily means repetitive and vice versa it's not exactly the same and indeed this is a fairly fairly restrictive and concrete notion in this periodic