Video 4-4: §4.3 Constructing string matching DFAs

0:00 Constructing the DFA

0:03 it we still need to construct this deterministic finite automaton if we have it we know how to find uh for any text whether the pattern occurs that part's fine but how do we find it and we can do a very simple thing we can just write the pattern on this chain of states and uh don't add any other edges this is not a valid dfa because we don't know where to go if we say are in state 4 and read a c but there's another type of automaton the non-deterministic finite automaton nfas that do allow this by having an implicit garbage state if you ever take it an edge that's not there you're essentially um well you should go back to zero in this case um so this is this is in a sense um the non-deterministic finite automaton for the right language and we could use this to do matching directly what you do for this is you are not in a single state but you're in a set of states so let's see how this works in an example again same same text as before and again uh here the automaton is constructed from the pattern but the construction is very simple you just write down the pattern like this initially you're just in state zero now

0:31 Introduction to NFAs

1:04 Simulating the NFA

1:27 after you read a you can either take this edge to one or you stay in zero so you're uh in a sense in a quantum sense maybe you're in both states zero and one you don't know which one it really is and both are possible you read another a that can take you from zero to one but you already are in state one or it can take you from one uh basically to nothing so that states dropped but you can still stay in state 0 and also add the 0 again so you get 0 and 1. now if you read a b things become a little more interesting well the the parallel world that was in state one the b takes us to t state two so we have state two in the new set we could also have been in state zero and then a b would have taken us back to state 0. so we can be in states 0 and 2 after reading the b here if we now read an a we get from state 2 to state 3 we get from state 0 to state 0 or to state 1 so now we have all of these as a possibility if we now read c then no matter where we

2:04 State set simulation

2:47 were the 3 cannot continue with a c so that parallel universe just collapses and is gone the same for the one whereas if we are in state 0 we would again stay there so we always have state 0 in this in this automaton okay if you continue simulating it like this always go from all possible states of the world to all possible successor states

3:19 then what you reach here is uh there's a state where i do have the state seven the accepting state as one possible way the world could have come and that means i accept so at this point again i have found my pattern it's the same occurrence as before so this is all fine in principle this would work but maintaining these sets of states and going through going through all possible states each time and finding what could be this new successor states that's as almost almost as expensive as doing the brute force algorithm so this is not quite helpful yet now again uh theoretical computer science comes to the rescue here in in that you can always take an nfa and transform it into a dfa there's an algorithm called the powerset construction and there's another algorithm called the the myhill nero dfa minimization you can apply these two and then you get the best possible dfa just starting with the nfa which as we've seen is very simple to get but here the objection from the from the programmer algorithms person is that the state space can blow up exponentially that's uh what's coming from this power set uh so this might not be very efficient

3:56 NFA to DFA conversion

4:46 Inductive construction

4:54 three very clever people found that you don't have to go this route you can instead because these are very specific automata these are not arbitrary dfas or nfas they're specifically from the string matching problem so you can actually construct them inductively you can start with an automaton for the pattern where you leave off the last character and now you try to add that in and see what happens

5:30 let me try to draw this this part here um you previously have this automaton a j minus one and now uh you add you add one more state name to the state j plus one

5:52 so that one's new and you add a new edge this one with pj that is the new match edge that's the the edge you take if you find the correct uh the correct symbol that continues your pattern but you also need to find these edges that go back so that first part that's the easy easy part maybe um color code this a bit and okay i want the entire edge to be green so um that's this part uh we also need the other part we also need these outgoing edges

6:35 um i don't know make it red because it's hard so these are the transitions if we read a character that does not match we have to go to some state here but we have to figure out which state that is that is a little less obvious um which state that that should be

7:01 okay um in automata speak this is called the transition function often denoted as delta so you go from state j to and read symbol c then this delta j of j and c tells you where to go what's the next state

7:19 Transition function logic

7:21 um how can we find this this delta jc for that let me draw a different picture right it's almost the same as my as my usual one so here's a prefix of our pattern

7:43 that's the pattern up to character j that's what we previously had and let's try to add one more character the c so this uh transition function um remember from before what the states mean i think this is uh useful to remember to point out again state q should mean that we've seen this prefix on the of the pattern and no longer thing okay that's that's the intuition

8:17 and that means we should now find this longest prefix that matches with the c attached to it so what we need is um this shifted so that in here we have so the the entire thing would again be p0j

8:43 but now we need that the parts here are equal and the length of that thing is uh our new state so i don't know maybe i can draw this inside here this

9:04 the length of this is um our new state q prime um [Music] so so again this is what we want we currently have seen a prefix of the pattern now we read one more character that doesn't match that means we have to shift our pattern to the right but we want to take as many of the matching characters as possible so we only want to shift as much so that we have the next the next part that is that is aligned and all these characters match so we want the length of the longest prefix of the current match that is the suffix of this thing so it's a suffix when i cut off the first character i don't want the same string again

10:00 and that's the state of the automaton after reading this um and that state is less than j because this length red cannot be as long as the current match it has to be strictly smaller there was a mismatch so we have to shift by at least one and that means it's part the we find the red thing again in our automaton that we already have okay because the state number is smaller we already know that this state is in the automaton and we never need to go beyond state j so in a sense we can we can run this old automaton and on the one shorter thing and from that we get the next uh the transitions for the new state

