Video 4-5: §4.5 The Knuth-Morris-Pratt algorithm

0:00 Introduction to KMP

0:03 so in the next sub section we look at the knuthmore spread algorithm which will be the final answer to how to reduce the space from the string matching automaton that we've seen in the previous section the main innovation here [Music] will be that we don't really go using a dfa as we've done it so far because that inevitably needs storing all these transitions so we need the table that has the states and the alphabet symbols we try to get away from that

0:39 the key insight here is if you remember how we constructed this dfa there was this state x which is the last state we reached with um the pattern where we chopped off the first symbol and then the last the next step was always copying things in this table or simulating the automaton for one step from this state x how about we do this last simulation during the matching phase as opposed to as opposed to computing it up front

1:10 it's a little unclear how to formulate this nicely in in automaton language but it's possible and the way to go is what people have called failure links this is not how the idea originally was explained but i think it's the the most intuitive way to think about it so we have our automaton as before and every state now has just two outgoing arcs one that goes with the matching character to the next higher state and one other edge which is a failure link and these failure links marked with this with this cross they are to take if you cannot follow the match link but they don't consume a character so you just follow that link and you still try to match the same character in the text that's the that's the key innovation and that's what you can do with these automata that wasn't possible with the dfa that gives them just enough flexibility to allow the smaller space you occasionally have to follow several failure links if you're in state 5 you couldn't match a c because the next character was an a then you would have to jump to three and you can still match the b so you have to follow another one still can't match the b so you have to follow another one

2:30 that can take some time so you have to follow several of those in a row because they don't consume a character well we'll see how this works let's go through a full example briefly just so that this this idea is clear and

2:48 Example and mechanics

2:52 we start in state 0 then we read an a so after that we go into state 1. in state 1 we can read a b and go to state 2 and then read and a go to state 3. so far everything fine read a b go to state four read an a go to state five and at this stage we can't read the next character which is a b and the match transition would be a c so we can't go there instead we go to state 3 back and try again now in this case we can read a b so that's that's it for that point and we move move to state four in four we can actually read the a but then comes an a and not a c so again we can't follow the the match link instead we jump back to three and then try again but three also doesn't accept an a so we have to follow another failure link back to one and from one we can still not read the a so we follow another failure link back to zero and only in zero we can finally read every character because either it goes to the match link or it stays there and then it's consumed and gone in this case a actually leads us to one

4:12 so we can move this forward and well a few more so we go to this this and four and that's the end of the example so i changed the text a bit here if you remember from last time um another way to draw this is uh if you try to you remember we had guesses and checks for these algorithms so initially we tried to find the pattern starting at at the initial position and we could get till the fifth character but then there was a mismatch and so this mismatch meant we go back to state three which means now we have three letters of the pattern that are still in alignment with the text and we try to go from there so that's the same as shifting this guess by a few positions forward so that instead of five we now have only three overlapping with the text so we moved it forward by two and we don't need to check these these three matches we know that they are matches that's encoded in the automaton

5:24 and then in this case we could go forward um and then this was the case where we had to go several steps back before we could match it again and so only the last one determines how long you really shift the pattern is it clear how the automaton works through the text try to match the next character if it doesn't work follow the failure link and keep that character

5:50 Worst-case analysis

5:50 alright let's do a quick wake up and test if you're following along is again one you have to read uh carefully we made it you made it guys uh all right

7:05 most people seem done three two one and locked and so we have a variety of opinions uh the right one is this one most a few or the the largest bar at least

7:29 and so i mean this one we could go up to m steps the length of the pattern in an in a completely degenerate case so for example if the pattern often in this string matching

7:48 [Music] pen doesn't want okay if i write with the mouse this will look a little less nice if the pattern consists of m occurrences of a what if i could charge this or if that's the problem

8:10 if the pattern is just m a's in a row then the failure link automaton will always just go one step back and so if you're in the last step and read a b or try to read a b so you're in state q minus one m m minus one uh you try to read a b but there is no b so you go back to the previous state q minus two you try to read a b but there is none so it propagates all the way through to the beginning

