Video 5-2: String matching with automata

0:01 In the next section, we'll see how to do better and for that we'll also establish some common ground for some several future methods. Uh so it's um it's worth spending a little time on on that part. Uh it's also an invitation to kind of apply all your knowledge about uh automata theory if you've had some under undergrad introduction. Uh if you've seen these these kind of things, regular expression and formal languages, you could say string matching is nothing but deciding whether the text has a specific pattern matches this regular expression. Namely, an arbitrary string followed by the pattern followed by more arbitrary string. That's what pattern matching asks about.

0:48 And because this right hand side is a regular expression, there's an automated pipeline of algorithms that gets you from this description of the of the language a deterministic finite automaton, a small little machine or program where you can feed the text through and it'll tell you whether the text has this shape. And so with that, you can check for an occurrence of P in exactly n steps. uh you see one letter in the text exactly once. Uh you can even tweak this this automaton to um give you all the occurrences but then we'll we'll come to that. So as a theoretical computer scientist maybe you would say that's all that's needed uh uh for a practitioner. There's a few things that are left open. First of all maybe none of this made any sense to you. So if that's you then don't worry. Uh this is connecting to some other TCS topics but we don't require to use them. Um even if you do know these things that this automaton exists doesn't mean you can efficiently construct it.

2:02 And indeed the automaton might be big if you're just looking at the worst case of these constructions. It turns out that for the problem we're trying to solve for the specific kind of regular expression the automaton is never big and you can always find it fairly efficiently. Uh but for that you have to use the specific structure of the uh of the specific regular expression. uh jumping to the end. For those of you who haven't seen this, this is what one of these automata can look like. And let's see how how it proceeds through a text to check if there's an occurrence. So we have this this pattern P uh AB A B A CA. This is what you find if you read from left to right through the the state transitions and each time on the arc you see the next letter of the pattern. Uh the way such an automaton works is that you initially start in the state zero because that's where this arrow goes through. So it says that's the starting state and then in each time step you read one more letter from the text and you follow the arc with that letter. And the way the automaton is built means that there's always exactly one choice.

3:18 And so let's quickly do that. We start in state zero. Then after reading an A, the first letter of T, we move to state one. Now in state one, we read another A which here says you should stay in state one. Then we read a B from state one. That brings us to state two. Then from state two, we read another A. Aha, that brings us to state three. In state three, now we read a C. That's the next letter in the text. And that tells us to go all the way back. Okay, tough luck. So we have to do that and then you keep going in each time step you consume exactly one character. So after n steps the text is pro processed entirely and you find if you do that here that at some certain point you reach this state seven and that's a special state because it's marked with these double lines. It's an accepting state that signals I've seen the pattern.

4:22 The way it's set up here says after I've seen this state seven once, I'm going to stay there for good. So this automaton only finds the first occurrence of the patterns. But you could easily extend this. So get rid of these transitions, add others. uh we'll come to which ones and then the same automaton can be used to feed the text through once and find all occurrences namely whenever I'm passing through this state seven I'm going to say h I've seen the pattern just now and then you can output the starting index okay that's a deterministic finite automaton it's finite because it's finite size has a fixed number of states they're given by the length of the pattern Uh, it's deterministic because in each step there was only exactly one choice no matter what the next character in the text was.

5:21 Now, why would this even make sense that such an automaton can exist? Why do I not need to know the actual history of the text? Why can I build a single automaton just from the pattern and it works for any text without remembering the previous parts of the text? At first, this should give you pause if you never thought about this why this even works. H but the reason is that if you've seen some some initial portion of the pattern and then you see another character, there's two options. Either you can extend to a one longer part portion of the pattern by having one more character or that doesn't work. But then all that you can have now is a is a potentially shorter version of the a shorter prefix of the pattern if you always keep track of the longest prefix that you you've seen so far. That's why here the the meaning the semantics of being in a certain state is the longest prefix of the pattern I can have seen so far by reading through the text has that many characters.

6:31 If that's the case, then any transition can only reduce the length of this if there's a mismatch. And that means all the characters that you need to find out how far you have to go back in the pattern, that's all determined by the prefix that you previously matched. And these characters before that, they're not interesting. they're never used.

