Video 4-4: §4.4 Constructing string matching DFAs

0:00 <Untitled Chapter 1>

0:04 in the next sub section we want to look at how to construct these automata that we've just used i've explained you briefly if you're given such an automaton how you can use it to search the text and i motivated slightly a bit why this automaton contains enough information for us to do this task

0:26 but it's not maybe not quite clear how to efficiently construct this automaton so let's let's have a look at this if you if you have this formal language background you might think uh why don't we use a simpler automaton the non-deterministic finite automaton instead of this deterministic one the reason is that the non-deterministic automaton is really easy to write down it is simply writing down the pattern like this as states and pretty much no other transitions how does a non-deterministic automaton work the the non-determinism part is now that you have the option to have two arcs with the same with the same character and in particular here you always have to decide do you follow this track now or do you stay with the current a in zero and the automaton doesn't help you it just says you figure out the way to decide where to go and it accepts the string if there is any way to get to the accepting state but if you took the wrong turn because you decided oh i'll stay and wait for another round or you went running down this track and got trapped that's your problem you have to try to find any possible sequence through the states

1:57 uh and another way to say this um is that at any point in time you have to think of being in a set of states as opposed to a single state

2:09 so let's see um how we can make sense of this uh because it's a nice precursor to what the the construction of the deterministic automaton does so in principle we could use this automaton so again this automaton is really easy to construct you just write the pattern down put states and and one arc and you add these these transitions here where you can stay with every character in the zero state it's trivial to construct and you can use it for string matching uh just there's a there's a catch but let's let's first see how in principle we can do it and the key inside is you can at any point in time remember to be in a set of states as opposed to a single state and whenever there's a way you reach the final states or whenever there's a final state in your current set of states you accept it's a little bit like quantum computing from the from the spirit but it's it's different in many ways so you shouldn't mix up quantum computing and non-determinism but it kind of has a similar flavor that there's parallel universes where you could have done different things but that's that's where the analogy stops a bit let's do it on an example again so same

3:25 example as before just to see how this works uh we initially start in only the start state zero so far so good now if an a comes i can go to state one but i could have also stayed so i just do both and after that i'm simultaneously in state zero one where i could be in any of those two states if i do another step a it doesn't really bring me further from one so this this branch that was in state one goes into the garbage state and dies out i've also been in state 0 in this point so taking another step a brings me again to state 1 and back to state 0 at the same time so after reading another a i'm still in this in this state set 0 1. if i now read a b things get slightly more interesting i can stay in state 0 but for the part for the parallel universe where i was in state 1 i now move on to state b state 2.

4:30 and from there on we get another branch so if i'm if i'm in 0 2 and i read an a from state 2 i can go to state 3. that's great from state 0 with an a i branch into 1 and 0. so i'm now in in 3 states 0 1 and 3.

4:50 if i read a c at this point these two die out from from 3 i cannot go anywhere so end of the line from 1 i die out go to the garbage state so the only thing that survives is state 0 which always survives because i can always stay there so after state after this transition with c i'm back to knowing nothing in a way

5:16 and then things repeat indeed so i have a and a again you will recognize the same as before then b is same as before a same as before but now the next character is different we're in the part of a match so now um if i read a b here i have to go through all three states and see what a b does to them from three i go to four from one i go to two and from zero i can only stay in zero so it brings me to the states zero two and four after reading the b if i read another a there i'm not branching out into four different universes uh all of these so four goes to five two goes to three and zero goes to one and zero so now in these four states if i read a c now five survives to this six the other two die out and zero remains but i'm still in states zero and six and reading one more a brings me from six to seven and uh that's all i need to know the other states are interesting to know of but as soon as you've reached the accepting state from any of these branches you accept the string okay

6:35 now it's a it's a nice exercise to compare this table to the one before but i'll leave that for you at home uh so again we can not only do this in this example but in principle whenever you have a non-deterministic automaton you can construct the deterministic from it and you can even minimize the dfa afterwards if you feel like it but the this problem two from before kind of remains uh the algorithm to compute a dfa from an nfa in general has a blow up where um if you haven't seen this think about this uh you you get a deterministic automaton by just taking the set of all the the states in the deterministic automaton are all subsets of states in the non-deterministic one and then you're doing exactly this simulation you go from one set of states to another set of states that's deterministic the problem is there's many sets of states so we're still not completely happy

7:46 but these three people in essentially uh two independent ways uh discovered that our string matching automaton is not a generic nfa and indeed if you apply this this construction here it doesn't actually lead to this exponential blow up or you can at least sneakily avoid it

8:09 and you can construct the dfa by adding one state at a time and avoid this blow up and so what you construct is first an automaton for the pattern up to the first j characters and then you add the jth character at the end and and see what that does to the automaton

8:37 so um this previous automaton i'm sorry for j minus one it will have states 0 1 up to j minus one you love this general shape and it will have various arcs going back

9:18 aj the automaton for the pattern with one more character at the end what we'll always have to add is the newt state j and and we also need the failure arcs so what happens if i am um so remember here in the previous automaton these were not really there instead they were loops on the accepting state

10:09 sorry i have to make the picture a little bigger this is always a mess with the indices so we have j minus one but we also have state j which is one after reading the the previous character products here so this one has a failure link somewhere back there but this one didn't now what i add to the new is state j plus one which is reached by the chafe character uh and i have to find out where do these go back so instead of staying there i now have to find where does this branch back to if i'm reading a character that's not the right one in the pattern okay so i need a new state this transition is easy but i also need the other transitions and these are the tough ones to figure out

