Video 7-4: String matching in enhanced suffix arrays

0:03 uh standard suffix arrays could already support some sort of string matching, but it wasn't quite up to speed in comparison with suffix trees. Let me try to remind you a bit. um we can find a pattern in uh a string for which we've computed the suffix array, the leaf array, the uh starting positions of all the suffixes in the alphabetic order. Um where you're doing a binary search. So you have login n plus two in the worst case. Binary search uses that many comparisons. uh checks if you're remember this was the suffix array and then you start in the middle is the pattern that I'm looking for smaller or bigger alphabetically than the suffix in the middle and then you you eventually cut the range in half recursively and so on. So after logarithmically many such questions, you're done. But each of these questions is a string comparison between the pattern and that suffix. And that could go on comparing many characters if they all share very long common prefixes.

1:17 Again, the stupid example of having a text of all a's shows you the worst case here is indeed login for the number of queries times m. each could be scanning the entire pattern. Whereas suffix trees could do uh a lot better assuming that the alphabet is constant or you're doing some some trickery inside the notes. You could even do it in constant time per character of the pattern. That's a far cry from this one. And uh if these enhanced suffix arrays claim to be a replacement for suffix trees, they should be able to do better. and they can and we were missing this last piece the arrangement queries for for a a simple solution um to do that to do better than that. Uh to motivate this um what all we'll have to do is avoid comparing characters where we already know that they're going to be the same. But how if you're forgetting everything in between? Unclear. So we have to remember something and the invariant that um we'll we'll try to remember is is precisely information about the longest common prefix we've seen in previous comparisons.

2:37 So specifically your in your binary search at some point that you have um two bounds that limit the range where p lies. So we have a suffix starting at A and a suffix starting at B that uh sandwich in the pattern in lexographic order and we will remember what was the number of characters the longest common prefix of this suffix starting at A and P and similarly for B that's what we'll maintain also when we keep going in the binary search the the goal will be to avoid doing same character comparisons again. Um, and what we'll use under the hood is that with range min queries, we can bump just the LCP array, these linear extra numbers between adjacent uh, suffixes, we can find the longest common prefix of any two suffixes of the text. So this doesn't directly tell us what the longest come prefix with P is but for any positions in the text we can do it and the answer is precisely the range main query of uh the LCP array in this range and the reason again just graphically speaking if there's some shared common part here it might look like this the characters that are shared from top to bottom are those up until the last one that is on the shortest common prefix in all of those. So that's the minimum in the LCP array.

4:27 Okay, how can we use this? Uh it turns out essentially uh you just do the obvious thing, but there's a few cases. So let me just illustrate it on an example. Here's um our text from Hannah Bance Bananas Man from the suffix uh suffix array example. Uh and I'll I'll cheat a little bit in that the indices for A and B that I'm going to pick are just chosen to illustrate the different cases. They're not really indices that can come up in a binary search because you would always cut things in half. Forgive me for that and just ignore it. Um, imagine the text is even longer and we're just zooming in on some bit. LA again longest common prefix between this upper say here and here.

5:15 There's some some lower bound for the pattern. Uh, and we know how many characters agree between the pattern and this suffix and similar for the upper bound. Immediately we know because this is a range in the suffix tree. These are sorted strings that the longest common prefix between this um tm the middle midpoint that we choose in the binary search and the pattern has to be at least as big as uh the minimum of these two because all the strings between the these two. So we know p lies between those two. All the strings between a and b share these suffixes. actually the uh um the LC the the RMQ of the LCP could be bigger. Uh but the um the pattern shares these characters with A or and B if it's the minimum. So it shares it with all the strings in that range. That's uh that's enough.

6:24 So we know a little bit about LM and people claim in practice you may just stop at this. Um you do the binary search you remember what the longest common prefix from the previous comparisons was and you just skip whatever is the minimum of of these two for the next comparison and keep comparing the characters from there. That's not optimal. So sometimes you do redundant comparisons if you do that. Um, so you can do slightly better and that's where the cases come in. Case one, LA and LB are the same. An example is here. Well, the common prefix between the pattern and the pattern will keep changing in the cases. I'm sorry about that. So here the pattern is Anna and uh we've narrowed it down to this range happens to be all the strings that start with a but that's pure coincidence. So all these strings here share the A as the first letter and so does the pattern. In this case we've maximally used what we know. That's all the knowledge we could extract from LA and LB. So we'll just start at M. This also shares the a. But then we'll start comparing with the next characters and we'll find that n is bigger than a. So uh p has to go this way. The next round of binary searching moves a to m and keeps going.