7:02 All the information that we could potentially need is contained in this prefix of the pattern and the next character. Now you've seen how we can use such an automaton if you're already given one. Of course, you also want to compute them given a pattern, right? And again you can take a a short visit to the theory of of formal languages in automata. There's a different kind of automaton. And here I'm stressing this again because we'll we'll use the very same trick later in uh the context of using several patterns. Um the other kind of automaton is a nondeterministic one where there's two new features. uh you can have several or no edges for certain letters which means you can have several continuations or maybe also none in which case one one computation dies out. Uh and you could also have epsilon transitions which means you can spontaneously go from a spate to another without consuming a character.

8:08 Uh with this extra freedom an automaton that matches exactly this this pattern is very easy. It's just the pattern written down plus an option to stay in state zero. And then it's up to the user of this automaton to figure out when you should start moving to the right or when you should stay in state zero. And the point is once you started moving along this line, you have to kind of hopefully know the future that you can keep continuing because if you ever read a character that's not the next in the pattern, the whole computation just stalls because there's no edge that you can follow. Now, this seems utterly useless. First of all, it's just a pattern written down with some uh extra arrows added. Uh why is that even useful? Um despite this you can actually use this to uh find the pattern by on the fly simulating all possible computations. So now uh this is almost a bit like uh if it was some quantum system but there's no quantum in there. Uh I'm just imagining I'm being simultaneously in all states that I could be uh I don't know positively framed schizophrenia. whatever. Um, initially I can only be in state zero because that's the starting state. But I can read an A now in two ways. I could either go to state one if I guess that's the beginning of the pattern or I could stay in state zero if that is not the beginning. So I'm after reading this a I'm in two states at the same time. And there's nothing wrong with that. That's my uh that's what I called positive schizophrenia if that exists. Okay, I'm not making fun of the mental illness.

10:05 So, let's let's skip that uh that term. But if I'm simultaneously in state zero and one and read another A, as I'm doing now, this first one where I'm in state one, that dies out and I'm stuck. So, this has no uh successors.

10:23 Whereas the state zero gives me the same two I had previously. I can go to state one or stay. So I'm still in states zero and one. If I read a B now, then this state one brings me to state two. But I could have also stayed in state zero from being in zero.

10:41 So after this I'm in states zero and two simultaneously. If from this I read another A, from state two I get to three and from state zero I get to either state zero again or state one. So now I'm I'm split rice and you can see how this keeps going. Maybe in each step you take all the possible edges from all the possible states you can be in. If there's any way for you to reach some configuration where state seven is a possibility then there was some way in the past at some point you took the right turn that led you to the accepting state and that means the overall computation is accepting in this case that means I've seen the pattern starting seven characters ago and at that time one of the options was to follow the path so you could have I said um I I don't need to do any fancy construction. I just take my pattern write it as the edges on these uh on these states with numbers and in each time step I just simulate what I can have done what I could have done all possible options.

11:58 Uh while this is possible um keeping track of this set of states makes things a bit more expensive and we actually don't need that. we can do uh all that that happens here. We can pre-process that and that speeds up the computation.

12:15 Now you could say fine what I'm actually doing here is turning a nondeterministic finite automaton into deterministic one and there's a general algorithm that does that for any such automaton. uh but as our practitioner rightly objects that has exponential blow up in the number of states at least in the worst case and so uh that doesn't sound appealing but it turns out here in this specific case for the specific types of non-deterministic automata that we have it can never happen you never get this exponential blowup indeed you don't get any extra states at all that's what's behind the canmor algorithm. It's a sequence of insights uh that I that I um attribute here to them that lead to their final algorithm. And the first one is that we we can do this this construction for the special automaton uh much more efficiently.

13:15 Um one way to say it is that we can construct this automaton uh inductively. What's missing from if you compare this one to the previous string matching automaton here is all the other edges. Uh the edges here along the path are the same. But then if I'm not seeing the next character of the pattern, I have to do something and I have to do the right something. If I'm just pointing these all back to zero, I might miss some occurrences. So I have to point these arrows in the right way. Uh and that's the part that we still have to do.

13:54 And for that you can assume you construct this auto atom on step by step making uh the pattern one character longer in each in each step. That means adding a new state J + one. The new accepting state the edge that leads into this one is predetermined. That's the J + one character in the pattern. But for the previous state, there used to be this ch state J that used to be the accepting state before the pattern grew that now loses its state as an accepting state. And it needs to get these extra edges that go back. So we need to find out where these go. Um in the formal notation for automata we write delta as a function that gives for uh a current state and the next symbol that we read in the text the next target state. That's the uh end points of these arcs in the diagram. That's what we have to compute.

