Video 4-4: §4.4 Constructing string matching DFAs

0:03 in the next subsection I want to discuss how you can construct the string matching automaton and also do that efficiently not just uh any way of doing it for that um I want to come back to the second type of automaton that appeared in the slider question much earlier that's the nondeterministic finite autometer and these guys they look similar to the deterministic autom if you draw them as such a state diagram at first s they might might look the same the difference is that they're allowed to have ambiguities in what to do in a certain state in particular uh they are allowed to have no edges for uh for some letters which means if you end up in this state and you see a letter that you can canot process tough luck guys you're doomed but that means you must have had some other option earlier on that might have brought you somewhere else or your input is not in the language so the automaton should reject then every possible way of moving through the state diagram has to reject but the sneaky bit of the definition is it's enough if there is one way for you to find your way through this Maze of states that leads to an accepting

1:33 State uh so it it's at first sounds not very useful in an algorithm but let's ignore that fact uh for now the the nice thing about nfas is that they're very trivial to write down for these kind of regular Expressions we can stay in the state zero as long as we want at some point we commit to move forward and read the pattern and then we can continue reading arbit characters that's easy as easy as it gets right uh the automon just expresses what we said in this regular expression before arbitrary things the pattern more arbitrary things it's just not clear how you're supposed to know when to start your journey and so the the automaton says well that's not my problem if you want to accept your input you better find a way but it's easy to write down cool that's a non-deterministic automaton and non-deterministic because it doesn't always tell you what to do and you kind of have to magically explore all options I carefully avoid to say you have to explore all options in parallel because I think that's not quite true it's not it's not true to the nature of non-determinism to equal it with with parallelism it's not the same notion so uh try not I try not to say it that way

2:59 uh but you're supposed to try all options we can actually use this automaton for string matching uh you have to keep track of all possible histories but it turns out this is not that hard uh it's not as hard as it sounds because um what is a history in a finite automaton it forgets everything about the past but except for the point that the state where it currently is so no matter how many different convoluted ways they may have been that lead to a certain point is all irrelevant if you reach the same state all the rest of the past is ignored so the set of all possible trajectories through the state diagram is at at a single point in time as a snapshot is just the a set of States previously deterministic automaton you were always in exactly one state now you're a bit more of a Quantum guy if you want but again this is another analogy that's not not not perfect but uh you can hover in this indeterminate state of being in several States until someone looks too close at you you're undecided uh okay um again it's not Quantum it's not in the quantum sense there's no probabilities there's nothing like this coming up uh you can just stay uncommitted and stay in several

4:28 States uh you're happy to accept whenever the set of states that you're in at the same time contains an accepting State a final State I think this is much easier on an example than it sounds we start in always state zero so initially there's no ambiguity if we read an a well let's look what the automon says I could stay here because a is part of the alphabet or I could move to one so after reading the a I'm simultaneously in zero and one pick what you want I'm not sure yet okay if you read another a you're actually staying in the same set uh because from one if you took this transition to one one step ago you would now be doomed so that that trajectory just ends there and it's lost but of course if you had stayed in zero you can again go to to one or stay in zero so you're again in the states zero and one simultaneously if you read a b from here things get a little more interesting because from zero with a B you can only stay in zero and from one with a B you advance to two so you're now in state zero and two if you read an a from there things Branch out further if you're in two it

5:46 goes to three and that's the only thing uh the other option was you were in zero but then you had two things that can happen so you're now in in three states at the same time then sometimes things Sy up again if you read a c the three is lost so that dies out the one is lost that dies out the only thing that remains is the zero State and that can only Loop so after that you're back to only one thing is possible and you keep you keep doing like this so this is the same as before um we have seen these states already a new thing happens when we're in States 0 1 and three and read B in that case both one goes to two three goes to four so we advance to two four and we stay in state zero because uh in this case we always stay in state zero there's always this loop from here things get even Wilder so with reading an a you Branch out into four different things it's really advancing the four advancing the two and advancing the zero to a one and staying where you are you read a c from here we already know that the 0 one and three will die out

7:06 we've seen that before over here but the five can move on to the six that's how we made progress now we're in this state Zer or six and with reading another a we reach a configuration that contains at least the final State and so we can say yep found a pattern and I don't even have to trace back back uh which of these complicated histories that I'm all lumping together now lead led me to this point it's enough to know if I reached this final State there was one and um I know at which position the match ended so I can subtract the length of P to get the starting position all right so that's kind of cool it's it's looks like the automaton contains no information that's helpful about the pattern because it's it's literally just a pattern written on these funny lines no other thought or input but if you treat it as an automaton in this sense stay in all possible States and uh just um maintain the set of States you can actually use it for string matching uh it's not a terrible algorithm it's not the fastest either because you have to maintain this set of states and so uh I guess you can construct you can probably construct a Toma where

8:31 the set of states that you're in is is fairly large and you would always have to at least check where each of these goes so it's it's not quite clear if you can do this very efficiently but the conceptual step seems to work

