Video 6-7: DC3 suffix array construction: induced sorting and merging

0:04 In the next section, I'll show you this uh promised algorithm for sorting the suffixes of a string in total linear time. It'll take us a little bit to get there because uh it's a very clever algorithm that has a few a few tiny steps um to get through. Each individual step, I think, is is fairly fundamental or elementary. Uh but the way they work together is is beautiful. Uh so it's split spread out over a few sections. Uh to start um we need one extra notation or one extra object that we haven't used yet which is the inverse suffix array. Uh remember the suffix array I denoted by L for leaf because it's the leaves of the suffix tree in left to right order if you order uh the edges at every node in alphabetic order. Um, and then the opposite of of the leaf array is the rank array. Uh, but you can also remember it by going left and going right. That's what this this picture is supposed to help you just remember the syntax. Uh, this is not so standard.

1:11 People usually call the suffix array SA and then this the inverse suffix array SA exponent minus one or something of that sort. I could never remember which one was which. I found it very annoying. So instead I'm using L for leaf array because I can remember that the leaves in a suffix tree have the starting index as the value and the uh suffix array as well has the starting index of the suffixes as the value and the position is the lexographic order.

1:44 Um the inverse is the rank of a certain string. If you have a starting position as an index, then the rank array tells you how many other suffixes are smaller in lexographic order. Uh that's there's many different ways to say the same thing and they're written down here. uh you can define it as the inverse permutation by having the index and the value flipped as it's as it's shown here or it's the number of the rank array has uh number of suffixes smaller uh base zero. Uh the other option to remember this uh which I find visually most most sticky so I'm going to spend a minute explaining it. It's natural that you start with the text and just write down all the suffixes. That's my postulation. And so you write them down in the text order by starting index. Then you get this nice triangle shape. And on the right you have the same strings but now in sorted order lexographic.

2:48 And then here what you have is going down the rank in sorted order. And what you don't know is the index. That's the leaf array. And on the right, on the left you have the the rank array. Now this going left and going right means if you have an index here, you know where the string starts and you'd like to know where it is in the sorted order, you take the R array, you want to go right and it tells you ah this is at index six in the sorted order. And vice versa, if you have a string where you know uh it's the penultimate in the sorted order, index 8 or rank eight, the leave array tells you where this guy starts. Okay, going left. U maybe it helps you to memorize this. Um if not, you just have to scroll back.

3:43 So with that, um let's tackle the actual algorithm to compute the sorted suffixes. And it turns out it's more convenient to compute the rank array and not the leaf array directly or the suffix array. But as this picture hopefully and this this definition shows, if you have one, you can compute the other in linear time by just going through a loop and setting uh going through loop of i and setting i at the position of r. It's a inverse permutation. So we can compute either of the two whatever is more convenient. And here we'll compute the rank array.

4:22 The algorithm um now there's several algorithms. I'm presenting just one. It's called DC3 or the skew algorithm. DC stands for difference cover. And the three means there's other alternatives. You can forget about that. Just wanted to mention why there's this weird name. And it does an awkward thing. It first recursively computes uh some of the ranks namely for all of the starting positions in the text that are not at a multiple of three. So for 2/3 of the input, you compute recursively what the solution should be. And then you use what you've computed to infer for the other third the sorted order or the the rank array to be specific. And finally you merge those two to get the sorted order for the overall list of suffixes. We'll keep um moving between these two worlds having um indices of a certain type and thinking of them as the strings that we sort. So this merging step you should think of just the rank arrays give you um the sorted orders of these suffixes. So of course you can merge them in essentially the standard way.

5:35 Uh whereas for this second step we exploit a bit more crucially that we're talking about suffixes and uh for the cost for the merge we'll have to look at this carefully as well. Uh before um we look further into how to do all this let's try to analyze the result. And here I'm just going to over reference that steps two and three will take linear time each. And then uh standard masters theorem if you have total cost linear in the first step then recurse on 2/3 is a geometric series. So the total cost is also linear because you get rid of a constant fraction of the input in each step. So if we can do all that we're good then we have a linear time algorithm to compute the the rank array and from that we can compute the leave array the suffix array [snorts] let's look at the second step first uh we'll come back to the first step conceptually it's just recursion so that's easy right where we have to do the actual work is in the conquer step And um it's uh the second step says we've recursively computed the sorted order of all those suffixes that start at indices that are not a multiple of three. So the one two stands for the the remainder by division of three of the starting index. That's these guys.

