Video 4-6: §4.5 The Knuth-Morris-Pratt algorithm - analyssis

0:00 The Knuth-Morris-Pratt Algorithm

0:04 so we left off last time in the knuth more spread algorithm with the analysis here's the code which has a an outer loop that goes through n and but also has this Loop following failure links so it's not immediately clear why that is in total a linear time algorithm n plus m and the analysis is basically an amortization argument uh maybe before I before I explain that step the intuition is that a failure link takes you a step back to the left and you will have to go one step at a time to the right before you can do that so whenever you take a failure link you have some somehow paid for that earlier by moving to the right

0:55 a formal argument is a little nicer if you formulate it in terms of the variables in the program our first observation is that the failure link always takes you strictly to the left a strict fail of J is strictly less than J apart from the start state which I guess technically doesn't have a failure link and then um in each iteration of this outer loop one of two things happens either you advance the position in the text if you're in this branch or you follow a failure link which intuitively shifts the pattern forwards so we reduce this this I minus Q we increase that we shift the pattern along the text even though we're still looking at the same position in the text and so each of these two things can happen at most end times if I'm Shifting the position in the text end times then I'm done with the text nothing left and if I shift the pattern by one position to the right I can also just do that n times because then the patterns shifted behind the text and so in in total this can do at most two times n comparison character comparisons between text and and pattern so even though the the loop looks like it might be n times M it never is

2:13 not if you sum over all the iterations now what's left is uh this magic function Computing the failure links um we somehow have to do that as well and we would like to do that efficiently otherwise the whole thing is a bit pointless you spend tons of time in the pre-processing

2:18 Computing failure links

2:38 the idea is to follow the construction that uh where I've shown you the the terrible audio video last time the construction of the string matching automaton we keep track of this this failure State X that's what we'll also do in in this algorithm and it's actually the same just simpler instead of going from X with all the possible characters to wherever that uh transition leads us we just store this as our failure link so in code this this looks like this we first initialize uh well this is kind of again I keep saying State 0 doesn't have a proper failure link it's convenient to initialize the fail array with zero just as a boundary condition so initially our failure state is also at zero and then we go through the pattern so remember we built the string matching automaton also by adding one more character at the end of the pattern one character at a time and we do the same thing here intuitively so we're looking at the next character we're making it one longer and we want to set the failure link of the next state and the claim is X always has the target of that next failure link and now we have to update where that where X should move to

4:00 now uh if the next character we read is also the position in the in the pattern where we are with this error state that means they both move a state forward then

4:23 we can just stop and increment X by one so suppose this while loop is never executed then we uh we immediately have a match Edge that we follow otherwise we might have to follow failure links and so we now do this on the part of the automaton we already have computed so we just follow the failure links this is this is very much where we had on the previous slide here looks very much like like this else branch so unless we're in state 0 where we want to stay so we set this to -1 and then add one again unless we're in state 0 we just follow the failure links and all of those are for a smaller index so we have computed them previously

5:16 so again we have a code that smells like it might be expensive because we have an outer loop that runs M times and we also have this inner loop where we could follow failure links and again it could be in the worst case we follow M failure links inside of this inner loop so it smells again like M times M somehow quadratic but the same same type of argument will show that it's not really M squared because again you can only follow failure links back if you previously one step at a time move forward

5:53 so the outer loop definitely has M iterations that's all that's prescribed by the for Loop and the while loop always makes X smaller each iteration in this degenerate case it makes it smaller by setting it so in the other case because fail always strictly goes to the left so while every iteration of the inner loop makes X1 smaller every iteration of the outer loop makes X exactly one bigger following a match Edge so we can't have more than M iterations of this Inner Loop in total because we always needed to have X move forward and we only do X forward steps uh we're going to do M forward steps with x in total so you can never move back more than m so we get this kind of same result 2m simple comparisons also for computing the failure links

6:52 Knuth-Morris-Pratt - Discussion

6:55 if you add this up then we have 2N plus 2m chronologically the other way around first 2m for the pre-processing then 2N for the matching part so um order of n plus M uh total total time cost by counting the character comparisons and of course that's that's not possible to beat in the worst case because you have to read the entire text and pattern that's uh it's kind of clear that you you can't find a pattern if you're not reading the pattern and you can't uh you can't find all patterns if you're not reading the entire text and you can't find all occurrences so in that sense the knuthm or spread algorithm has as optimal worst case performance or optimal worst case complexity I'm using complexity here in the sense of best possible feeder class so best possible order of growth if you want you can ask whether the 2N plus 2m if the factor 2 can be improved that's a different question but we're mostly interested here in the in the order of growth so it's it's optimal in the worst case but it's important to say worst case keep that in mind but a few other good things the space usage compared to what we previously had is much smaller so we need m space for the fail array

8:24 and that's it in particular it's independent of the alphabet size whereas the string matching automaton had this m times Sigma so it sounds like a great algorithm uh it has best possible overall running time at least in this asymptotic sense that's independent of the alphabet size which is convenient you can use it for Unicode and find patterns with all emoji that you like and it still doesn't blow up the extra space

9:54 so we should get to roughly 50 at least for for the judging from the attendance code uh so try to get well you all love automata Theory which I I appreciate that all but all but two uh fair enough and um so the there were many votes for most answers I'll comment a bit on why I think the other two are are less true

10:55 Clicker Question

11:02 uh first of all faster pre-processing on the pattern why so well the string matching automaton had to pay this Factor Sigma we had to fill uh for so when I say matching with DFAS it's constructing the string matching automaton and then you need to fill this table M times Sigma so if Sigma at least um is not too small then you will be faster with KMP now uh less space for the very same reason and or that that fifth option is the same thing again now um how about faster matching in the text now it probably depends on what you what you how you formalize faster let me give you the answer for wall clock time usually unless the unless the alphabet is really obnoxiously big and I think the Unicode size a few a few hundred thousand is still okay as long as the the table fits in Cache uh the string matching automaton won't be beaten easily because it's really a single lookup and then you go to the next character KMP is not too far from that but it has this factor of two in comparisons at least like that's the best we could prove with our analysis but I think this is also close to what it what it behaves like uh so in a way

12:27 um it's a little bit slower in the matching phase but usually that's far outweighed by what you spend on pre-processing if the alphabet is not tiny and the same for the third in a way uh the string matching automaton doesn't really do character comparisons so it's kind of a trick question if you want it does zero but even if you count following an arc by the character it uses exactly n and KMP at least on some examples uses 2N

12:57 okay before we close this and leave KMP behind for the moment I want to point out something so that's it's both a nuisance but also just shows you how widely this is used the the same the same concept behind the failure links that we looked at they turn out to be much more versatile than just for the tasks that we used finding exact patterns uh and uh so people used something with a slightly different name the prefix function which really is the same thing it's just that there's a shift in index so um that's that's the relation I was looking for the failure link is at J what f is at J minus one otherwise it's really the same thing if you want it's a typical Street start counting at zero or at one problem so just this this has stuck in the literature so you may find the prefix function in in textbooks and and academic literature so that you you can relate this the definition originally why it's called prefix function F of J is the length of the length of the longest prefix of the pattern up to position J which is also a suffix of or is a strict suffix of this so not exactly the same but it's also a suffix

13:01 The KMP prefix function

14:30 of the the pattern when you chop off the first character which is very very close to what we had for the definition of these uh failure links or the yeah the failure links and the construction of the string matching automata so in our case the difference is that we use exclusive indices not inclusive right okay so just just keep that in mind and be warned if you see this elsewhere it might often be the same type of function but an off by one shift uh I can't spare you with that