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

0:00 Introduction to automata

0:04 in The Next Step section I want to show you the first algorithm that exploits these kind of avoids these kind of redundant comparisons with the text characters and for that we'll use finite automata so that is the point where I want to ask you how familiar you are with this

1:19 all right so uh a third has never seen it a third says Ah that is that a thing I don't remember something weekly another third has seen it but you know maybe not test me right now

1:37 it is essentially just a way to view the algorithms that I'm going to explain which I think is is much more memorable now it might not be as memorable if you haven't seen these before so I'll try to briefly explain what these automata do um and then we'll see if it was effective for you in a way the problem is is all solved for us already if you look at it from the right angle because if you're trying to find a pattern in a text we're trying to check if the text is part of this language namely the language formed by any possible string of any length followed by the pattern followed by a more arbitrary characters clearly that's finding pattern in the text now expressing that's the first pattern is a little more tricky but let's ignore that for now I will only use this as a vague motivation anyways but if the text has this form if the text is in this language so this is probably something I haven't formally defined with writes sets of strings and then the concatenation operator to produce all possible combinations any string from the first set with any string from the second set concatenate the two that's one element of the resulting set and so in this in this mixture it's even

1:54 Language theory context

2:58 I should have put uh curly braces around the P I guess uh so it's is there any string followed by P followed by any other string that's all the strings in this set of strings in this language and we check whether T is an element of that set now uh that formulation might not have helped you too much but if you've seen regular regular Expressions regular languages before you may remember that this is a regular expression this the cleaning star is a regular expression operation and concatenation is and so you can write this as a regular expression you could use any kind of programming language library for regular expressions and express that they often have again different syntax but uh they they can express something like this now theoretical computer science will tell you that okay if you have a regular expression there is a deterministic finite automaton that's what the DFA was that recognizes exactly this language and a deterministic automaton reads one character does one state transition and then it's done with its work and waiting for the next thing to be fed so if you feed it all the characters of the text one by one you will you will uh get the result from the automaton yes or no it's in the language or not

4:27 so you get this after T steps that's almost as good as it came back as it can get right you need to read the text to solve this problem so that's that's pretty good uh so remember this guy theoretician says Ah it's brilliant so well what are you why don't you worry about this uh Brute Force algorithm Etc it's all done for you okay I think as an abbreviation it's uh fair game

5:02 all grown-ups aren't we so there's a few things where the programmer will correctly insist that we're not so done yet uh ignoring this zeroth problem uh it's not enough to know that there is some algorithm out there if you want to implement it you have to also be able to write it down and more seriously the automaton that results from that such a construction in general can be really big exponentially big to be precise that's a bit of a problem even in theory right so we don't like that too much the approach will still work uh but for somewhat interesting reasons that don't fall out of this Theory automatically if you've never seen automata automata before then this hasn't helped you too much but also don't worry too much because uh I'll show you examples of the automata that we need and then you will get enough of automata for this class definitely read it up because it's cool Theory but um you may survive without

6:08 what we usually call in automaton these kind of diagrams um I'll I'll show you how this what what how that is an automaton in a second um I first want to convince you how you can do string matching with this DFA where we still have to address the problem that this regular expression just said there's some occurrence somewhere in the text it didn't directly tell us where the occurrence is and it didn't guarantee that we find the first occurrence both of which are really no problems but uh I think an example makes that clear so treat this automaton as given to you from some super smart person and don't think about it how to construct it for now this is the string matching automaton for this pattern and you can always verify this by checking that there's a b a b a c a the pattern written on these on these horizontal edges now uh the way these automata work they're um little machines that are supposed to be in one of these states each of these round square round circles is one state that the automaton could be in there's some indication this arrow that comes from nowhere is the starting state so you're supposed to start there and what you do is when you execute the

6:20 Automaton mechanics

7:37 automaton you read the text character by character and the diagram tells you what to do you just follow the single the Unique Edge with the character that you see so let's let's try and do that and I'll explain the rest on the way we start in state 0 as I said then we read an a that's the first character in the text now if we're in state 0 there's an arrow with a going to state 1. so after this we're in state 1. same thing happens now except that now we look from this state with an a we stay in the same state we're still here but now we read a b and that takes us to state two

8:25 from State 2 with another a we go to state three and now it's day three if we read a c we have to go all the way back to zero and and let's speed this up a little okay a brings us to one from one with an a we stay in one with the B we go to two with an a again we go to three and now we see something new from state three with a B we go further to four and to five and to six and to seven so you can already see if you if you find the pattern at any point in time in the text you just run through the states go one state further up each way if you ever reach this double circle State that's an accepting state which means you're allowed when you end in this state you're allowed to declare Victory you can say I accept this input that's the automaton point of view the string matching point of view is as soon as you reach this state you can you can return because you found an occurrence of the pattern and the way we do things the way we construct these automata will guarantee you that it's also the first occurrence if you had seen one before you would

