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

0:00 Introduction

0:03 in this subsection i want to introduce the knuthmois pratt algorithm based on the same ideas we've seen for constructing the dfa for string matching but trying to overcome the main weakness of the dfas namely their space overhead

0:20 Failurelinks

0:24 so this is what what uh what you've just seen dfas are fast but they need this transition table for all possible alphabet symbols and it seems a bit wasteful to store all these because we just in the construction we just copied a column in the table over to the next state there's a lot of redundancy in this table so maybe we can do away with this and that's the third ingenious insight from knuth morris and pratt we can do this last step

0:57 during the matching instead of pre-computing it for all the symbols if that doesn't make a lot of sense to you uh it will make much more sense in a second and the right way to think about this is again an automaton like this but a slightly different type of automaton so we use a new type of transition called the failure links so these are the things that have an of an x or this this cross on the top these guys here otherwise uh this automaton is very similar to the ones we've seen before it has the pattern on this chain to the accepting state and uh now what's different is that each state only has one other link other than the matching edge it only has one other edge and that's the failure link it's not a it's not exactly um a com an automaton in the sense of a formal language theory because if you transition if you take this failure link transition you don't consume a character from the text so if you're sitting in state 4 and you would like to read a c the next character in the text is a c you're not allowed to do this because there's only an a so you have to take this failure link but then in state

2:22 two you still try to read the same c so you would take another fader link and then you can read the c actually that's the that's the main distinction

2:36 um here's a more uh more detailed example how that works if you go through an entire text i think i'll i'll just show you the end result you do the same construction or the same simulation i just sketched uh whenever you cannot follow this match edge you have to take failure links and then try again with the same character uh that's that's the important message here and it can sometimes happen that you have to go through several states before you can actually process a character

3:15 if you are in state 3 and you try to read another a you cannot read the a here so you take the failure link you cannot read the a here so you take another failure link and then you can read the a so you go from state 3 to 1 and 0 and then eventually end up in state 1. that is the failure link automaton and it uh as you might already see now we only have to store one number for each state namely where does the failure link go yeah and we've lost this dependency on the size of the alphabet

3:50 Automata

3:54 so let's uh get you guys awake again um and see if uh if you're digested this part about failure automata already what is the worst possible time it could take to read a single character in the failure link automaton for a pattern how long can it take to process a single character in the text

4:52 i'd like to see a few more votes that's okay we're approaching 20 we did have up to 35 eventually so maybe i'll give you another second but i think people are on the right scent for this one

5:23 okay 25 cents like a good number i'll show you the results and the correct answer is theta of of m so that's uh that's this one um the the reason for that is you can basically have an automaton that looks like this uh you can if the pattern is all a's uh you would indeed get this

6:00 uh in this in this example um the failure links would always just go one go back one state and if if you have m copies of this and you're in this state and you read something that's not an a a mismatch you go one step back try again still not an a okay you try again try again try again so you could take a long list going back through all the states one hop at a time that sounds like a problem because we don't really want to spend beta m time for each character in the text that would bring us back to essentially the complexity of the brute force method it turns out that this is not a problem but the reason for that needs a closer look so let's first write down the actual algorithm for canoe with more spread this is this is the code and

6:30 Algorithm

6:59 the first thing it does is compute these failure links i'll show you on the next slide how that works um then it iterates with i through all the guesses um that's that's this one but it's not a simple for loop as it was in the brute force method instead it's a while loop and i can jump in in larger increments there are two cases essentially we can either find a match if the next character matches then we take the match transition in the automaton so we go from state q to state q plus one q is the current state in the automaton i didn't say that even though it's written here you start in the start state zero if you find a match you go to the next state um and here uh i is actually the position in the text that's um maybe i should have used i and j separately so here's i is not exactly the guess it's not the starting position of a potential match it's the the current position in the text that we read

8:07 if we end up in state m that's the accepting state then we can return the occurrence we found because i is the current position in the text we have to go back by the length of the pattern so this i mean this is uh equals or this could also be written as i minus m maybe more intuitive if we don't have a match so the next character is different from what we want to see we have to do something else we have to follow a failure link there's no failure links for the start state we just stay where we are but if we're not in the start state then we compute the failure link so the target of the failure link is stored in this array fail and then we just move our state there if we are in the initial state then we advance and go to the next character then there was just no way uh to find that character this maybe doesn't occur at all in this in the pattern string but that's fine then we just state in the initial state which says we haven't seen any part of the pattern

9:09 uh that's how this code works and let's see how we can analyze it uh maybe turn myself off entirely for this part um how long does it take to execute the entire code going through uh this this while loop um with the entire text uh one important observation is the fader links always point backwards right we never have um they always point in that direction that's that's one observation and now in each iteration of this of this while loop we do one of two things for sure we either advance in the text by one position that happens here or here or we shift our pattern forward

10:00 so the guess i minus j where we currently guess that the pattern starts moves by one step forward okay this is a little more subtle but whenever we update q this is this is essentially um this is essentially what happens by um

10:29 by going to a smaller state we implicitly shift the the pattern forward in the text by at least one position because of that now each of these cases can only happen at most n times because uh there's only n positions in the text so we can only advance the text end times and this also advances the text but with the pattern and the pattern can only advance in the text can also only advance in the text n times so the entire loop can only be executed at most two end times

11:15 by simply observing that each iteration in the loop makes progress either by moving to the next character in the text or by shifting the pattern along the text forward by at least one position so uh both the green and the blue can either only happen n times and we do one thing of these at least so the total loop iteration the total number of iterations of the while loop can be at most 2n and we do exactly one simple comparison in each iteration so that's why we have at most two n iterations and at most two n symbol comparisons that's the analysis of uh knuth moy spreads but we excluded computing the failure links and that is a second important part of the code so let's look how that works