11:15 and remember what it meant to be in a certain state it meant we've seen a certain prefix and that was the longest that we know that we could have seen up to this point

11:26 um so let's go through this uh so delta is the is the target of this arc delta jz means i'm i'm in state j i'm reading a character c and now i have to go i have to jump back so these are only for the arcs that don't bring us forward and that leads to [Music] a state delta jc that's the target of this of this arc

12:06 and we want to know where this is now remembering the invariance it is the state so it's the length of the longest prefix of this text of this thing that we can find uh so that it's always also a suffix of this so i think this is best shown in a little picture on the side

12:35 so we know that text currently looks like this we have p 0 up to j but excluding j and we read one more character c and it's not the right and that we would have expected here

12:55 and now we're trying to shift the pattern forward by as little as possible so that i here have the same but with the first character emitted and again the character c at the end and i want to shift this forward so that these characters all match okay that's that's the goal

13:27 now the inside here is so the inside really is into this in this equality how much do i shift this forward that tells is something that the smaller automaton can tell me because this never uses the last character of the pattern it only uses up to the jth position so i can use the automaton i already know and simulate that automaton to tell me what should be the state where i'm i'm supposed to be at now so you can simulate the old automaton aj minus one on this text just suppose uh you start reading the text again but you omit the first character of the pattern

14:12 um and so we'll see um how this works in a second uh taken as this so this would work you can construct the automaton like this but it seems each time you compute one more arc you have to simulate the automaton so you have m states in total you have sigma arcs per state and each time you would have to simulate the automaton one smaller with something on the pattern so that would take another m time and so this this seems a bit expensive

14:57 and there's another another little trick the second insight from this algorithm is that we don't have to run this automaton from scratch because if you did this simulation it would always start with the same prefix p1 up to j and only the last character differs we have different characters c so we need a different arc here for the different characters in the alphabet that are not the correct one but the simulation would always use the same prefix so we don't really need to do it we instead can't just remember what is the second to last state and go one step from there

15:38 and so um that's what we can do we maintain a state x which is the state where we would have gone with this reading this in the automaton and from this state we go one further arc with all the different characters

15:55 and then we update we put these into the delta table there's a nice graphical way to show this and it's nicely shown in this video so i just show you this instead of trying to recreate slides for it i hope the sound is audible let's take a look at a demo that does the full construction for the kmp

16:15 The Full Construction for the Kmp Dfa

16:23 dfa uh so uh here goes uh 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 uh and uh the mismatched transitions are easy 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 started out without that character which would be the empty string so we start out with just filling in zeros

17:03 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

17:17 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 one if we found a c we go to state 0. and 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 two 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 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 goes where the machine would go if we saw an a that transitioned from two to three so we just move x to state one 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

18:35 it gets going so [Music] now the mismatch 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 and when we see a b x goes to state two

19:15 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 b a b b a b and that's a check all right so now it's 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 three now we're ready for state five we've got excel computed 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 that's the we do update x to get ready but when we get to state 6 we're done and again it's just as a double check 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:47 State Five

20:34 all right the audio was great but i can try to smuggle in the original video in the recording if you want to watch it again i think er i know it is maybe a bit slow but the the construction is very nicely shown that it's very simple you if you look at this matrix of the transitions you just have to copy columns and so um executing it by hand is is maybe the better way to understand what's happening here

21:04 uh let me wrap up this this sub section by looking at at how well these methods work so this might not have been obvious from how i showed this on the examples but uh if you've given this automaton finding the pattern in the text is really beating the text through the automaton and this takes n steps because it's a deterministic automaton so in each step you just need to find what is the transition i have to take that brings it to some other state and then you keep going from there you can do this with table lookups for this delta table that you've seen in the video

21:46 building the dfa uh necessarily needs as much time as you need rx to fill and there's m states sigma rx per state so that's the number of arcs sigma times m uh and with the construction from the video it actually is constant time per edge so uh in total if you sum this up we spend m times sigma time on the preprocessing stage uh plus n for the matching so that's the total time that's already um much better than n times m if m is not super small and even if m is fairly small the preprocessing step is also fast right um the space is what you need for this transition table of the automaton so again you need one entry for each arc m times sigma is the number of arcs so that's the roughly the space you need for executing this algorithm

22:46 in terms of the time this is actually really hard to beat for the matching part and because you do one table lookup for each character in the text and at least if if the alphabet is small this is also the best possible total time the big downside is the space overhead and think again so sigma is the size of the alphabet which can be small if you have something like dna but it could be the unicode alphabet which is 150 000 characters so you're trying to find a little string like love in all the works of shakespeare and you spend i don't know a megabyte of space for building this lookup table and you have to fill this first so you're probably halfway done if you just use the brute force method so this doesn't sound too scary using one megabyte of of memory but remember it grows with the pattern length and it's just a very very basic task that you might use many times so you want something really efficient there so we'll try to work on this a bit more especially bringing the space down and that's what then is called the knuthmore spread algorithm i think we'll reserve this gem for next time where you have fresh energy it'll bring all these ideas together

23:02 Space Overhead

23:53 The Knuthmore Spread Algorithm

24:03 and just take this idea of the automaton one step further to get rid of this dependency on sigma