8:44 Pseudocode implementation

8:44 all right if we encode what we've done in the automaton in pseudocode it looks like this it is exactly what the example showed you on on the automaton just um spelled out in with variables there's a step where we compute the failure links so remember the automaton now is is actually really simple the only variable thing is the failure links the match edges are always just using the next character in the pattern and the only other thing we needed to know is for each state where does the failure link go to and so we can use a single array fail that tells me for state q the failure link goes to fail of q uh that's all that we need try to rescue this this pen because it's a little convenient to write on the slide

9:47 now we have we have two variables here once where we computed the failure links one is encoding the guess which position in the text is is the one we're looking at

10:00 that didn't really work so it's it's not the battery okay we'll have to do without one is the current position in the text and the other is uh the current state in the automaton queue and so while we're not done in the text we try to match the next character and if that matches we move with the match link that makes the state one bigger and we move one forward in the text so that's the the position in the text that we that we currently consider it's it's not really the guess it's moving alongside with the position in the pattern if we reach by that the accepting state then we found a match and we return where it started which is q positions or m positions before

11:00 if we couldn't match then we have to follow a failure link and here we do this by following the failure link except in the state 0 when we're in state 0 then there's no failure link really for that one it just stays where it is and if we're in state 0 then we consume a character right so at some point if we can't match the character at all we have to move forward so state 0 is a little bit exceptional here which you can also see in the picture state zero doesn't have a failure link

11:39 all right so that's that's the code for the knuthmore spread algorithm the only thing that is missing is how to compute the failure links and we'll come to that in a second what i want to look at first is how good is this algorithm how fast is it because one thing we noticed and i asked you in the slider question it could it could happen that you go m steps back in in the string in to read one character so if we had to do this n times for every character in the text go step go m steps back in the worst case it sounds like this is n times m which is as bad as the brute force algorithm but if you think about it this can't really happen because if you go back these m steps you're at the beginning of the automaton in state 0 and that doesn't have a failure link so in a way you need to first move along and moving along means you follow the match edge and that was cheap you never follow a failure link and then a match edge so for every failure link that you follow you need it to have a cheap operation first and more formally you can express this like this

11:48 Complexity proof

12:54 in each iteration we do one of two things that make progress we either move with i through the text and you can only move n times with i then you're at the end whenever we never make i smaller it only ever gets one bigger and if that not doesn't happen then we shift the pattern forward in this in this example picture the red part or in in other ways

13:21 we we move back in the automaton but that kind of moves us forward too just not in in in i but in the imaginary position of the gas and it's important for that that the failure link always goes strictly one step back at least so it's strictly less than j for for every state and so the first thing can only happen n times as i already said because we move through the text and the second thing can also happen just n times because we can't move the pattern position the guess more than n times so in the worst case both of these happen n times at most and so the total cost is 2 times n even though every individual step might cost m but as i said this only can happen if there were many cheap steps to compensate for it

14:23 Computing failure links

14:24 so what's missing is how to compute the failure links and that's also important because it's part of the running time for the entire algorithm if you remember the construction for the dfa which i realized was monday but maybe you still remember we had this state x that was kept which was simulating the partially built automaton on the pattern where you leave out the first character and then whenever we added the next match link we also updated where x would go and it turns out that x is exactly where the failure link should go uh go through the examples again if this doesn't appear doesn't appear so clear if you look look it up on an example it becomes really obvious and so a way to compute it is by simulating the construction that you've seen in the video and in code you do it like this you start with well fail 0 is just to initialize it's not a real failure link and initially we start with x in zero then we go through all the positions in the pattern and the first thing is we set the failure link for the state j which is the previous x the previous state that you got to if you chop off the first character and then we update

15:46 where acts should go next and if the if we're in state x and we can match the next character so pj is the character we want to add to the the prefix of the pattern and if that matches from x then we can take that link so we just increment x that means follow a match edge if that doesn't work then either we reach the beginning and so x should just stay where it is and this minus one is just compensated by the plus one over here so it becomes zero again for the next iteration and if we're not at the state zero then we follow one of the failure links that we've computed before so in in a sense this is again simulating the automaton on itself on the com on the prefix that we've already computed

