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

0:02 in the next section we'll look at the K moris Pratt algorithm the same three names that popped up in the previous section by giving the key ideas to improve the construction of string matching autometer but the the final solution that they came up with um looks slightly different and uh it gets away without this Sigma factor in the space for the string matching

0:29 automaton so if you recall the string matching automaton as a DFA was essentially as fast as it could get for the matching part but it needs this transition table which tells you for each state and and symbol where to go and it just seems impossible to reduce that further because you need to specify where to go but uh the simulation in the construction of the automaton looked very very similar each time we always had this error State X and then we copied the entire column that's all already screams redundancy in your to to to you that you're copying these entire columns and then only change one entry and so uh the last Insight is um let's deviate slightly from this strict notion of a DFA and instead um do something that works better with this notion that we just keep um a previous state

1:31 and the solution for this if you want to keep keep drawing like the nice images like this um is a failure link so these these are not automat in a normal sense instead they have normal edges where you have to follow uh a character if you can read it but they also have these error links which if you cannot follow a normal match Edge you have to take the error the error link but you don't consume the character so if you're if you're in state five and you read something that's not a c say you read an a then you would go via this error Edge to state three and try again reading the same a and this case again you cannot really read the a so you have to do another Edge uh following the error Edge again and you still try to read the same a and it still doesn't work so you still have to go the error Edge one more one more step and in state zero you finally can read your character a that's different from our aom as we've seen them before uh but this has the benefit that every state needs just a single error Edge a failure

2:50 link now it's it's worth to point out the distinction to a non-deterministic fin out automaton because the the computation is still deterministic you have exactly one choice what to do uh but you're not always using a character if if you've seen automata before there's a notion of an Epsilon transition in nfas where you're allowed to take a transition without reading a character but these are different in this case you either have to take the matching Edge or you have to take the failure link there's never any ambiguity of what to

3:29 do and here's for our famous example from for um ababaca uh the failure link version and let's first see how we um use that to read through the text but let me let me do this quickly because it's um similar to what we've done uh we start in state zero we read an a as the next character oh we can do that perfect now we're done then we read a b in that state oh okay that also works so we go to state two from two we read an a a that's the next character in the text so we go to state three from state three a b brings us to State four 4 a takes us to five but now from five there's no way to read the B so instead we go back to three and for three we can read a b so here it brings us to State four and so on and so forth okay um here's that uh drawn nicely and it can happen that in a certain State you have to follow failure links a few times before you can um eventually read that character that's just how these automata

4:50 work okay wake up time after uh a long bit of of just listening it's not a trick question but it's a question that needs um little second thir all right um let's see some some spread of

6:41 answers and uh majority got it but it's a it's a big spread um now this is asking about the worst case what's the worst case time to read a single character if we're using such an automaton uh and the worst case as also often is realized if you have a very boring pattern say it's just a another one I I mean you have to take my word for this but you will find that the failure links always just go back one step in this case and so if you're if you're sitting in this state say and you read a b then you'll have to bump down essentially M steps before you can read your read your B the start state will always have um all characters apart from the one that leads there will Loop in state zero that's why in the worst case it takes takes so much time now apart from just waking you up that's also pointing out a potential problem right we loved our string matching automa because they gave uh constant time per character in the text as the matching time and now it seems like we messed this up now it could take um essentially M time for each character in the text so that sounds like we're back to n *

8:12 m now fortunately that's not true and the reason in this example maybe um you can see why it can't be true you can't always have to fall back all the way down the automaton uh to be able to to have this long path of an expensive character to read you have to somehow make your way to the right first and so whenever you have these long chains of uh expensive reads that don't make progress you had many cheap ones before and we'll we'll come back to that in a second I didn't show you full code for the string matching autom partly because nobody really uses those um there's only Fringe use cases whereas KMP is a is an algorithm that's um uh a bit more bit more widely used um in practice sometimes boil more beat it so uh that's the second one we'll come to but I'm jumping ahead of myself for for KMP I wanted to give you full code and so here it is there's a first part that we haven't talked about yet that'll be the next slide we have to compute the failure links similar to how we computed the automaton before um and the rest of the code explains the matching step and I'll run through it very quickly because it's

