Video 7-1: Range-minimum queries

0:02 In this next unit, we'll move closer to the state-of-the-art for string indexes for large uh texts, in particular bionformatics genomes, and that will build on the suffix trees, but extend them a bit. um to make better use of our LCP array that we've introduced in the previous uh unit, we'll talk about some uh useful black box that first of all may not appear to be directly connected but is is precisely what we need for making better use of LCP arrays and then we'll see some applications of this and at least the ideas of how to reduce the space further in in modern index indexes.

0:50 We've also left open this business of computing longest common extensions and that's been burning under my nails to close. So maybe the same is true for you. Remember what this was? Uh we had a string and LCE queries are given two positions in that text. How many characters do they share? already at the time um we connected it to the suffix tree in the following sense that the longest common extension of two positions in a text is the longest common prefix of two suffixes. So the LCP array seems to be getting towards the answer. Uh but the LCP array only has entries for two adjacent leaves or two adjacent suffixes in sorted order. uh whereas here the LC queries need arbitrary suffixes as input.

1:43 Uh you can still use the suffix tree in in this way that uh longest common extension of of these two if they're not adjacent is still given by the string depth of their lowest common ancestor in the tree. But that means we have to know how to compute lowest common ancestors in a tree which we also haven't covered. So either way, we're kind of running in circles here, but we're connecting things uh making uh making connections between knowledges is probably still useful. And I promised at the time that we can somehow do this um formulated here for the lowest common ancestors in trees. But as you see, it's equivalent uh to here talking about the longest common prefixes of of arbitrary suffix arbitrary suffixes. Um the promise was we can do this in linear time, linear space and then for the pre-processing and then constant time per query for longest longest common extensions or uh LCAS.

2:49 [snorts] To get there, let's look at a different problem and you'll see soon how it connects. Uh but let me first define it. The range minimum query problem is the following innocent task. You're given an array of numbers. Um, and you can look at this array of numbers in a pre-processing step. And then there's a a query phase same as for longest common extensions. Now I'm asking you queries uh a range from i to j. Where in that range is the smallest value in the array? Uh this sounds cute and useless. Why would you uh want to answer these queries? But bear with me for a bit. Um two nitpicks uh will insist on reporting the index of the minimum, not its value. Um because we have the array at query time, we can look up the value if we wanted. That's just a bit more general. And if there's ties, we insist on getting the leftmost position of the minimum.

4:00 Uh that's just to make it make it well defined. Uh neither of these is really critical at this point. Uh but keep that in mind. That's our definition. So as an example in in this array, uh if you look at just the red range, the minimum value is two and the leftmost occurrence of two is at position 10. So 10 is the answer.

4:24 What does that have to do with longest common extensions, longest common prefixes, and lowest common ancestors? Well, everything uh to compute the longest common extension of two positions in the text. In other words, the string depth of the lowest common ancestor of their uh in the suffix tree of the of these two leaves or the longest common prefix of these two suffixes that start at position i and j. You just take the smallest value in the LCP array there.

5:04 Here we really need the value not the index. That's why the result of this RMQ query is wrapped is is put into the LCP array. So we really read the minimum value. Uh so all all this says is you're finding a range in the LCP array and give me the minimum value. And now I'm going to do this dangerous thing of trying to zoom in a bit.

5:33 It's slow. I don't dare to do it faster. uh it's been crashing a few times in other cases. Why is this correct? Uh suppose we want the longest common prefix of these two leaves or in other words the suffixes starting at position five are a band and one are a nanaban. What's the longest common prefix of those? Well, you can look it up from the strings. It's just the single a. But you can also take the two and look at the corresponding range in the LCP array. And if you think about it here in these uh LCP intervals, clearly the lowest dip that you have between these two end points is going to dominate the the answer. If there's uh a shared common prefix between all here all these strings from here to here, it has to be one of those intervals or within one of those intervals. The lowest that we ever reach in between from here to here, that's the answer. And here the minimum is one.

6:46 That's precisely the connection. And so uh if we can answer these range minimum queries on our LCP array, we can compute the longest common prefix of any two suffixes no matter where they are. They don't need to be adjacent. And that also directly solves the longest common extension problem because they're the same thing. Okay. So provided that we have the suffix array, the inverse suffix array, the LCP array already computed, just solving RMQ on top of it solves longest common extensions. That's the final black box that we left open. But again, we shifted things only. We haven't solved the range moon query problem. Uh but I promise you we will. And it's again going to be building on only on things that you've already seen.

7:54 Um, as a little remark, the range minimum query problem is comparison based. So it doesn't necessarily care that the entries are numbers. It could be arbitrary objects that you can uh order. Um also like for the longest common extension problem there's two uh running times plus the space usage and it's uh to have a concise notation let me write P and Q with these angled brackets for the pre-processing time and the query time and any kind of solution will have some combination of these two times. Uh also note that if the pre-processing time is P of N, you don't have enough time to waste more space or fill more space with chunk than P of N. So the space you use is always bounded by P of N as well. We'll be content with that bound uh here. So we don't need a separate notation for that. In practice, um that's a separate concern that you would also want to look at saving more space.

9:03 If you have any RMQ solution with such a quality, then we immediately obtain an LC solution where you have the same same running time provided that the pre-processing is at least linear. The theta class doesn't even change.

9:23 As always with new problems, you should first check what is the most trivial you can do. And the most extreme you can do is either do nothing at pre-processing time and scan the array at query time that corresponds to constant time pre-processing or even zero and linear time worst case for queries. Fine, but not great. Um the other extreme is there's only n squ queries. Let's just premp compute them all. If you do it stupidly then it takes cubic time. If you do it slightly less stupidly you can do it in quatratic time by reusing that you're you're finding the minimum of one range and then you make it one longer. No need to go from scratch and finding the minimum again. Uh but still you're you're paying quadratic time and space for getting constant query time. Maybe we can do a tad better.