Video 4-3: §4.3 String matching with finite automata

0:00 String matching introduction

0:02 in the next section we'll look at string matching using uh finite automata or DFAS eventually of different different such things if you've had some undergr class in autometa theory some of the things will uh will be familiar um but it's not often discussed as an application of all that theory I think it's a nice way to motivate that so just to see uh where people stand on this I won't r on this much and I could already make a prediction how this will how this will pan

0:41 out probably the twoth thirds who do Advanced Computer Science um have seen at least part of this and the other third might not have seen much of it so it's the same old problem I can't really rely on everyone knowing it um but in this case I don't think it's rep petition so I'll I'll just go through

1:40 way okay if I remember correctly we had a few more people vote for the attendance code 128 but most people have cast their vote this is not not so important so many many haven't heard about this um and then the others a split between okay I've I've heard this before but I don't really remember so much um plus a few

2:06 others so in this case we don't really need to know any about this it just makes connecting the dots a little nicer for those of you who know it uh but you can follow the part that I present either

2:23 way for those who know it uh the short solution for string matching really should be we try to find the patterns somewhere in the text that's to say we try to represent the text as the pattern plus some string of arbitrary length before it and some other string of arbitrary L arbitrary length before and after the pattern after the pattern and before the pattern H and because it's Sigma Star both can be empty so it's fine if the pattern occurs right at the beginning and so on that's just a a different way to phrase the problem now I've uh

3:08 I've lost in this uh for the moment the Restriction that we want to find the first occurrence of the pattern um that's a bit more tricky to express if but you can can still try but we won't we won't have to worry about this um the automata theory or formal language theory part here would say ah this is a regular expression or regular uh language and it's recognized by a regular expression and so that means we know that's

3:48 Understanding the automaton

3:50 Theory there is a thing called deterministic finite automaton I'll show you what these are that recognizes this and so we can feed the text through this in in exactly n steps as many steps as the text has characters not n * m or anything like that right just end steps once we have the automaton and that automaton should be able to decide if the text is of this form which means it contains the pattern or not so that's that's good um a theoretician might say okay cool that's all I need um maybe not uh there's a few things that are open first of all maybe you don't know all this stuff then it doesn't help but you can learn about it more seriously though uh this would only tell us there exists a pattern but it doesn't tell us where it is uh it only exists it says there is some occurrence of the pattern doesn't tell us where um and also who knows like this automaton that's an existence that just says there is some but maybe it's absurdly big and it's just is beyond practical and both of these problems could be very real now it turns out they both aren't really a problem but uh you want to look inside the black box to see that that

5:14 indeed is the case so uh let's first go over what an automaton is for us we can basically think of it as a diagram like this uh we have States these are the the circles and I just numbered them they can have other names if it's convenient uh but this doesn't matter it's some set of states and we will use the numbers because they have some meaning in our case but that's uh up up to us uh and we also need an alphabet Associated for such an automaton that's the type of letters that can occur on these edges um we also need a start state so that's usually just shown by a little arrow coming out of nowhere that means you have to start in state zero initially there are these double line States these are accepting States uh that has a meaning in the formal language sense for us it it will just mean okay we found a pattern that's kind of the success moment and then there's all these arcs which tell you ah if you're here and you see as the next character an a you should follow that Arc and go to state one now more formally people often write this uh instead of drawing this this picture you can um specify the so-called

6:25 Formalizing the transition

6:35 transition function and I'll always use Delta for that that's a function that maps from the states so Q is the set of states Sigma is the alphabet that we

7:11 use it maps from a pair of states and the next character that we read to a new state so for example here the edge I just showed you when we are in state five and we read an a we go to State

7:31 One okay so you can either give the automaton by specifying this transition function plus all the other information you need to say what the start state is and what the alphabet is uh this the transition function you can give as a table then it's kind of implicit we can say the the states okay let me try to squeeze this here we can have the states up

