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

0:00 Intro

0:02 in the next step section we want to look at the first non-trivial algorithm to find strings string patterns in a text and we'll use finite automata for this now i asked you to tell me what you know about um about these topics and it seems either many of you love emoji or you haven't had an automotive course so i'll i'll keep the references to all this um a bit short but at least you will learn something in this lesson that's that's useful

0:39 and there's also substantial fraction of the people who've seen that before but might have forgotten a bit of it for those it's a nice refresher then so in essence what this subsection is is as you ask me a practical question find this pattern in the text um and computer scientists or theoretical computer scientists tell you well this is this is something we know how to do listen here's here's how to do it um theoretical computer scientists talk about languages formal languages which are just sets of strings and you can write formal languages for example like this you can say this is the language of all strings that have something sigma star is is an arbitrary string arbitrary length then the pattern and then another arbitrary string and now you're asking if your text is part of this language so you can formulate it in this um [Music]

1:49 string matching in this deciding whether a string is part of a formal language we can formulate a same question in this problem now moreover this language on the right the sigma sigma star p sigma star is a regular language in case you've heard this before so in particular you can describe it as a regular expression which this kind of already is depending on the notation you allow it also means whenever a language is regular there exists a deterministic finite automaton to recognize it so we can just simulate this automaton feeding the text through and so in n steps this tells you if the pattern occurs or not that's really cool and pretty opaque if you haven't heard about all these concepts so theoretician says job done but programmer says hold on a sec there's a few problems you glossed over and the first one is not the serious one you can fix that one but the second one is a little more serious we say in this step there is some automaton but that's not enough to program it you have to find it you have to explicitly construct it and there is a way to do that but it can produce automaton automata that are exponential in the length of the pattern that's kind of a problem we don't want

3:19 that that's really expensive now let's ignore those two problems for a moment and see why despite these these problems the approach actually works it's just not completely obvious even from the theoretical perspective without looking at it closer why

3:23 Theory

3:42 but let's assume first let's make a visit to wishful thinking lands let's suppose we already have an automaton that solved this problem for us how would that work or formulate it differently if you've never seen autonomous now is the time to wake up because i'll tell you what they look like and so here is one this is a deterministic finite automaton abbreviated as dfa

4:10 there are these little diagrams with states and arcs they have a starting state that's where the arrow points to that comes from nowhere and then they have a bunch of states which are just these these circles and the automaton at every point in time is in one state and as the arrow suggests initially we start in zero a second feature the states can be like these which are with just a single line these are non-accepting if you read the string left to right if you read the string through and you stop in a state that is like this then you reject the string and if you stop in a state with the double line you accept the string now automata what does it mean accept and reject there are devices to tell you if a string is part of a language or not and remember we'll use this on this language so the automaton will tell you if the pattern occurs or not by accepting or rejecting the text that's how this works

5:17 now what i haven't told you is how the automaton runs and i think let's just do this on an example this is actually quite intuitive we start in state zero that's shown in this uh table down here um and now i'm reading the first character of my text and well here it happens to be an a then i i look at my state and check the outgoing arcs and there must be exactly one with an a in a deterministic finite automaton there's always exactly one outgoing edge with a letter for each well there's one outgoing arc for each letter in the alphabet now one uh one violation is allowed if there's no arc then you go to an implicit garbage state that you can never leave which means if there ever is no arc for your letter you're immediately reject because you're you're trapped in this in this doomed state we don't draw those because sometimes automata have tons of arcs going to this garbage state so that would clutter up the picture that's the only exception what is never allowed is having two outgoing arcs with the same letter all right so from zero there's an arc to one so we are in state one now if we read another a we follow this arc so we're again in

6:33 state one now we read a b that brings us to state two now we're in state two we read an a where do we have to go straight we follow this one from the three a c brings us back to zero from zero on a is back to one and we stain one with another a one with a b brings us to two then a brings us to three and now we go forward to four and actually five and six and seven and here we stay with whatever letter we just stay in seven

7:16 so the automaton has accepted the text which means there was a pattern occurring somewhere in the text but the well this doesn't immediately tell us where is where the pattern occurred but if you pay close attention the first time you reach stage seven signals the end of the first occurrence and after that we just stay in seven forever so it's not very interesting and so you can calculate back from this uh you know how long the pattern is so it must have been at this position whatever that is in the text you can keep track of the index in the text okay that's how a deterministic finite automaton works and this automaton magically does the job in that whenever i feed it with a text that contains this pattern it will end up in the accepting state because you basically march down to the right through the states what's not obvious is if you take any of the other arcs it will not mess things up you will also find any occurrences that come later but we'll come back to this

8:29 Explanation

8:35 so why why does this automaton work and how can we possibly construct this if it's not already given to us the key insight is this in the in the box and

8:52 might need a second to to digest so it expresses what a given state expresses in knowledge about the text it means if we're currently in state queue that means the text ends with a prefix of the pattern namely up to the q with position but excluding that one and also there's no longer prefix of the pattern that we have seen up to this point okay so the state's number is the length of the longest prefix of the pattern that's the suffix of the text we've seen so far anyone followed

9:36 i hope this is somewhere written here in roughly the same way well this is maybe the the shorter way to express it now why is this enough to determine if we find a pattern occurrence and how to do the next step because this is just saying we can somehow guarantee this invariant that we always keep track of the the longest prefix of the pattern that we've seen but we don't know what the text looked like um before this occurrence so how can we keep track of this invariant so if we find the next character and it matches then we just make q1 bigger that's that's easy enough that is why we have these edges to the right whenever we find the next character in the pattern so for example if if we're in state 3 it means we have seen the first three characters of the pattern which is aba we don't know what the text was before but this is where we currently are if the next character in the text now is a b that happens also to be the fourth character in the pattern so we just go to state four represent well expressing the new knowledge that the prefix of p is now one longer uh the interesting case is when the next

10:58 character is not the right one not the one that the pattern has so like in this case in state three the c and here's c is for for an arbitrary character we know what we know about the text is it ends with this prefix of p and this one u character we also know that this is not a prefix of p

11:25 because the c doesn't match okay um and the third thing we know is without this c this was the longest match uh the longest prefix of p that we could find so in in in pictures that's what the text looks like in this situation we have this prefix and the new character now what we try to find is a new state which again is the longest prefix of the pattern so we want to shift the pattern to the right so that now uh we again find a partial match and the good thing about this is it only needs the portion of the text that we know it is irrelevant what's to the left because we only ever shift the pattern to the right so we can um intuitively we can just go through all the possible choices we can shift the pattern by one and check if all the characters aligned match if not we shift one further and so on and so forth if we do this in our example we have so this was the case that okay let me leave this one so we go to state four but then the other option was if i have a b a and now i read a c um there's nothing in the first few

12:46 characters of p with a c so if i find a c in the text i know there's no occurrence of p containing any of these positions i have to shift the pattern entirely to the right so the earliest occurrence can be starting after the c and that's why i go back to state 0. the longest prefix of the pattern i can have seen at this point is empty is no way i can start with a c okay

13:25 so the important message is that this this new longest prefix is always shorter than the previous one so all the information we need is contained in what we know about the text so far what we haven't figured out yet is how to efficiently find this this next transition