11:50 Failure links

12:10 remember that the failure links point to this error state x in the construction from the dfa we will use the very same idea that we've seen for constructing the dfa but instead now of copying over the columns of this transition table we just store the state x that we are and that's that's the only change we need really so um we initialize x to the start state and the well the start state doesn't really happen in a failure link so this will never be used and then um we do something similar we iterate through the the pattern and we set the current state's fader link to whatever axis at the time and then we update x so there's two options either we can read the next if if we can read the next character and it's the same as in the pattern so we can extend the match then we move with x along the match edge and that means we just update x to x plus one if we don't have a match yet then we have to follow failure links but luckily these are the failure links that we already computed because they're further to the left uh so um if we've already reached the start state then we do nothing uh and uh

13:38 a quicky way to say this is we set x to minus one and then increment it again maybe a different flow in the code would have made this more intuitive if we're not in the state then we just follow one failure link and then try again so it's uh in a sense we're using the part of the automaton that we've already constructed to simulate what would be the next step for x and we always store what x was in in each of the positions

14:12 and again we we want to analyze how long this takes this loop takes m iterations that's easy but we have this inner while loop that could uh take our running time beyond m but indeed it doesn't um because this this inner while loop it always makes m smaller namely here remember again that fail is always smaller than its argument

14:44 so that's that's this part and we only increment x once per iteration of the outer while loop so x only ever gets bigger here so there's no way this this inner while loop can be executed more often than the outer while loop we can basically charge each iteration of this inner while loop to one iteration of the outer for loop and we only have m iterations for the outer loop so that means we can in total only have emulations of the outer loop and migrations of the inner group at most that's another 2m symbol comparisons for computing the failure links so that's 2m previously was 2n for the text in total it's 2 times n plus m that's what's written here that's the time the character comparisons are 2 times n plus m and this is optimal in the worst case there's no way you can do better the knuthmore spread algorithm basically gets the time that you need to just read the two pattern that the two texts the pattern and the text so that is the best possible that we can hope for and the space is essentially as big as the pattern but there's no dependency on the alphabet that's again almost as good as it can get

16:08 but we'll see some some further tricks later down in this in this unit so the total time is asymptotically optimal in the worst case and that's for any alphabet size that's really important and the the space overhead is is much better than for the dfa that's uh that's the knuthmois pratt algorithm

16:39 then i have um one question for you uh just reflecting a bit um and stressing that part again what are the advantages of kmp uh you should be able to answer with multiple answers so check all that apply

17:01 and yeah i'll leave you with that for a minute i'd like to see at least the 25 that we've had before 24 one more i see things moving but people just change the votes we have 25 so here are here are your answers and um the main points are let me show this on the other part

18:34 um kmp is faster in terms of the pre-processing because we don't have to factor sigma it uses less space that's something i've stressed a lot so almost all of you tick this one and it makes also the entire running time independent of sigma which is um an important fact if you use for some reason a very large alphabet like you have you allow the entire unicode alphabet the knowledge more spread algorithm is is very useful for match for string matching and it was the first worst case optimal algorithm for this problem but it turns out that the insights that led to it uh are much more uh general than just this algorithm and um indeed there's uh the this failure function that we used

18:55 Prefix function

19:30 fail of q which was the failure link target in the in the literature there's um a thing called the prefix function often denoted by capital f that's why i didn't use f for our failure function which is uh very slightly different um but it's almost the same as you can as you can see here essentially just a shift in the in the argument and this uh this failure function this prefix function sorry has found uses in many other problems uh in stringology whenever you try to answer problems that answer questions about strings that have to do with self-similarity and and overlaps and partial matches often there's a way to formulate it in terms of this prefix function so this has uh this has become uh useful and important way beyond the classic string matching problem so i want to briefly discuss this here as well just so that you're aware of the notation and can relate to this so again let me indicate this here to make the connection

21:07 the prefix function is defined as the length of the longest prefix of this pattern that is a suffix well the substring it's the same it's the same prefix of the pattern but with the first character omitted okay and that's also if you translate this to our fail function you get the following property about fail of j and this is really really useful and you should definitely memorize this and let me draw the picture that belongs to this

21:50 here we have our prefix up to excluding this the chaff character and now fail j is the length of the longest prefix so here's the same thing again same thing again but the bit shifted now again yeah i've drawn this many times i want that these two parts are equal so there's a self-similarity in this in this string there's a part at the end a suffix that is also a prefix okay so fail chase the length of the longest prefix of this thing this prefix the one that ends here so this blue part is then only

22:53 and this blue part is the longest prefix that is also a suffix of that occurs again here a suffix of this and at least one pattern is emitted so this one means that here is at least one character of a gap we shift this right by at least one position

23:18 and then um finally fail j is just the length of this thing and that is nothing but this j prime so it's this this length it's the length of the overlap okay um this is all i want to say about the prefix function um we will have a look a closer look at kmp and the prefix function or the failure failure link function in the tutorials to practice that a little bit i think memorizing this picture and this in this definition is helpful if you ever see the f and the prefix function used in some book or paper then be aware of this offset it's at the end down to the question do strings start with the zero or with the with the zeroth character with the first character to be consistent i chose that string start with a zero so that has certain implications and makes some definitions nicer here it means that there's a slight difference to how things are done in in many books

24:32 with that um let's close the chapter on kmp uh we'll continue tomorrow a little bit more on string matching we've seen that kmp is an optimal algorithm but it turns out you can beat it you can improve upon this optimal algorithm in an interesting way and uh well i'll tell you more about this then tomorrow and we'll also

24:58 conclude this unit then