7:59 here and we're going to have the letters uh the rows and then you can try to fill that table and I'm not going to do it because it's too many many steps I'll bore you to death but uh the entry for five and a should be a one that's that entry here okay so you can either give the table or you can give that drawing uh we don't need to um to be overly formal on this now there's one important bit that I didn't talk about yet and that's the word deterministic deterministic means there shouldn't be any ambiguity or any chance now where where could there be ambiguity if you look at the transition function the way it's called a function means for every pair of states and symbol there can be exactly one state and also uh there has to be one so if you draw the table that's kind of obvious but in the picture you could have several outgoing AR Mars with the same letter or there could be letters missing so deterministic just means exactly

9:12 one Arc for each character okay so what does all of that have to do with uh string matching what I'll promise you on this slide and we'll come to how to get there is that this this automaton that's drawn here is capable of helping to recognize texts that contain this pattern P okay first obvious thing to note if you look at the pattern you find the pattern here a b a b a c a if you just follow the edges that go left to right you find the pattern again so at least it occurs in some sense in the automaton that's reassuring right um the way this automaton works now is hopefully very intuitive you initially start in the start State you always are in one state and then you just do what the arcs tell you to do by reading through the text so you're initially in state zero then if you read through the text the first thing you find is an A so you're in state zero you read an an a that takes you to State

9:26 Pattern recognition mechanics

10:42 one so I'm I'm probably not going to be able to do this for all of the letters otherwise we'll get in a very messy picture I'll just draw it for one one transition now we're in state one and we read another a The Arc there takes us back to State one and that's all that you do now if you ever reach that state seven while you're doing this you found a found An Occurrence and uh the more that's kind of obvious because we just followed these these green edges the more interesting statement is that if you do not end up in state seven then there's no match up to this point uh and we'll get back to that uh let's complete the table just uh to finish this off so we're in state one still we read a b that brings this to state two we're in state two we read an a this time the next so I'm just going through the characters of the text right this is the text written down again so from state two reading an a brings us to state three from state three reading a c all the way back to zero all right zero reading in a brings us to one one reading in a brings us

11:54 back to one one reading a b advances us to two now we see another a that brings us to three been there before but this time we see a b which gets us further to State four from four we read an a gets us to five and then we read a c and then an A so you get to six and then seven and so that means ending with the current letter with the one that we've just read there's an occurrence of the pattern so from here down to um well the length of the pattern back we have ABAB AA that's our pattern okay and for string matching we would now return that we basically found a match starting at this position so that's that's the connection between those

12:54 two and uh here's the same information without the messy drawings now um you could spell this out in code and you find detailed code in the book If you if you want to look that up um now the code can't use these kind of diagrams but it can use a transition function and variables and so you maintain the current state you read the next character you take the transition table to tell you what the next state is that you go to it just keep going like this each time checking if you reach the final state so the code for that is not hard and uh each step just takes you um so uh each letter of the text just means one one lookup of of the next state and potentially a check for the final State that's very cheap right uh so let's also write that

13:50 The intuition of states

14:09 we read at most each text character once and you should compare this to the brute force method which in the worst case needed n * m right if m is a few hundreds of thousands of characters long it's it's quite a reduction now of course uh this all hinges on someone telling you what this automaton is and uh let me also tell you if you just just took the the car the arcs that go left to right and don't pay attention to those going back then you can miss occurrences so you can't always just jump back to zero for

14:48 example so what we're still missing is a way to build that automaton but if we have it we have a good string matching algorithm now um to to build our way towards this uh let's first understand the automaton more and then worry about how to compute it efficiently and the the main Insight is to give the states a specific meaning and once you internalize that much of the rest Falls kind of into place so that's that's the an important bit to um to pay close attention to uh the intuition is that if you're in state q that means you've read some some part of the text fine [Music]

15:33 um so you may have seen the text up to this point and it may continue but at this point you've seen a certain part of the pattern a certain prefix of the pattern so maybe the pattern can look like this and you've seen up to here a certain prefix of the pattern in the sense that if this is p and this is the text then these characters are all matches so they're all the same okay you always have seen a prefix of the pattern if the prefix can be empty right so this is not saying anything you can always find a q so that this is true if you set Q to zero for example but the point here is that it has to be the longest C

