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

0:00 Intro

0:04 in the next subset subsection I want to show you the full knuth Mori spread algorithm the essence of which you have seen previously the the way to construct this string matching automaton is most of what knuth Mori spread is there's just this this little blemish that you had to store the transition function the edges for this automaton for every possible input character even if most of those never occurred in your pattern and so the canoe with more spread algorithm is a modification of that that avoids this this overhead in space

0:40 Failure Links

0:44 and the idea for that is to modify the type of automata we look at we Define a new type of transition which doesn't have an exact correspondence in the automata in the automaton world but it's very convenient in at least in this case so um the third inside of those three I don't think it was one inside per person I think I said it was basically invented independently by two groups of them anyways that's the historical the historical bit uh remember how we constructed the automaton we always kept track of this state X where we would be if you know the first character wasn't there and where we started looking if we have a mismatch why would we not delay this simulation of this last step until we actually need it so in a way already before we just had the current state and then the state X and that was essentially all the information but it's not it's not uh at First Clear how you can do this

1:58 the right notion for this is a failure link that's a new type of of Link in the automaton so it's an edge but instead of uh a character it has this cross mark as an as a as a label which says no character matched and the way these work is if you're in a state and you see a new character for which you have an edge you have to take that edge if you don't have an edge for that character you follow the failure link but you keep the same characters so you don't declare the C done then as normally an automaton would you keep the same character of the text and try again and that could mean it still doesn't work because you only have an edge for B so you have to take another failure link and maybe another failure link and only at this point you can consume the C because this this Loop Edge allows the C okay so in a way the computations are like if in a DFA you always know exactly what to do because it's either there is an edge for your character then you have to take it well there's no such Edge then you have to take the failure link no no random guessing no no schroding us

3:17 whatever you're not in several States um but at the same time it's also not quite like a DFA it's a little different is our running example this time with failure links instead of the the tons of edges for all characters I think you can already visually see that you need fewer edges and here the alphabet was just three characters um let me run through the example briefly uh you start in state zero

3:28 Failure link automaton - Example

3:54 now I read an a sorry I should have said I started in state 0 over to the left now I read an A and after that I'm in state 1. I read B I'm in state two I read an a I'm in state three so far so good and another B that brings me to State four and an A and I'm in happy in state five but now uh I read a b instead of the C so I can't take the next Edge so instead I have to go back to three the important bit is I'm not consuming the bead yet I'm only consuming the B when I appear can finally take the transition that has a b that's the important distinction I'm in state four region a brings me to State five I'm in state five I cannot read an a the next character so what I have to do is follow a failure link brings me to state three now in state three I can still not read an A so I have to go another failure link back to one and uh still no luck so I have to go back to zero and then I can read an a that brings me back to State One sometimes these uh can Cascade a bit

5:06 wrong State One I can read a b and go to state two I can read an a go to state three to B go to state four but we haven't passed through State seven so no match in this case it's a different text uh here's the same thing in nice

5:34 and that's that's the part I showed uh here's the the pattern how it is aligned with the text I think this needs careful reading what's the worst case time to process one character in such an automata and as I've just shown you

6:52 had at least 50 before with the other questions I'll leave you a little bit of space a little bit of time three more two more one more ah there we go okay so we have a clear winner in terms of popular vote and a few other answers but uh that's the right one uh so why is that the case so first of all why is it not constant it would have been nice like in DFA to have constant time for each character in a way that's true but only in an amortized way remember that haunts us again from the resizing arrays we'll come to that next week uh I want to show that this can actually happen the way that it's uh why can it not be worse than m well uh processing a character stops as soon as you take an edge that consumes that character so you can only have more effort if you have to follow failure links because that's the only the only two things that this automaton can do one stops the processing and the other keeps going so we have to have more keep goings for this to be more expensive but a failure link always brings us further to the right in to the left in the picture

7:31 Clicker Question

8:35 uh they always lead to a state with a smaller index because they correspond to Shifting the pattern further so you cannot have more than M value links but you you could have M if you have a degenerate pattern like this with all A's

8:58 so here uh if if you work out the failure links they always just go one hop back intuitively because uh every position could be a match uh there's nothing in in the pattern it's so self-symmetric self-similar it doesn't block any of the occurrences okay so that sounds bad but uh we'll see that this is not such a big problem

9:36 I want to briefly show the the code for the algorithm and then the analysis will probably have to wait till next week the knuth Mars proud algorithm is pretty much just explained uh just translated the idea I explained on the automaton to code to convince you that it's uh it's easy to write this down in in a way that's also efficient on computers to execute and to make it make it a bit more concrete and precise

10:09 there's one function that will get to next week which is Computing these failure links one obvious thing about the about the automaton that I haven't stated it doesn't need a transition function for every state and every character it just needs one failure link for each state we don't even need these other things because it's implicit in the pattern I know what the label of each of these edges is it's just the corresponding character of the pattern so all I need to store about this automaton is the failure links

10:47 The Knuth-Morris-Pratt Algorithm

10:50 so there's a function to compute those Let's ignore it for now and then we have an array of the failure links which is just the target of these Target of these arrows for a state q fail Q is the target of the failure link then we start with position zero in the text that's our first guess and we start with State 0 in the automaton that's our starting state as long as we haven't read the entire text we check if we can follow the match Edge which is is the current position in the text matching the next in the pattern if that's the case we follow the match Edge which means we move I one step further so we go to the next position in the text and we also increment the state in the automaton that's the easy case if we reach that way the accepting State we can return the occurrence that we found and again I is the position in the text that we compare so you have to go back queue steps to get the the return value is supposed to be the starting position of the pattern in the text so hence the I minus Q now the interesting thing is the failure link if the next character does not

12:08 match so in this case these two two options if you're in a normal State not the state zero then you have to follow a failure link so we check we take one failure link and then check again and this checking again is just doing the the while loop iteration one more time right so if we couldn't match a character we do one failure link and then we go back and try again and this automatically does the right thing if we're in state 0 then there is no legal failure link so for State 0 we just always go to the next position in the correct the next character in the text in in the pictures I wrote this like like this uh so whenever you have a character that's not the match one you just consume it at this point because you have to eventually get rid of those that don't occur so it's it's clear that there's um a special case needed for this state zero [Music] um and that's it not too not too convoluted code I think