11:00 this sounds uh this might sound a bit abstract and complicated there's a concrete example um coming up next i just want to point out that um this seems to require simulating the smaller automaton m times sigma times whenever i add a new state i have to simulate it for all possible symbols and uh fortunately that's that's not the case um but maybe let's go back and do an example in in this automaton here

11:24 Constructing new edges

11:41 suppose we want to find the edge that goes from state 3 with an a so we currently have constructed only this part of the automaton without the 3 that's what we have up to two

12:16 now we're adding this new state and we're adding this edge that's the easy edge now we need these two edges um what happens if i read an a what happens if i read a c so let's look at what happens if i read an a i currently have in in state 3

12:38 we have this p 0 j and the new c what we read is a b a and then another a a b a is the part of is the prefix of the pattern that we found when we reach state 3 and now we read an a which is not the right character we can't move forward but we have to jump back

13:06 a and simulate the automaton on baa so we essentially ignore this a here so let's do that we start in the initial state b takes us back to zero a takes us to one simulate a again so we end in state one

13:35 and voila this is where from three the arc goes to that goes to state one this is exactly what happens here so to construct one new edge we can take what we currently read from the pattern plus the new symbol and we just take the first character off and simulate that in the automaton then you get the result of the the target of that edge that works fine just again this seems like it's very expensive

14:06 KMP DFA construction

14:08 okay so that's that's this comment it would work but it's not what we want because it's slow uh a second insight from the same three clever people shows you you can actually um do this last step um in one shot by simply doing a copy step and one updates and i found this is so nicely explained in these lecture videos of of robert cedric and kevin wayne that there's no way i'm gonna explain this in a nicer way so i'll just show you this video instead so here it goes

14:51 let's take a look at a demo that does the full construction for the kmp dfa uh so uh here goes again one state for every character plus an accept uh match transitions are easy we build those uh and uh we're gonna start at position zero and the mismatch transitions are easy so what i was saying is what you see here in this table is the targets of the arcs here if you're in state zero now you read an a that takes you to state one so that's why this entry in that row and in that column is a one you're currently in state zero you read an a that takes you to state one and the other two take you to state zero okay uh back back to centric

15:50 uh so now when we move over uh x is when we're at position one of the pattern x is where we would be if we uh started out without that character which would be the empty string so we start out with just filling in zeros

16:06 for state zero and we can do that without any further reasoning but now we've got x initialize so now what we need to do is uh fill in the mismatch transitions for state one uh so what are they they're uh what would happen if we found those characters uh uh in uh and we were in state x if we found an a we go to state 1. if we found a c we go to state 0. maybe you notice that's just taking the entries corresponding to the entries we need from x's column and putting it in j's column that's all it is and then we need to update x which is where it would be if we match to b so we'll stay in x will stay in state 0. so now let's look at state 2. so 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 and then don't forget we have to update x and x goes where the machine would go if we saw an a that

17:28 transitioned from two to three so we just move x to state 1. so now we have x in state 1 and we're doing position 3. and now you can see how really simple the algorithm is once it gets going so now the mismatched transitions are a and c and that's what we have to fill in for column three but those mismatched transitions were already computed that's where x would go if we if 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 three and again we update x uh and when we see a b uh x uh goes to state two

18:15 and again you can check what what is x supposed to be it's it's supposed to be 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 b a b b a b 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 then we update x that's if you see an a you go to state 3. now we're ready for state 5 we've got x all computed and we need to do a and b and we get those from x if it's an a it's a 1 and if it's a b it's a 4 it's just move them over and then when we do the c 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 uh x is where you'd be if you saw b a b a c that's the construction of the knuth morris pratt dfa

19:37 Algorithm efficiency

19:40 all right uh there we're back um i hope you could follow through this um what was what was done in this algorithm to compute this d of a was that uh instead of figuring out the end point for each of the different transitions you figured out uh that there is a single state x from which all these transitions have already been computed in a previous step because the same computation is done over and over so you could just copy that state's transitions and overwrite just one of the edges namely the one for the match transition and x had to be the state that you are in after reading the pattern with the first character excluded uh that's that's all there is to computing uh this string matching dfa

20:32 KMP performance review

20:34 how how well does this work um string matching with deterministic finite automata um the running time is very good for the matching part it's essentially just a lookup in this in this table that we've constructed as you've seen in the video so you do this table lookup given the state and the transition and update the state that's as fast as fast as you can go building the automaton it needs m times sigma time because um you do need uh to write that table you have to copy these columns initially it looked like we might get another factor of sigma but this is uh this is really the time that uh that we need and so the total time is um this n for uh the matching part and um m times sigma for constructing the automaton and we also need m times sigma space that is just the size of this transition table the good things about matching with string matching automata with dfas is the matching time is really hard to beat these table lookups are almost as easy as you can get and the total time is is optimal if the alphabet size is fairly small and by optimal i mean here it's theta of n plus m which would be the time for just reading

22:04 the pattern once and reading the text once you clearly have to read at least every character so you can answer this pattern matching question in in the worst case okay so that's good um what is what is not great yet is the substantial space overhead for this m time sigma um think of of something like unicode where uh sigma could easily be well in the billions i guess um how big is the unicode character set um i don't even have the up-to-date figures but um well the used character sets maybe is 100k characters um i'll look it up and put it in the notes what the actual current count is this is counting all the characters in all the languages that humanity ever used plus all the emoji plus a lot of extra stuff mathematical symbols and all these things so sigma can actually be very big even if m is small this space overhead can be a problem