16:52 and let's also analyze this this outer for loop can only run m times because j is never touched inside but we have this inner while loop which again follows failure links so in each individual iteration of the outer loop the inner loop could run m times that sounds like it could be m squared but the same trick as before applies

17:18 whenever x is incremented uh that's one iteration of the outer loop then that's why i wrote the code like with the minus one in here to make that in the analysis a bit easier or clearer we only increment x in this outer loop so it's only incremented m times in total whereas every iteration of the while loop where we continue it makes x smaller this makes it smaller because remember the failure link always goes strictly to the left and this also makes it smaller so we only have m iterations of the inner loop summed over all the iterations of the outer loop so it's again m plus m

17:58 it's no coincidence that we have essentially the same result in both cases this factor two you will see the tutorials that the two algorithms simulating the algorithm and computing the algorithm they're really kind of the same they are written in a slightly different form but if you if you show how they work on an example that's what you'll do in the tutorials

18:23 they're they're computing the same steps in a sense and with these two things together that's the knuthmore spread algorithm in its full glory we've even gone through the analysis to show that we never have more than two n plus m uh character comparisons in the whole in the whole process and that seems essentially best possible because at least in the worst case we have to read the entire text and the entire pattern to find if the text contains the pattern if there was some algorithm that somehow avoids this you could sneakily modify the input and smuggle in an occurrence that the algorithm then wouldn't find and so that can't be possible so for for worst case kmp is as best possible at least up to this constant factor of two

19:19 and also the space is decent because we now have only a dependency on the pattern and there's no factor sigma anymore no influence of the alphabet size so it's asymptotically optimal in terms of the total time and reasonably efficient in terms of the space so that's um on that side the end of the story

19:48 KMP performance review

19:54 let's briefly see how much you kept and how much you digested from this while i was talking so it's a long question i'll leave you some time it's basically about what is what is good about the algorithm

22:08 ah okay pen works again that's good all right i think you had plenty time for this one now sorry for me messing around let me lock this so we have votes for for many of the options

22:31 um we can briefly discuss i think it's mostly these that are correct okay that doesn't fit on the screen anyways so so we compare kmp to the previous one matching with the string matching automaton uh the pre-processing is faster because you don't have the dependency on sigma this might not be in all cases faster but it usually is if sigma is not really small and it also uses less space for the same reason uh the matching is usually faster actually with the automaton because you just have one table look up uh so that's that's usually the fastest you can get actually um same character comparisons um likely the other ones faster if the text is long for the same reason we have this factor of two in k and p which is not nothing but yeah i stress this quite often enough and so we like we like to have something that doesn't depend on the alphabet size

23:55 Prefix functions

23:55 goodie one last thing on kmp this failure functions the failure links that we computed for the kmp algorithm they turn out to be quite versatile and useful in in other contexts uh and so people have reinvented this a few times with different notation so there's there's a thing called the kmp prefix function which is essentially our our fail but

24:29 shift shifts the index by one and there's an alternative definition for or fail or for f and i think that's that's something you is worth memorizing is worth for you to keep in mind and there's a picture that goes along it if this is our pattern

24:56 then we look up to a certain point j so maybe i should put j slightly to the left because it's uh to the right because it's excluded so the jth character is excluded we look at the character prefix of the pattern of length j and then fail j is the length of the longest prefix of this that i can align with my

25:48 so it's it's the longest prefix we want the shortest shift here or the longest overlap so this should be the maximal length overlap well this is again the pattern just shift it a bit

26:18 shift it a bit at least one position and all these these positions here in between they match so they are the same okay so you take a string you ignore a part at the end you'd only look at a prefix and you ask how much can i take this prefix and shift it forward and it still matches you want to to have the maximal overlap and then fail j is the length of this overlap well no not quite its length of the brief well that's the same yeah it's the length of this prefix the length of the green part that's our fail j

26:58 alright this will come haunt us again in the next next unit