Video 4-4: §4.4 Constructing string matching DFAs

0:00 Non-deterministic automata

0:04 in the next section we'll look at how to construct these string matching autometer that work so well for finding the occurrences of a pattern in a text and again um for those who've had some automa Theory I've been uh tortured with a bit of that in some some previous lecture maybe you know about nfas if DFA stands for deterministic finite automaton then NFA might stand for non-deterministic finite automaton um and it does uh these are all kinds of automa that are not deterministic it's kind of a it doesn't really say what they are um it just means that they can leave some parts up to

0:53 ambiguity and um in a way the easy part to build this the string matching automaton was just writing down the pattern on edges to the right and leaving the automaton as it is if you additionally allow the automaton to stay in state zero for all letters you've actually built um a valid non-deterministic automaton for this for this language Sigma star P Sigma star it's kind of not so useful algorithmically but it will help in an indirect way um I just want to point out for those who haven't used these automaton the way the way they're um reading an input now means when I start in state zero even if I read an a I don't have to go to state one I can also decide ah this time I'd actually rather stay in state zero and then reaching the final State means there's some way to choose among these options that gets you there or another way to put the same is instead of being in a single state is kind of a a parallel or or all possibility Universe Quantum world you're always in all possible states where you could have been if you made the appropriate choice so if I'm initially in state zero deterministically and I read a letter a i Branch out into being in state one

2:25 following this Edge and in state zero simultaneously okay and from then on you always have to go where could you end up from all the states where you currently are there's no real Quantum involved in this it's all just um saying you're in a set of states and so you can um read the text we had before it's the same example if you want to go back um at home we're initially in state zero after reading a we're in States zero and one after reading another a if we're in state zero we go to state one okay we already had that and we can also stay in state zero if we're in state one and we read an a h the automaton doesn't tell us um where to go that means that branch that parallel universe just collapses it dies out because there's is a dead end okay so if you're in States 01 and you read an a you're afterwards still in States zero and one

3:34 if you're in that in these two states and read a b it's a little more interesting from state zero B means you can stay in state zero so you get that state zero but you could have also been in state one and then read a b that brings you to one to two so afterwards you're in States zero and two and then things get more wild if you read another a from here you can either be again in state zero or in state one if you were in zero or from two go to three so you can be in any of zero one or three uh and so on and so forth now you found An Occurrence whenever seven is one of the possible states where you're currently in that's the way to read this and that's actually not a terrible way to think about string matching it's just not such an efficient way and we already know a somewhat okay way the brute force method and in a way this one is essentially not much better H the point is that we have to maintain this set of states in the worst case it's the whole set and then every transition needs to go through all the states you could be in so you end up

4:41 with essentially a this n * m worst case uh very similar to the root force method okay so was this all um not useful ah another piece of theory for any non-deterministic finite automaton you can there's an algorithm to construct an equivalent deterministic fin out automaton now now we're getting closer that algorithm is called the power set construction and and it basically works by using instead of the states we have all possible sets of States as your States so every state is a set of States from the previous automaton and the transition essentially work like in our example okay um and then there's even an algorithm to find a smallest possible DFA so in a way again both of these problems are kind of solved but uh from practical point of view the concern is that the power set is an exponential blowup even if you can minimize the states away afterwards that's really not helpful we don't don't want to have an exponential blow up and this is where um where we get to um these uh these three names that will pop up later again um somewhat independently K Morris and Pratt uh came up with um a few related ideas that help to avoid this exponential blow up and the first of these ideas is that

4:54 Automata theory concepts

6:25 we don't have to go blackbox from NFA to DFA and then min miniz it we can build the automaton instead step by step uh and if if you if you remember our example from before uh this was the string matching automaton I've shown you for our example pattern how many states did it have well just m or M plus one uh because the states had this specific meaning let's hope that this is general and we always need just M plus one States and not 2 to the m or something something crazy like

7:08 that and they found uh they made the following observation um which I guess is okay sorry I'll go back to the um example one more time um maybe instead let me just copy this

7:42 then we have it bit more um nicely drawn so let's suppose we're trying to um to find the transition from state three when reading uh a letter A so we're trying to trying to Def trying to find this Edge but suppose we don't know where it goes yet now the idea of km in pra is um we add the next letter of the pattern one step at a time so we assume inductively we've already built this part of the automaton everything that involves the first three states is known to us now um uh have to draw more pictures remember what it meant to be in the state three it meant there's our text and then it meant that there were the first three characters of the pattern that we could read up until this point and no longer prefix of the pattern was possible to read up to this point and now that the next letter that comes that is an a which is not a b which would be the next character in the

8:11 Building string matchers

9:14 pattern and so we somehow have to shift the pattern a little bit and that is spelled out here but let me show it in the example first so [Music] um the actual letters that go here are a a and we know they match the

9:50 text so the text ends with these three letters a b a and then comes another a now uh we know the the automaton should not now go to the state that tells us what's the the longest prefix of the pattern we've seen if we read the A and if we just figure this out uh manually we could try to shift it by

10:19 one but we see that's a mismatch with what we've seen from the text that doesn't match at all if we shift it by two that's a bit better but it would still mismatch um with this a here I should probably draw it like this so the best we can do is is shift it all the way along so that only the a is aligned with the next letter that we're reading so the state we should we should go is State one and of course that's also what the automaton does but how can the algorithm find this out using this green automaton without all this case by case and thinking through well it can do it by pretending we're reading the text one more

11:17 time so we're reading what we know about the text a b a a except that we leave out the first why do we do that because we already know that's that's not matching so um we know the longest longest prefix that we can still find is definitely not four it's at most three so we just start reading with three so we take baa and look where the automaton A2 ends up after reading baa if we start in zero we read a b still in zero we read a one to an a to go to one and we read another a we're still in one so that's that's our