8:51 fine now again uh theoretical computer science has all solved it for you uh there's a theorem and myner wrote If you have a non-deterministic pite automaton whatever the language is could be ours you can construct an equivalent deterministic one from that it's called the power set construction it's a standard Topic in undergrad classes an automater but if you haven't seen it doesn't matter too much uh the programmers who have seen it will rightly object that while this is cool it's an exponential blow up in the number of states uh as the term suggests you're basically creating a DFA using all the possible subsets of states and that sounds that sounds really expensive so he's already giving up um but luckily some some really smart people thought this through and discovered something so there's a an ingenious insight and that's what also the KMP stands for that you've seen before this first algorithm or admittedly second if you want want um string matching algorithm that we'll get to you don't you don't really have to apply this PO set construction because the types of autom we're using are a bit special uh to take this to the take that apart um let's uh let's see how we can go from a pattern where the last character is

10:26 missing and add one more character and see if we can build the automaton inductively so the idea is to start with essentially just the empty pattern that the automaton does nothing if you can do an inductive step where you can take the automaton for the first J characters pattern p 0 up to J remember excluding so it's j characters because we start at zero if we have an automaton for that maybe we can add the next character and build the DFA for the one bigger pattern there's an easy bit so um let me draw the part that we that we have now uh because this is is a bit index

11:17 Mayhem to show you again so the pattern here is seven characters long but the automaton has eight states we start at the zero and there's always this is pattern character Zero there's always the uh the indices match between the state and then the next outgoing right Arc has the pattern character of the same index as the state had so we have state

11:54 J and then there's a new Edge labeled with P of J that's the new character that we append and uh we know where this leads to it always goes to a new state j+ one so that's the easy

12:21 part let's make that green as well but we but we need when we're in the state J which previously was the accepting state right so okay let me go to the example again back here the pattern has length seven that means State seven is the accepting State and I don't need to worry what happens in that state because it always just had this Loop you found the pattern happily stay where you are if I add another character at the end this changes and I have to worry about what to do if I if I don't see uh the correct next

13:08 character so we now need somehow these these links that go back if I find a c that is not the same as the next character in the pattern uh in in language notation people write this as this transition function so Delta of J and c means you're in the state J and you read a character C that's just the target of these of these

13:39 arrows so how do we find out where to go with this and uh you can't just always point back to zero then you would Overlook cases you can um you can do examples where that happens you say the patterns is just bbbbb if you were to jump back to zero you would miss

14:00 occurrences the Insight from can Morris and Pratt is that we can use uh the construction of the of the automaton that we already have to help us out and let me spell out a bit to explain this what the transition function is supposed to do and that's remember this this boxs from before that we've used what is the meaning of a state so this new state if I go from State J and I read a character C that is not the the next matching one I'm supposed to find the longest prefix of this string the pattern the first J characters of the pattern and this new character C added I'm supposed to find the longest prefix of that which is also a suffix of that same string but with the first character removed so I'm trying to look for

15:04 I'm trying to look for how much can I shift the pattern to the right I want the smallest amount so that I still get match and so of course this will be a suffix of the same string um and stripping one character off is just to make sure that I'm not saying haha I keep the exact same string it's a suffix of itself so uh I'm not doing anything to avoid that uh degeneracy I'm taking one character

15:51 off now because that's uh definitely shorter there's no way if you just see that part um let let me reind this this still doesn't seem to help us much but we know we have an automaton for the one shorter pattern and uh it will have to react to any kind of string in some way but we know in what way because we know what the states mean so if we feed the automaton that we already have with this string where we omit the first character it will have to end up in some State J and that state uh sorry will have to end up in some State and that state will not be more than J if it were was more than J it would be J + one and that would mean that c is the next matching character but we're in the case where that's not the next matching character so what I'm saying here is if if you feed the automaton that we have so far with these characters it will not run into the new Edge it will stay in the part that you've already constructed and so we can use the automaton for the part of the pattern that we already have to find out this longest prefix because that's what the

17:09 states there mean it's a little convoluted um let me see if I can okay yeah we have to go all the way back but I I'll show it on the example that we used before suppose we have this part of the pattern and of the automaton so that would be A2 because we have two pattern characters already dealt with and now the task is say to find the transition from um this new state to uh when you read an a

18:04 uh sorry sorry that's the easy one that's that's this one the interesting one is um finding say with a c where we have to go to if we're in state two which previously was this accepting State and so what what this tells us

18:29 is round and C so in this case we have a b and then C so we strip off the first character to go to P1 J C that's just BC and now we simulate our green part of the tomaton on just this part and there's not too much interesting happening but it goes zero B C so it reaches state

19:15 zero and that's why the Edge from two with the c should go back to zero okay I know it's first time where things get a little hairy in the

19:36 details the the trick here really is you can use the automaton you already have so far because it it does the same thing you want and the part you've constructed must be big enough for the part for what you need so you can do this with all the mismatch characters and then you obtain the next larger