9:34 what we've seen in the example we maintain a position in the text and the current state in this automaton the KMP automaton with failure links we go through all positions in the text one by one um let me check if we can take the match Edge if so we advance to the next state so we make q1 bigger and we go to the next symbol in the text if that by we reach the end of the pattern we found our match and we can return that and remember we only find out once we've read the entire pattern so we have to subtract the length of the pattern again to get the starting position string matching was supposed to return the index of the first character of the match uh somewhat arbitrarily otherwise so if we can't take the match Edge we have to follow failure links until we can and so um unless we already in state zero we update our state to the failure link jumping back to the

10:40 left and uh so we do this and then we go back to the while loop so we we just start uh trying in the in the new state again

10:49 okay in terms of space we only uh looked like we don't we don't really represent the automaton anymore at all uh I could draw this pict picture but there's only two types of edges those that are match edges and I can compute those from the pattern on the fly or the failure links and that's a single number for each state that's just one array that's why we just have

11:19 this uh let's quickly analyze this because the question pointed out some of the characters in the text might need M time to read them potentially dangerous but it's not a problem

11:59 happen so um we'll bound the overall number of iterations of this y Loop because inside if you look at what happens there's a few if then else and so on but there's no further Loops so the whole inner loop part from here to here I want it that in Black that's all just constant time we're not doing anything con uh more costly in there

12:33 so the the only thing that counts is how often do we have this outer repetition of the loop and so there's there's these two options we can either make progress in the text which means I goes gets closer to n which eventually means we're we're running out of characters in the text and that happens here and here or we shift the pattern forward and that's a little more subtle it doesn't necessarily move I right it could could keep I where it is um but we still um shift the pattern forward whenever we update Q so we have either steps that increase I or steps that increase I minus

13:38 and in this case we use that fail is always strictly less than its argument so when we're in this case we make Q strictly smaller and that makes I minus Q strictly

13:58 bigger so in total we can have at most n of these steps where I gets bigger I never gets smaller and it starts at zero and it is at most n so we can have at most n steps like this and similarly this term I minus Q uh it starts at zero it goes up to essentially at most n and it's incremented by um at least one whenever we have the green part so we can have at most n steps of this as well so in total we're doing at most two n symbol comparisons where the the comparison that we pay for is always at this step okay that's that's the trick in this case you can't analyze the loop in isolation but there's there's these two different paths it can take and both of these each can only happen n times so in in total there can only be two n of them into at

15:05 most what's missing is Computing the failure links and uh well that will do something very very analogous to the DFA construction and indeed it turns out we've already done everything back then that we needed it's just that instead of copying columns we just remember that state X that failure state that we went to where we took the column and copied it that's exactly uh the state uh the target of the failure link so here's the code for that spelled out um we start initially with setting the failure link to zero failure state is also zero um and we don't have to do the match Edge so we skip that part we just set um the next entry to X and then we update X which means we now have to use the failure link

16:07 automaton um to update x to the next step so if x is currently three then we have to set it to where it was if we read a b and so while the the next character that we see is not the next C we have to read um we again follow a failure link and this this minus one is just because we update X increment X here anyways so that's a a boundary case for the zero it's the very same very same idea as we did for in more detail for the DFA

16:57 construction now again um we want this to be a efficient and uh now we have two nested Loops we have an outer loop that runs M times and we have an inner loop that could potentially run M times so it could be if you just look at this maybe it could be quadratic in M but it turns out it's not actually like that with a very similar argument as

17:27 before the outer loop is at most M times uh but the inner loop always makes X at least one smaller remember bale of X is strictly less than x so X becomes one smaller here but it's only incremented once here so every iteration

17:43 of the inner loop makes X One smaller but it can't go below zero and it's only incremented by one for each iteration of the outer loop so that means the inner loop has at most m iterations in total because X start at zero it can never go beyond M and each of these iterations of the inner loop consumes one from X so you have aerations of the inner loop aerations of the outer loop um and two M simple comparisons again from from this part at

18:22 most if you if you find this looks very similar to the code before then wait for the tutorial where where you will explore the similarity between between those two between those two algorithms between this one for using the failure link automaton for string matching and this one for computing the failure links they're indeed uh intimately