14:55 Um and it turns out you can inductively do this. All that you need to compute the target of this delta is already in the automaton that you constructed. And so you can use you can bootstrap the automaton uh to find where you have to go. Um uh for this part um so there's uh an intuitive version.

15:30 Let me let me maybe uh go back to the example to sketch this. Here's our example automaton. And the interesting bits are for example um when I'm in state five here and I'm I'm now asking where should I go with this edge that has a B.

15:53 Okay. Now we know the answer is we go to four. What five means is that I've seen from the text something and then a beginning of the of the pattern. Namely, I've seen five characters of the pattern aba. Let's maybe put this explicitly on top. And now the scenario with my uh arc here is the next character I'm seeing is another B.

16:32 And this is a mismatch. The next character I would have wanted to see in the pattern is a C, not a B. Now the next the target state I have to go to is the longest prefix of the pattern that I can bring in alignment with these characters from the text that I've seen. And so what intuitively you want to do is shift the pattern to the right one step at a time until it matches. Shifting it one step to the right would mean I'm putting this in alignment. Uh we m we made it so that not any single character matches. So that doesn't work. If I shift one more though.

17:40 No. If I shift two positions, then a b a b all matches. The length of this pattern of this prefix of the pattern that I found here. That's the same as p 04.

17:56 It's the first four characters of the pattern, which means I should go to state four if I read a b from state five. Okay. Uh that's that's the intuition behind where we should go. Now another way to arrive at that same target of the arc is to to start at the automaton at the beginning and simulate where it ends up if I read the text that starts there because that's by definition what the automaton should do. Now if I do this starting at A, I know where it ends up namely in state five. uh up to the B I mean up to this point. I know where it ends up in state five because that's where we started from. So how can I get the automaton to simulate where something where it ends up in state four? I don't know how far I have to shift the pattern. But I can just omit the first character and start reading B A B A in the automaton. And that will magically get get me to essentially where I need to go. So I go B A B A. And from there I can read another B.

19:14 And that brings me to state four which is the target of my arrow. So we get the same answer. is four. That's also reading in the automaton from state zero with the same pattern P1 up to five followed by a B. And P1 means I'm leaving off the first character.

19:47 And so what I mean by this delta here is just uh you start at state zero and then you consecutively read these characters and follow the transitions.

19:55 So all I need to produce these new arcs is to simulate the automaton that I'm currently building. That sounds potentially dangerous because it might use the edges that I'm just defining now. Right? So uh it it sounds like this could be a problem.

20:18 But it is not a problem if you build the automaton from left to right because then you can you can work out that the arcs that you're using in the simulation where you leave off the first character that can only be using parts of the automaton that you've already constructed the previous step. So in particular here um it's entirely contained in this automaton just for the first J characters or J minus one there's always this offset I think AJ has J minus one characters correct uh because it leads to state J uh ah this is is the index shift is always a nightmare. Um, that's the new automaton. AJ A + one leads to state J. So I guess it has the same number of characters. Okay, so up to state J. Uh, but the arcs are only computed up to state J minus one. Last one doesn't have outgoing arcs.

21:31 But the the main point is the length of the longest prefix that I could possibly see is always one shorter and so it's always part of the automaton that I've computed already.

21:50 That means we can get all the transitions by simulating the automaton on the long one shorter prefix. But it sounds like this is expensive because you always have to run the automaton from the beginning. Again, my example would have been if we're currently looking to build the transitions from five. So, we're only seeing this prefix of the automaton. We don't know where these go yet. Now, I'm I'm trying to add the state six and the edges out of five. I've added the edge for B. Let's do the transition for A just to be sure that we understand the pattern. We've seen B A A B A B A. But now when we're seeing another A, what we have to do is uh read from the beginning in the automaton starting without the first character. So B A B A A. We do that from here. It's B A B A A A A. So we go to state one and that's where the arc from five also goes.

23:05 Now this sounds like each time for every arc I have to start from the beginning and walk for potentially up to M characters. That sounds expensive.

23:21 That's what this alludes to. That's the number of edges from every state. the sigma the outgoing edges and each seems to require simulating the automaton.

23:30 But it turns out that's also not needed. The second insight that these uh gentlemen had was that these simulations share a lot. Uh I don't know if uh the way I quickly showed it in the example maybe was was too quick to see it but it's clear if you always start you always have this uh P1 up to J followed by one other character this prefix will always be the same because the automaton is deterministic. It has to do the same thing on the first J characters and is only the last character that leads from there to a slightly different state. So we can very efficiently compute this automaton. Uh here's a very simple um uh piece of code that does this. Um let's illustrate this while also trying to do uh the intuitive version.