20:03 now this still sounds expensive if you wanted to execute it because you would have to run many times this smaller automaton each time going through all these characters and uh it turns out you don't even have to do that you can be even smarter here uh you can if if you do this on an example it's it's easy to see uh all these simulations of the smaller automaton they start with the same characters and just the last character is different because that's the new mismatched character so they all do the same kind of computation up to a point and there's one more thing where they differ so you might as well instead do all these simulations together and remember where you landed and then just do the last step for each mismatch character and uh even smarter you can maintain this state so you don't have to start simulating from scratch you keep that state and Advance it with you um I think this is this is so well animated in this video by uh from from the book that we used in in unit 2 as well there's no point in me recreating this so I'll just show you this snippet from the video I'm not sure how well the audio will work but uh let's try well

21:22 let's take a look at a demo that does the Full Construction for the KMP uh DFA uh so here goes again one state for every character plus an accept uh match transitions are easy we build those uh and uh we're going to start at position zero uh and the mismatch transitions are easy uh so now when we move over uh X is when we're in position one of the pattern X is where we would be if we started out without that character which would be the empty string uh so uh we start out with just filling in zeros uh for state zero and we can uh do that without any further reasoning but now we've got x initialized uh so now what we need to do is uh fill in uh the mismatch transitions uh for State one uh so what are they they're uh what would happen if we found those characters uh uh in and we were in state X if we found an a we go to state one if we found a c we go to state zero uh and maybe you notice that's just taking uh the entries corresponding to the entries we need uh from X's column and putting it in J's column that's all it is and then we need to uh update x uh which is

22:57 where it would B uh if we match to B uh so we'll stay in X will stay in state zero so now uh let's look at state two so uh we need to fill in what would happen if we got a B and what would happen if we got a C well it's what would happen if we were in state X and we got a b or a c so all we do is move those two zeros over to column two uh and then don't forget we have to update x and x go where the machine would go if we saw an a that transition from two to three so we just move X to State one uh so now we have X in state one and we're doing position three and now you can see how really simple the algorithm is once it gets going uh so uh now the mismatch transitions are A and C that's what we have to fill in for column 3 uh but those mismatch transitions were already computed uh that's where X would go uh if we that's where it would go if we happen to be in state one so we move the one and zero from column one over to column 3 and again we update x uh when

24:10 we see a b uh x uh goes to state two uh and again you can check what what is X supposed to be it's it's supposed to be uh where you would be if you started the machine on the pattern with the first letter cut off so it's it's supposed to be where would you wind up if you got bab B A and that's a check all right so now uh straightforward State four we have to fill in B and C we go to X's column and copy over B and C from X's column uh then we update x uh that's if you see an a you go to state three uh now we're ready for State five we've got X all computed uh and we need to do uh A and B and we get those from X if it's an a it's a one uh and if it's a b it's a four it's just move them over uh and then uh when we do the C uh and get the accept uh there's no mismatch uh that's the we do update X to get ready uh but uh when we get to State six uh we're done and again it's just as a double check X is where you'd be if you saw b a b b a

25:29 c that's the construction of the can Morris Pratt DFA the key part here is you can you can maintain the state X where you would have been if you read the car the pattern that you're that you're building the tomon for with the first character omitted and that automatically takes you to the position just before where you should go so this character this this position X State X is not what you put in the Delta function but from there you take one more transition and the result there is what goes into the transition function so Delta that was what um is shown in this table here right uh and if you wanted to code this really you see it's copying colums so it's uh it's really easy to do this on an example at least

26:22 manually the the tricky bit is um explaining why it's correct let's briefly discuss how well this works uh even without showing detailed detailed code for the construction um I hope that the video makes makes it clear enough how that code could look like the matching part for the running time is is as good it can POS as it can possibly go you're looking at each position in the text and you do a lookup for the DFA transitions that's one one table lookup uh the time for building the DF fa is a little less clear but uh you can essentially do it in the time needed to produce the table that's again if you follow from the video uh copying the column is proportional to the number of copied elements and updating the state X and producing the new matching Edge is also constant time each so the total time is is M times Sigma Sigma is the size of the alphabet right that's the the number of rows in the table that you have uh plus n for the matching part uh and the space is obviously what you need to store the transition function so it's the number of edges uh the matching time is really really good if the alphabet is not too big also

27:45 the overall time is as good as you can get because you need to read the text uh but the it is quite a substantial space overhead to have this Factor Sigma in there and um so for that I I looked this up in the break if you use all Unicode characters then uh Sigma with the latest release is

28:29 149,00 K now suddenly this is megabytes and megabytes of uh of table and most of the entries will be all zeros because if your pattern's just a th characters long most of the 150,000 emojis won't occur in it right it's a bit of a waste of space and time to fill all this thing with zeros just because potentially the text could have all these emojis but then you would still discover that the pattern doesn't have them that seems wasteful so in a way um if you can guarantee that the the the alphabet is small or you don't have to worry about space this is this is a fair good uh good algorithm but we're not completely happy yet in the general case