Video 5-3: The Knuth-Morris-Pratt algorithm

0:03 Okay, time for the for the final piece in this algorithm. We're almost at the final solution that Kenuth Morris and Pratt came up with. Uh the string matching automaton that we've seen can already be constructed efficiently. The only part that was suboptimal was this dependence on the size of the alphabet. And if you carefully remember or watch how we constructed the automaton, it was already suggesting an improvement. Namely, I was in the simulation updating this state X where then you have to take all the edges from. Why not just keep that state instead of copying all the edges? That's the that's the third insight that they had. uh if you want you can say this is uh the way I presented it as following from automa theory is exactly what led us into this slightly suboptimal way because this is the best you can do if you insist on having a classical deterministic finite automaton but if you don't then you can slightly modify the type of automaton and the type of computation on these automatter that you do and then the dependence on on sigma can be avoided.

1:25 Um in the automata world what we use is now a special type of arc called a failure link which uh the rules are you're only allowed or you're forced to take the failure link if you cannot follow the edges with characters. In all the automa here there will only be a single edge with a character on it. So if you're sitting here and you don't see a C, you have to follow this failure link, but you do not consume the next character of the text. The failure links are just updating the state of the automaton. You're still looking at the same character in the text. And then you try again. Maybe it wasn't a C here, so you had to go there. But maybe it's a B that you can read from here. Now, it could also happen that it's an A. So you can neither follow the C nor the B. Then you have to follow another failure link and another until you can finally read this.

2:26 Because these failure links don't consume characters, it might mean that we have to follow several of them before we make progress in the text. Now note that the computations are still unambiguous. It's still always a single thing that you can do. either follow an edge or follow a failure link. So it's still a deterministic computation. Uh but still if you want it doesn't map to any of the standard automata classes. But I would say that's the fault of the definitions from automa theory. Not the fault of this automa. It's a is a fine computation device. Uh in particular deterministic.

3:08 What's also obvious here is every state needs just two edges. a match edge and a failure link. No dependence on sigma. Uh here's an example of how you can use this automaton to match in the text. I don't want to give this uh example in full detail. It works as I sketched. Uh there's always just one thing that you can do. It might sometimes mean that you go through several failure links before you can process a character. Well, that's just how it works.

3:43 Uh here's code for simulating the automaton. So what the example showed is written up in specific code. Um I'm not going to read through the code really. Uh it keeps track of the state and the position in the text and the rest is fairly straightforward given if if you understand the automaton you could reproduce this code. The code is here for the analysis because now um as shown in this example, it can potentially take you a long time before you process the next character in the text. And in the code, this also shows there's an outer loop that says um I'm going to go through the positions in the text, but I'm not always making progress. I this position in the text is incremented here and here. Uh but I might spend a lot of time always in this other case where I'm following failure links. So the danger seems to be that I might take more than linear time in this algorithm. If I'm often running into this second state where I don't make progress, I is not incremented.

4:56 But if you look closely there is something that changes namely Q. So in each iteration either I increases or Q decreases because the failure link is always strictly going to the to the left.

5:13 So you can do an amortized analysis of this loop uh where each individual character may see many failure links but summed over all the characters of the text you cannot see much on average. Intuitively, you could say before you have to follow failure links for a long time. You must have used match edges to get to the right, but you can only get to the right one step at a time, consuming one character in the text each. The failure links might jump further left, but the worst case is that they jump one position back each time. But you can't go more to the right than you went to the left. uh there's no no teleporting. So the total number of of jumps the total number of failure links you follow is at most the number of positions in the text. If you want more formally you can say um that in each iteration of this outer while loop we either make i bigger or i minus q bigger.

6:21 And so in each case we make progress and we cannot not do progress for um for one of the two. But then individually I can be made at most n times bigger than I'm at the end of the text and I minus q can also not be made more than n times bigger. So each of the cases can summed over all the iterations only happen at most n times. So after two n steps, two n iterations, the loop's done.