16:37 so there's no way to put P further to the left and also get get matches all the way across so this means somewhere along the way here you have a mismatch you have a character that doesn't match if if you're in state q it means the length of this thing is q and whenever you shift the pattern further inwards the text giving you more matched characters something goes wrong at some point one of the characters is mismatched Okay so we've we've seen the prefix of the pattern and that's the longest we've seen so

17:18 far um okay now uh you may wonder if we take a step back uh how is it even possible to have a a single automaton that works for all texts now we still have to read the text but uh how can it be that we can find occurrences in the text if all we build the automaton on is the pattern and um the reason to see that that's enough information that all the information you need is is this prefix of the pattern you've seen so far is the next step read about read the next character and see what can happen

17:23 Correctness and invariants

18:03 so if we um if we're in a certain state q and we now read a character C from the text we don't know what that is the text could be anything um so one one letter C comes so um there's two options it could be the next character of the pattern then we just go to the next Arc so if we're in this state then we've seen the first three characters of P and not more if we now see a b then we've seen now the first four characters of p and that's that's the easy case if if we have a a non-match so there's not the right character coming what can we say well we've seen so much of the text let me draw this again to not clutter it up too much so the text may continue in particular it continues one further letter with c and we're in this in this state we've seen up to here let me draw it so I can draw the green things in between this is the

19:19 pattern and then we had matches up to that position but then a mismatch with c and this here is the first Q characters that's the situation we're in and now the argument is all we need to know is in this prefix of P it doesn't matter what the text looks like before that

19:52 occurrence so everything that's before that occurrence is irrelevant from the and the reason for that is that we picked the longest prefix if C is a mismatch then uh we have to shift p further to the right to get a match again if there was a way to shift p to the left then chopping off that last character would give us a longer than the longest prefix and that's a

20:29 contradiction so what we can find is some some Q Prime as shown in this picture here all right let me try it again so that you can shift the pattern a bit further and now you can get alignment up to this

20:52 point of all the characters here including the C and we already know this Q Prime must be at least one long one shorter than Q it must be strictly less otherwise we would get a contradiction to this longest prefix from

21:16 previously so that's why such an automaton is even possible all you need to do the next step to maintain this invariant that you're in a state that stores what's the longest bit of the pattern that I've seen so far in the text ending here all you need for that is in that prefix itself so the automaton can work for any

21:55 Modifying for multiple matches

21:59 text now um this this kind of argument is also the the correctness proof of the string matching procedure um that's what I alluded to earlier when I said when we're discussing this example the the important the easy bit is that when you reach the state seven the accepting state that you found a pattern occurrs because you just walked along this this path uh the more tricky bit is to argue that if if you're not here then you have not found one so what you would have to do is um prove by induction that this invariant is always maintained and because it's the longest prefix of P that we've seen up to this point if all the way through the text you never reach up to State M the length of the pattern then you've never seen the entire pattern uh this this part is a little less intuitive to explain I think um you have to go through this invariance is there a question

23:07 B um uh are you in this example yes uh so uh letter B at the end of the text or at the end of the pattern so another B at the end here

23:24 um so uh as you see in the picture the way the automaton is drawn here it would just stay in that state seven forever uh so what this Arc with Sigma means is it stays there no matter what comes uh we don't really use the automaton like this because the first time we reach that state we will just immediately return um you could modify the automaton to keep going so that you can keep keep reading through the text that's a small modification now so in this example it means what whatever comes you will always stay in state seven I'm not sure if that is your actual question uh in this that's kind of a a boring answer

24:09 um I think you'll you'll look at this in one of the tutorial problems as well uh you can just extend the construction for the automaton to the last state and then you get the matches the the the edges that you would need for the mismatching characters there so you you can extend the automaton so that it keeps reading and it just flies by this accepting State whenever there's An Occurrence um that's maybe worth worth noting down we might um I comment on this in the in a later unit on on on the parallel

24:53 problems but because we discussed it anyways let me write it down briefly keep keep finding other CES so what what this getting at is the DFA can find all

26:12 occurrences and essentially the same time it can just uh tell you once it found one um I think the Cod the the book has detailed code for that part finding all occurrences we'll at least get to it in the context of the KMP algorithm um if you're if you're very keen maybe uh ping me on campus wire the changes are not too hard um but maybe if you're seeing it the first time that's that's not quite true