9:42 have reached this state before so you would have returned back then as an automaton I I put the sigma here so whatever happens you stay in this accepting State because more chunk at the end doesn't destroy the fact that you've seen the pattern already

10:04 is it clear how the automaton works now it's called deterministic because for every state and every character there's exactly one Edge that you have to follow so you always uh you always know exactly what to do so there's no no um autonomy in this automaton it's following exactly what you tell it and you can completely predict what will happen

10:37 State transitions logic

10:40 so to to better understand the algorithm see the automaton and also to be able to construct them uh let's Zoom a bit further in what these different states mean it seems to have just worked in this example that once you read once you run through all the states you get to the end so the I think the the part that's kind of obvious is this chain left to right if you are able to just step through all the states like this especially like in this example where there's one two three four five six seven you just go to these one after the other it's obvious that you found the pattern what's not so clear is Maybe how do you make the automotive so that you don't ever Miss An Occurrence because um you you may have half overlapping half occurrences then you jump back because you couldn't continue your current guess but maybe there was another gas half overlapping and now you're you're not finding that one uh that's that's the thing that could happen if you just start drawing random edges the key Insight that makes this work here is the following you're in this state q in a certain position in a certain number Q if you were able to find the first Q

12:01 characters of the pattern in the text up to this position so as a as a suffix of the part of the text you've read so far you find a prefix of the pattern and it's position 0 up to Q exclusive so it's length Q the number of characters you could match is q and also important there's no longer prefix of P that you could find this way so um I will many times draw sketches like this let's do this here as well here's the text and you've really only seen it up to this point so whatever comes after this we don't know yet it's a fog of War and we try to find our pattern

12:54 align somehow to the text again there's some parts sticking out and all these positions are matches so I'm drawing those in green even though it's just this probably is not visible as green

13:21 so these These are green because they're equal they're matches um and also this is the longest the longest such overlap so if you put the pattern in any other way

13:50 so that's the pattern if you if you would do that then there's some mismatch to the text so the the state q is the longest the longest part of the pattern you have seen up to this point okay

14:13 that's the important distinction here's the picture in in slightly nicer but that's explaining the next step uh I think it's it's useful to go back to the example to a certain position let's say we look at this part

14:40 so we've seen the text up to here and we're trying to put the pattern in partial overlap with this in the best possible way how many characters can we match and so I could have put the pattern further to the back the pattern starts with a B so I can put it like this that would also be a match but this is not the longest because I can find this longer one that has a b a b a c a now again remember I'm I'm ignoring what's on this side this is not visible but this is longer than these two so I'm in state four at this point because the longest prefix of the pattern I can match with the text so far is is length four

15:39 now it seems maybe at first a bit weird how can you forget everything about the text and just remember this single number without forgetting any occurrences in the text and the reason why this still works is that uh you keep you keep track of the pattern that you've seen and you keep track of the longest part that you've seen so we know that the text ends with these characters that's what this picture shows there's the text and we know at the end of the text so far there's the first Q characters of P and now we see one more character C that's the next character we look at and we try to decide what's the next state to go into so our DFA always has to be in one such state so I have to know for every new character what's the next state to go into

16:37 now there's there's two uh possibilities the easy one is if I can just uh if I see the next character that occurs in the pattern at this point then I'm just seeing the one longer prefix so I go from Q to Q Plus 1. that's the easy case

16:54 that's the part that we've seen before many times so when I was at this position and I see another a I can just extend this uh existing potential occurs it's partial occurrence by one so I go to state five the tricky bit is what if that doesn't work then I might have to go to a a much smaller State maybe all the way back to zero like all these these long arcs here LED back to zero basically saying I haven't seen anything of the pattern up to this point

17:29 but how do we know how far we have to jump back I'm looking for this Q Prime which is the longest overlapping bit uh for the with the text that I've seen so far

17:48 and the the trick here is that I never need more characters of the text than are covered by this pattern here because that was the longest occurrence so if I have a mismatch now the new part that I can match cannot be longer than that only if C is a match but it cannot be reaching into this un this part of T that I've completely forgotten

18:19 that's why all the information is is in the automaton that we need the new longest match will always be shorter than Q and that's why all the characters we need for that are contained in there

18:46 now this is all great um but it still doesn't tell us how we can possibly find this automaton it just lists a lot of uh wishful thinking properties we would like this box to be true we like to always have these states but how to find this next q Prime is still a little unclear