7:10 And u knowing their ranks, we want to sort the suffixes that do start at a multiple of three. Uh how could we do that? and in linear time please. Well, for that we clearly have to compare these uh these suffixes that start at uh say position zero and three all all the multiples of three. We could do that compare characterize but that might be too expensive if they share a lot of uh common characters. Also, we still need to kind of sort uh just using a a blackbox sorting algorithm wouldn't work either. Um but they're strings and you can compare them. So if you start doing that, you compare the first character. There's two cases. Either the first character already decides who is smaller or it doesn't in which case it has to be equal. Then you have to look at the following characters. But the following characters after T0, the suffix that starts at the beginning, that's the suffix starting at one. And same for T3.

8:16 uh if you remove the first character, you add T4, the suffix starting at position 4. And for those two, these are both in R12. So for those two guys, you already know the rank or how they compare, you can look up the rank and compare the ranks instead of the actual strings. So instead of comparing potentially many characters, you compare a single integer. Also, we recursively computed this and its suffixes terminated by a dollar. So this this there can't be ties. There will always be a definite outcome strictly less strictly greater.

8:51 Uh these two together we can combine into a single check by saying we're comparing pairs of uh a character and an integer. Right? The first is one character of the string and the second is is one rank. And we compare these pairs in lexographic order. And that's the same as comparing these suffixes. Okay, now this this is actually easy to do. Um let me show you in an example what this looks. Uh but already at this level we're sorting pairs where both components are of a small and fixed size and integers. Let's say the characters are integers as well. So of course we can use counting sword or radic sword for that.

9:46 uh as a concrete example just because it prepared it anyways. Uh here's the long text. Here are the recursive call sorts all the suffixes that start at not a multiple of three. And technically what it gives you is this rank array that tells you for every starting position um the number of suffixes that are smaller. I wrote them down here in in sorted order, but of course I guess you can you can imagine what this looks like. And here are the suffixes that have a multiple of three as the starting index which we want to sort now. So we take their first character and then replace all the rest with the rank of what's left which in each case is just the suffix starting one character later. And that's all always one where we have computed the rank already. Okay. So instead of dealing with this to sort, we're dealing with this to sort. And with two rounds of counting sort, we can do this in linear time.

10:49 Linear in the number of guys here, which is certainly O of N in total. And that's our rank array for all the suffixes that start at a position modulo 3 equals zero. That's step two, which um created from this 2/3 list, the 1/3 list. Next, we have to merge um we're given the two sorted inputs as runs and um try to produce the merged result. And as you may imagine, we can try to do a similar trick as as we did now. We uh look at maybe a few characters at the beginning and hope that the rest can be settled by doing an integer comparison.

11:41 What we're doing is essentially the standard merge method which already is linear time if every comparison takes constant time. And uh we have to use what we've premputed to speed up these comparisons. But let's let's just start in the example and see what happens. Suppose we've already merged uh a few of these uh suffixes. Now that means we're sitting here and here, right? So the question now is is T15 or T11 smaller? And of course you could look at it and just take the string, but uh let's pretend we're an algorithm and can't. So here are the two suffixes. we split off the first character and are left with some slightly shorter suffix in both cases. But if we do that here uh we turn the green suffix one from the guys here with multiple of three index into a blue one and vice versa. So uh we can't directly compare their ranks because I guess this is maybe a subtlety I didn't point out. uh the ranks here in in R12 and in R0 these are local relative to this collection of the data they go from 0 to 14 here and from 0 to 7 here. So if you take numbers one from here and one from here, they have no meaning, right? So that doesn't work.

13:08 And so it seems that trick fails. H uh but luckily if you just go on one more step, it works. By splitting off uh a second character, you always end up with two blue guys. Now you could you could analyze a bit more clearly uh a bit more generally what you need for this to happen and that's exactly where the difference covers come in. You need some structure of uh separating the starting indices so that when you split off a constant number of characters at the beginning you always end up with something that's in the same in the same set.

13:49 one option is the the chosen and I'll leave it with that but that's um one way to generalize the algorithm. So again, the trick is you're trying to compare something where you don't exactly know and you can't use the rank arrays directly. But if you split off either one or two characters, and this depends on what the starting index is, you're guaranteed to find two blue suffixes for which you do have the ranks and then it stops.

14:25 So in this case um you need two but uh that's already the worst case. In either case the comparison you need in every step of the merge can be decided in constant time after checking one or two characters and one rank. Oh at most that so you can also do merge in linear time and that means we've completed step two and step three in linear time. So all good.