6:54 So even though it's at first at first sight maybe looks like it's slower, it isn't really only a factor two. What's left out here is the computation of the failure links. That was just a call to this uh function with a forward reference. Uh the algorithm here is very very similar to the computation of this uh deterministic automaton. Basically you you simulate again leaving off the first character you simulate where you would have gone to what state you would have gone with the prefix with one shorter. And now instead of copying the outgoing transitions of this state X, you insert a failure link to that state X. And that's all. Um maybe we can do a short example instead of diving through the code. That was the famous example from all the all the chapter.

7:55 So let's try from zero to one. We take edge A. Now state zero doesn't need a failure link because you're already on the floor, right? You have nothing to that you've read. So uh let's go to next state. Now I need a failure link for one.

8:14 So the failure link for one I'm starting with nothing. Uh so I have a that I've read. If I chop off the first character that's nothing. So that's staying in state zero. So my x I'm marking that again here is state zero. And the failure link for one goes back to zero. And that's not an X, that's a cross. I can't really draw this better, I think. Let's add another state. So, state three.

8:50 And here's an A. Now, I'm adding the failure link for state two. What do I have to do? Well, I could either say I'm simulating the automaton from the beginning with one character less, so with the B, or I could start where I left off and go one step further. Now, in this case, it's the same because we're just at the beginning. So, I'm walking one step from zero with a B. Uh, but that actually leaves me where I am, right?

9:37 So, here's another um another state. Now, uh did I update my state X correctly? No, I didn't. Um so, this we would have to do now for three. The prefix we've read is ABA. So we have to simulate the automaton for BA. B would stay here failure link. So this is always sigma without a I'm staying and then I'm reading A. So I would move with my failure state to one.

10:13 And so from three with a failure link I'm going to one. Okay. Let's do one last one so that we see the construction with the failure link.

10:28 The failure link for three with BA was this red thing. If I now move to four, I would have wanted the simulation for B A B. I already know where BA brought me. So, I'm leaving from the red one with a B. That brings me to state two.

10:50 And hence the failure link for four would have to go here. Okay, that way you can can construct these and that should match what the algorithm here does. Uh it keeps track of the state X always remembers this in this fail array. The failure links now are a single array and then you always make make one step.

11:19 very similar to the previous code. This looks like it might be slow because there's an outer loop that runs for m iterations and there's an inner loop that might also run for m iterations because you move again you follow failure links to the left by the very same argument. Um again this inner loop in total cannot run more than m times because before you can make x smaller you have to have made x larger previously and you only make it larger down here and only by one thing at a time. So over the course of all iterations of the outer loop you're making x at most m bigger and this always makes x strictly smaller. So you cannot make X in total more strictly smaller than M times when you never make it bigger than M times. Okay, that's why also the computation of the failure links is linear in the word you're doing this over the pattern in this case.

12:27 So in total we have for the can more spread a linear cost in both text and pattern length and no dependence on the alphabet whatsoever. Again for bionformatics context it's not super critical but it's useful. Cutting a factor two is always good. In the worst case, this is best possible uh because you have to read the text in the pattern to make sure that you've c caught all the occurrences. Uh now you could go further um in in this depending on the type of data. Sometimes you can do a little better if you're assuming that it's not the worst case. So for certain types of texts and patterns, you can hope to do better. In the worst case, KMP is already best possible.

13:22 For historic reasons, there's a a different notation that's widely used called the prefix function with slightly shifted indices. I think by and large for this module, this I'm I'm not sure if this occurs. It might occur in some of the textbooks that I cited on the website. So maybe uh just keep in mind that these failure links that we computed in KMP are intimately related to some other function called the prefix function or the pi function um which occur in some other texts that describe this in slightly different words but it's the same thing up to maybe a shift by minus one. So whenever you read about these in in other sources you might have to live with an off by one. This is uh there's just no um global consistency on even whether strings should start with zero or one uh as the index but also here whether you um include the length or the stopping index. Okay, just just be warned about that.