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

0:00 Limitations of brute force

0:04 we've seen our first simple method the brute force string matching method which was okay but sometimes had a really poor behavior and one reason for that is that it doesn't exploit regularities in the pattern in this next subsection we want to look at a first attempt to overcome this and for all of those for all those of you who have seen a formal language class you actually have all the knowledge that is needed for that except you might not realize it and for all those who haven't seen uh regular expression and and grammars and all and automata um we'll we'll briefly recap how these things work before we start with that though i want to see how familiar you are with these things

0:18 Theoretical background poll

1:02 no i don't seem to have that question prepared so uh let me just start this as [Music] um so i'll just put in the the dummy options for you and you can use the slide then

1:28 okay so ignore the the text in the question on slido uh i somehow lost the the question when i prepared the session um but just uh use what's written on the

1:55 okay i'll probably have to switch back and forth a couple of times uh remember a means you haven't heard of this you see the results next to it but i want to show it for the video as well and b says uh you remember the terms vaguely but not very well and c and d are means you're fairly familiar with it and i think most people have voted now and most people seem to either not have heard it at all or just vaguely remember it weren't qh is enough to claim that they they do remember uh so that's that's fine um that means um i will go slowly over these parts thanks for participating in the poll

2:37 String matching with DFA

2:43 if you if you do know then this problem becomes simple because you can recognize it is asking the following question uh if you're if you're looking for the pattern in for a pattern in the text so here's our text again i'll draw these pictures 500 times so um get used to this

3:10 if we try to find the pattern in here it actually means so if these match at this point i will i will draw these little lines to say that there's equal characters in these ranges what that really means is there's the pattern here and then arbitrary stuff uh before and after it and that together gives you the text

3:40 okay another way of saying we can find the pattern in the text is saying the text is something followed by the pattern followed by more something a different something potentially and this is uh what formal language people write in this way this is the set of all strings over this alphabet sigma so that's stuff this is again more stuff and there's the pattern in between so this uh this term is the set of all strings that are formed by something followed by p followed by something and something can be empty in both cases okay people from from regular expression people from from formal languages will know that this is a regular expression which means that this language that results from it is a regular language a formal regular formal language and if you've seen an automata class then you will know that for all regular languages you can find a deterministic finite automaton a dfa that recognizes this and by simulating this dfa on the text so you feed the text one character at a time into this automaton you can read off from the automaton uh what is the uh if you find a pattern and what position okay uh that's pretty cool so as the theoretician would say job done let's go home uh

5:08 Practical challenges

5:11 the practitioner the the programmer who wants to implement this might say hold on uh not quite uh first of all i don't know about all this stuff so please help me out and uh more seriously also if you if you do know uh this just says there is such an automaton but uh it's not clear how to compute it maybe and the second problem is these automata can be very very big and then they would be close to useless for an efficient algorithm it turns out both problems are not a real problem they can be very efficiently solved but they require a little closer look than our available

6:04 Simulating the automaton

6:06 it's a directed graph there are these circles that's these are states that you can be in and then there are arcs or directed edges with letters on them which are the labels um that are assigned to this and um you can you can simulate such an automaton but basically starting with the start state so this this arrow indicates where to start and then whenever you read the next character you just follow the edge that is labeled with that character okay um maybe i'll show you just the picture for the moment this automaton is built from the pattern and you can see this by uh reading the characters on this chain of of states from 0 to 7 you read exactly the pattern a b a b a c a that's our pattern what you do if you want to find the pattern in the text now is you simulate the automaton on the text let's do that briefly together we start with the initial state zero here's the text um already prepared this in this table so we read an a we're in that state zero at the moment so we check what edge goes with an a so that's goes to state one now we read an a again and the arc says we stay in state one

7:34 so we're in state one still now we read a b and the edge for b goes to state two okay so now we're in state two and we read in a so you you see how this goes uh state three with a c leads us back to zero um from zero with an a we go back to one and another a we stay in in one now reading a b takes us to two again then we read another a takes us to three read another b here so that takes us to four and now things get slightly more interesting we actually get to

8:19 the end of this automaton and at this point we have we have reached this node 7. uh this work this state seven and that's double circle that means it's an absorbing it's a final state an accepting state if you end up in that state you will accept the input so automata always do one of one or two things you feed them with a string and they either tell you i like this string or they tell you i don't like this string they accept it or they reject it and they accept it exactly if and only if you end up in a final state after reading the input okay we do one more a but then here the entire alphabet just keeps us in in this final state so that means this automaton is built so that if there is an occurrence of the pattern in t that first occurrence will take you to state 7 and you will stay there indefinitely which also means the first point where you found state 7 that is the end of the first occurrence right so you can find a here is your occurrence of the pattern abab aca

9:35 that's pretty easy that's um mostly what we need from automata theory the other things there's a few other concepts that will make more sense if you've seen them before otherwise the motivation might not make so much sense to you but you can still follow along by just looking at the examples and listening to what i say

9:57 Intuition and invariant

9:59 so here's that table filled out in nicely uh what is going on here what is what is um the intuition behind this and i want to stress that part so this uh this automaton i just threw this at you and i i said this is built from the pattern and we will look uh closely at what that means and how to build it the main insight that is behind this automaton is is this invariant if you're currently in state q it means you have seen a prefix of the pattern of q characters position 0 up to q but excluding q remember

10:44 so this is this is the longest prefix of the pattern you have seen up to now when you start when you start reading the text that's the longest prefix of the pattern you can find in the the current portion of the text and no longer prefix of that exists um so this is this is shown down here but um in a we need that picture for something else um let me let me show this again so one more time my favorite picture here's the text the light's doing weird things today

11:21 you feed the text through this automaton so there's a certain portion of the text that your automaton has not yet seen okay so this is this is the prefix that the automaton really has read

11:39 you feed this into the automaton character by character and after every character this the automaton changes state and that state tells you what it currently thinks it has seen and if at this point you're in state q after reading this last character then it means that there's a prefix of the pattern

12:06 maybe the pattern would be here but we don't know if this matches the only thing we know is that up to here it matches and this is this matching part is exactly up to sort up to up to state up to letter q but excluding this last one okay um that is what is meant by this invariant and that's how this cons this automaton is constructed

12:44 um why why can something like this work so here the puzzling thing is that this automaton is only constructed knowing the pattern it doesn't know the text and the same automaton works for all texts that might be a bit surprising how is this possible because if the automaton only knows the pattern how can it react correctly to all possible texts and the answer to that is is in this observation here

13:16 the automaton or its state to be more precise tells us that the text we've seen so far ends with a certain prefix of the pattern that was the previous state q and now we read one more character from the text c

13:34 if we have a um if we have a mismatch if we do have a match then we just go to the next state and uh we know again um more about the text we have learned more about the text by knowing that there's one more character we could match but how do we know what to do if it doesn't match um then we know that this is not a prefix of p and we know uh before we had c this was the longest prefix okay so this also means if you're looking at if you're looking at this picture down here if the text currently ends with um this uh shouldn't be the entire text there can be stuff before it i forgot to draw the stuff so uh t is stuff followed by a prefix of the pattern and now this new character c which is not the next character in the pattern so this is um it's not pq

14:46 otherwise we would not be in this case um then we would want to find a new state q prime and that state can only be smaller so it's completely determined by the characters we already know and the one character that we read so all the information to decide uh what happens is already in the automaton

15:12 i hope this uh helped a bit to clarify why the automaton really has all the information necessary to determine what next state to go to and hence to decide whether the pattern occurs in the text