12:14 result so here's here spelled out in words again in general what this looks like the new transition should still be according to the same invariant the longest prefix that matches this and um that has to be a suffix of the pattern when I chop off the first character so note here is a starts at one here it starts at

12:39 zero and that's the the state of the automaton that I've previously built when I start reading the text with the first character dropped if you if you try to do it exactly like that it doesn't look like it's very efficient but it turns out we can avoid that but that's that's still a useful way um to build the automaton

13:07 um let's do one more example where we try to find Delta of five and B so when we're trying to find the transitions for State five we know that c brings us to State six that's the match Edge and for the other two transitions for example B we have to look at what we already have and the previous automaton we have is this part A up to including

13:49 four being in state five means we've seen the first five letters of the pattern and the first five letters of the pattern are a b and a b a and now we're reading a c sorry B and we drop the first

14:17 character so we look in the blue automaton where do we end up when we read ba a b a b start at zero b a b a b State four and that's for we're supposed to end

14:35 up okay so manually that's it's not a terrible way to build it for a small pattern if the pattern gets very very long and you do this exactly following the steps like this you will naturally follow lead to the algorithm that I'll show you next which does this a little faster because you keep doing the same things and to kind of give you a chance to see that in action let's do um the other transition for

15:07 a so again we read in the blue automaton but this time ba a ba a a all right we start in the beginning we read b a b a and then instead of a b we have an A which brings us back to State

15:28 one now you may have noticed that the paths for the green and the and the blue Parts they all start with reading ba ba there's no need to simulate the automaton each time from scratch instead I could have gone b a b a so I remember after reading ba ba I'm in state three and then I can go one Edge for B and another Edge for a right I'm always reading with the autometer on the same same prefix and then one letter at the end changes that's only the last state that is different all

16:09 Optimized table computation

16:11 right that's the second Insight of the three uh of the three names the people behind the names K Morris and PR the simulations of this smaller automaton only differ in the last step so why don't we remember where we've been and uh you can push this one bit further with this algorithm by noticing if you go from one automaton building okay back to my example last time if you go from now constructing the transitions from State five to constructing those for State six this blue automaton gets a little bigger I add one more state but I can also track that the prefix I read of the pattern also just gets one longer so when I was in state three before reading the last symbol because I read ba ba in this blue automaton once I go to the one bigger one I add the b a b a c so I go from state three to state zero and that's the state where I start reading from so it should say from State six whenever I read something that's not an a that's the same as reading that from state zero and that's indeed true because B and C stay in state zero from State Six B and C go to state

17:46 zero that means constructing the automaton here in the code AS Computing this transition function in an array uh is very very short and simple I'll show you on on the example uh first of all we initialize um the First Column to all

18:11 zeros but then we overwrite the match Edge so um state zero and the first character of the pattern a should instead go to state one that corresponds to the one matching Edge that goes to the right now I maintain also this state X where I was when I read the one pattern the pattern without the first character and initially I'm in state

18:42 zero now I go through all the all the columns of the table and the first step is I copy the column from col from column x to the next column where I'm filling things in now so my my J is one I'm looking at this column First Step just copy the previous column because that's where X is but we overwrite the match Edge that's the only change we do so we're in this in this case the match Edge should be for B so here we put a two to go to the next stage the next uh State instead of staying where we are and the last bit is update X and uh that means we're in the column of X and we read the next character of the pattern which is B so we're in this we read a b we stay in zero so zero is still correct let me go do it one more time we copy the column zero because that's where X is 1 0 0 and we update the match Edge we should go from with an a to three that's that last bit update the uh

19:58 the edge here so we're in state zero and we read an a that brings us to State one so X has now become one next column we start by copying which is copying from column one then we overwrite for the match Edge which is a b where we should now go to four and we update X we're in state one we read a b that brings us to state two all right next one four we copy from column x 3 0 we update the match Edge uh which is an A so here we should go to Five the rest stays as it is and um we update X we're in state two and we read this in a so we go to state three all right and one more time we copy from state three 4 0 and we have a match Edge for C so here we go to state six let's see if I did it correctly yeah looks all right so if you want you can draw the picture from this right the same diagram as we had before um I didn't do it here well I did it because I was didn't do it because I was lazy to prepare it but I wanted to show the table because in this case I

21:33 think the table shows you much cleaner what happens than the messy Arc diagram and um that's basically all that's how you compute these uh string matching autometer the code is super simple maybe digging through why it does the correct thing is uh needs a bit of caffeine maybe a look in the red book um but once you code it up it's very fast and very simple in terms of what happens computationally that's the part I want to comment on briefly um let's analyze how good string matching with the DFA is I've already said before when we have the automaton reading through the text once it is just one table lookup for each text character that's essentially as fast as you can get I don't I can't I can hardly imagine speeding that up further building the automaton we still somehow have to fill the table so even though um visually it was copying a column and changing one entry copying a column is still copying a column and writing every cell um so we need Theta of M * Sigma time just because that's the size of the output the table is that Big M * Sigma so if you add that up the total time for string matching becomes uh M * Sigma + m and also the space for the

22:05 Complexity and performance

23:02 string matching automaton is the size of the table essentially and that's M * Sigma so that's very very good for the matching time if you build the pattern automon once and use it many times it's probably As Good As It Gets but the space overhead can be big um and in particular Sigma in our examples will always be small because my slides are a very finite but remember uh Unicode could be your character set uh h i look this up this time okay that's from October last year

23:45 it was just short of 150,000 characters as I said before all the useful emoji and all the scripts that Humanity has ever imagined uh so it could be big Sigma could be quite a big number