7:56 Uh note that because we explicitly compare this suffix at M and P, we all also learn the actual value for LM because we stop comparing exactly when we've exhausted the same characters. That was the cleanest case. The other case is well if these are not the same there's two symmetric cases and let's just assume that LA is bigger in if you implement this you'll need a second case where everything is mirrored and this case unfortunately splits into three subcases. All the examples will have the property that there's a longer common prefix between the pattern and A than the pattern and B. Here it's LA is one and LB is zero. Right?

8:53 And on top of that here we have that the longest common prefix between TA and TM. So these two guys here I'm running out of good colors but let me use this light green for that.

9:05 This is bigger than LA. they share more characters than uh P and LA. In that case, you can figure out that because P already disagreed with After here, the first character, the second is larger, we know that it's larger because P has to be bigger than A or at least as big as A and we know they disagree. So bigger than A, bigger than the um suffix starting at A. And we know that M has up to this position at least these uh two letters are the same as in A. So P will still disagree on this second letter and we'll still win over M by the it's just they're the same. We've done the same comparison and we don't have to touch any characters by just comparing the longest common prefix information. We already know what the outcome of this comparison will be. Okay, there's a symmetric case which has almost the same um meaning in this case.

10:13 Uh there's a longest common prefix between the pattern or it's even more right. Um almost found the string but not quite. Um we also have some overlap with B but just two letters. So again, we're still in case two where LA is bigger than LB.

10:40 This is something like seven. This is two. But then we also have the longest common prefix between A and M, which is these three guys here.

10:57 And in this case, uh the green part is shorter than the blue part. Well, what we know is that the pattern agrees with A for a lot of characters and then eventually is bigger. If M shares the same characters here and then is bigger than what A had, it must also be bigger than what P had because they're the same, right? The decision for the comparison is done after looking at the first four characters and the first four characters of P and A are the same. So of course the comparison between M and A and M and P has the same outcome. Again no comparisons of actual characters needed.

11:37 Last case uh pinky promise is is this one where these two are the same and then again we have to do some comparisons. Let me mark down again what is equal.

11:51 So we have um three here and two and now uh the longest common prefix between a and m is also three which means we've maximally exhausted our current knowledge. We can't deduce more about the order where p goes from the prefixes that we looked at. So we have to compare the next characters from here onwards and the next character already decides P is going to be bigger smaller than than M. So it'll have to go here. We report that we didn't find it. Whatever whatever comes after the binary search. Okay.

12:35 Yeah. In all cases you can figure out that you've learned LM. um needs a different argument in the three cases, but you can work it out. And you can go through the cases again and verify that whenever um whenever you're doing a comparison that comes out as equal, that character in P, you're not going to touch again. you're you're not going to uh compare that more than um more than once in one recursive step of the um of the binary search and you'll always make progress. So over the entire binary search you touch all the characters in P a constant time each. That's why the oval search time um is is this m plus login is not exactly equal to the suffix tree time where you could get rid of this plus login but it's uh it's good enough because either I mean login is is fairly small the only real problem previously was if m is relatively big and then in this case m dominates That was essentially the last missing piece in our discussion of enhanced suffix arrays and how they can support the operations of a suffix tree without storing this uh full tree structure. All the other bits we've also filled now with the arrangement queries. And so you've essentially seen how to replace suffix trees entirely just using these array based techniques.

14:12 Okay. Uh what next? We still need for all of this to work the text explicitly written out. We need this in in various places. Um certainly here for the last part you were doing comparisons with certain characters in the text. So you need the text.

14:35 There's the notion um of a self index which is an index on a text that helps us search but doesn't need the text. It's a bit crazy like if a book had only the index and the rest is thrown away. Uh you obviously need to grow the index a bit by that. Then um in a more technical term we we can if we don't have to explicitly store the text so that we can jump to specific characters. We might get away with storing it in compressed space, but still work on it, still searching it.

15:10 And indeed, that's possible. That's that's up next.