18:49 related for the overall string matching we have to do both we first have to compute the failure links that takes two M character comparisons at most most and then we have to do the simulation of the automaton reading the text that's at most two end character comparisons so in total we have time dominated by n plus M Big O of n plus M time and that for the first time is um essentially the best possible time because if we were supposed to find all occurrences of the pattern in the text we at least have to be allowed to read the pattern and the text once and that already gives you that time so kmor PR the algorithm has optimal worst case complexity which also means the other complexities are are sandwiched between the the lower Bound in the worst case and this um and the space usage is at least reduced to what we need to store the pattern that's also um hard to imagine how you can do much

19:58 better uh let's have a look uh at how much you digested this either from now or from something before this is supposed to be more of a question to reflect on what we talked about and you're you have all the information you need for answer ining this I I'll give you a minute or two to think about

22:02 so we got to 90 does that mean I should reveal the answers now uh okay maybe we can get a 100 well I'll slowly start three two and we have 100 one

22:22 goody so there's some controversial answers and um Let me let me discuss a bit um what I had in mind here here some of some parts of this question may be a bit vague so don't get don't get too uh too frustrated if if what you voted doesn't match my uh I'm Maring here uh the first part faster pre-processing on the pattern I think that's a pretty clear one because the DFA had this Factor Sigma unless Sigma is really small uh the pre-processing on the pattern goes down from M times Sigma to essentially Big O of M uh and that will almost always be faster uh even if Sigma is not not enormous um the matching part once I've built the automaton or the uh uh the virtual realization of the automaton in the KMP algorithm the matching itself is probably FAS with the DFA uh maybe something one can discuss but uh by and large it's faster because it doesn't have this Factor too uh KMP had overall order n plus M time complexity and this 2 m as an upper bound of the simpol comparisons but the string matching automaton is basically a factor one it uses table lookup not comparisons but it it will be similar in in time so actually the string matching

23:56 automaton wins on this part but it's uh it's bought with much more space so KMP uses less space because we're losing the factory Sigma that was the whole point that um I mentioned at the beginning and that also means it makes the running time independent of Sigma which is maybe somewhat surprising right it doesn't matter how many different characters there are in the pattern or the text uh maybe that sounds uh dubious at first but remember all we're doing is symbol comparisons so as long as it takes constant time to take two characters and tell you are they equal or not uh it's actually no contradiction here I skipped this one um fewer character comparisons uh that's a bit of a cheat because the string matching automaton doesn't really use character comparisons uh yeah uh you could also say um accesses to the character character the string matching automaton probably still wins at least for the matching part because it accesses each text character at most once um the KMP algorithm might um might

25:11 have to access the same character several times at most two on average but is a factor two again right and okay whatever depends on your liking uh one one last part that belongs into the KMP section is um a remark that this prefix

25:38 function the the failure links this uh fail array where is it here is actually much more versatile than just doing what we've done string matching with it in a sense it seems to capture some self-similarity in the pattern that has found it was found to be useful in many other contexts and that also means that people gave it slightly different names and slightly different conventions before it was uh formalized in in this version and so if you read about this in other books it can be a bit confusing because they use slightly different uh notation so the the typical thing you find is the KMP prefix function or can's prefix function function with slightly different names for that often denoted as f um and you can remember that f is essentially the same as fail it's just a shift by one in the index uh so the definition that people would would give for the prefix function is f of J is the length of the longest prefix of the prefix of the pattern ending at index J that that is also a suffix of that thing if you chop off the first character so again in pictures here's our entire

27:12 pattern here's position zero up to J so F of J is the length of the longest prefix so we have some shifted version of this that's P again shifted the length of the longest prefix that matches

27:35 here and I guess mismatches after and there's no shorter J right and that's very similar to how we defined the string matching transitions so there's no is no surprise that this is the same as fail apart from renaming things so the difference for us fail of J would have been excluding that position J otherwise it's the same so that also means um it it's useful to memorize memorize this alternative definition of the failure links fail of J is the length of the longest prefix of the first J characters of the pattern that is also a suffix of that thing if we chop off the first character and again the the prefix suffix thing is just uh uh a convoluted way to say what the picture says this whole thing is a prefix of the pattern uh now we take another prefix of the pattern it should be a suffix of that prefix uh untangling the words in pictures usually makes it easier but it's probably good to memorize this and untangle it when you need it on the spot so this this will crop up in in other uh efficient string algorithms um often under the name of prefix function so I wanted you to know about it