24:25 We start with state zero. That's a zero with one circle, not a double circle. Uh there's nothing to do in that state. So then we add one more state one.

24:38 with the first character a and there's no the zero always has some arcs back to itself with everything but a then uh let's add another state the two with a b now from state one I need outgoing arcs for anything but b okay I'm in this situation I've read uh an A. That's why I'm in state one. And now I could instead of a B either see a C or another A. That's the two cases. Let's handle them together. Then I'll just simulate the automaton on the one shorter prefix. So I'm starting in state zero and I well one shorter prefix is just this single character A or C. If I have an A, I'm going to state one. So the outgoing arc from one with an A should be one. Again, if I have C, a C, then I stay in state zero. And nothing happens here. Okay, state zero, uh, I can also fill that in with an A, we go to one, and otherwise we stay in zero.

25:53 Uh, if I'm in state one with a B, then I go to state two. Okay, let's do one more. So state three, we go there with an A. That's the match edge for the third character in the pattern. But now we also need the edges from two. I didn't draw these. So there's a loop with A and I go back with C. Now uh I've added this new state three. That means I've seen AB uh up to state two. Now, if I am in state two and don't see an A, I don't know yet what to do. So, let's see what I do if I see a B or a C. Again, get rid of the first character and do the simulation. We start in zero. We do one B. That keeps us in state zero. Now, from state zero, I can do a B or a C. A B and a C both keeps me in state zero. Okay, not much happens.

27:00 Next state bit more speed space is another B and three goes back to zero with A and C I'm adding state four. So I need the outgoing arcs of state three.

27:35 State three means I've just seen aba. Now if I see a b, I know where to go. If I don't see a b, then I could either have another a or a c. Where does that lead me to? Well, get rid of the first character. Do b a. And then an a keeps me in state one. and a C keeps me brings me back to zero.

28:06 Okay, so you see how this goes. Now in this case that was the slow algorithm where I each time started simulating the algorithm from scratch. Now observe I could have omitted that by remembering where I left off in the previous step. What do I mean by that? Um let's let's start again with um adding the arcs for state two. Uh I added the arcs for state two by reading a single B that brought me to state zero.

28:37 So I I remember this is where I was. And then for state two I had to read where um So again I'm trying to construct the outgoing arcs for state two. I do that by reading a B in the automaton. That brings me to this state where I have to take the last edge from and then both B and C from X stay in state zero. That's why from two I have two zeros here. Now if I go to the next state meaning I want to construct the outgoing arcs of state three. I would run the automaton on the prefix without the first character. So on B and A. But I already know where B led me to, namely X. So I can just keep X and update that one step. So if I go with X where it brings me when I read an A from here, then X is now this state, the outgoing edges from three are wherever I go from X. If I read the other characters A or C and A brings me back to uh state one. So with an A from three, I go to here and a C from here brings me back to zero. So I'm joining this long edge back with a C.

30:10 Now the cleverness of this is that I just need to remember where I left off and do one update step instead of starting from scratch all over each time. And that's also what's the what this algorithm does. uh you can formulate it is as essentially copying uh a row of a column of this transition matrix.

30:38 Okay, so far so good. Uh it's always it's always a bit confusing with the index shifts etc. Um but if you meticulously follow the simulation, it's always working out.

30:49 It's just a bit slow. So here's the example worked out. if you want to double check. Uh the way I'm the reason I'm not spending more effort more more time on on this specific code is that this is not the final solution yet. Um as a intermediate summary, this does work well. In particular, once you've built the automaton, the matching feeding the text through this automaton is very efficient. For each character in the text, you just follow one arc. uh building the automaton with this fancy algorithm is taking as much time as it needs to write down the matrix. So that's clearly best possible because the the object you construct has that many edges. So you need that time to write it down. So the total time is is this for string matching which is already fairly good. Uh the downside mainly is if the alphabet is really big this might be wasteful both in space and time.

31:52 For the bionformatics application, you could say there's not much to worry about here. Our alphabet is either four or maybe 20 characters. Yeah. Factor 20 in space maybe is okay. A factor 20 in time. Okay. What ran an hour now runs runs a day. H but fine. Maybe is okay.