Video 6-8: DC 3 suffix array construction: final algorithm

0:04 Now what's left to say is uh that oops we cheated a bit at least conceptually. Um there's different ways to solve this but I think um the narrative here um makes this very clear. Uh if you if you remember what the algorithm said it said recursively sort the suffixes that start at these indices not a multiple of three R12. But what does that mean? recurs on what like we can't just take a subset of strings and pretend that that's the same problem. It's not right. Uh so we somehow have to make it the same problem if you want to stay close to the original formulation. And indeed that is possible. You can you can make it work by constructing a specific string t prime that's constructed from t so that you can recurse on that string and you magically compute the right number or the right uh answer. So we want this uh a string t prime that lets us skip certain indices in the starting positions for suffixes.

1:13 Well, to do that, uh, we just bunch characters together and treat them as a single character. And in this case, what you have to do because you're essentially doing everything modulo 3 is, uh, consider triples of characters. So, instead of of this input string, um, tbox the the tripled string is just taking these first three and pretending that's one character. It's one u item.

1:41 And then of course the suffixes of of t box are precisely ignoring the box boundaries then are precisely the suffixes that start at uh multiples of three. Now this is not exactly what we wanted, right? We wanted the ones that don't start at multiples of three. But you can tweak this idea a bit. You take the ones uh that start uh at a multiple of 3 + 1 and a multiple of 3 + 2. So you concatenate two of these strings. Uh and that's our T prime. Then uh these the suffixes of this guy if you ignore the boxes are precisely the suffixes of the original text where the modulo 3 is one or two. So we can construct this string and then recursively can sort the suffixes of this string which because we only return a rank array only the integers that tell us how many other suffixes are smaller we don't even need to know that we've changed the string right it works uh the same way.

2:46 Good. So that's that's that fixed. But now we created a new problem uh because we accubed the size of the alphabet in each recursive call and that you can only do for a few times before it gets so big that you can no longer use counting sort at least in the simple way, right? Um what what we did to sort um at least in in uh in step two for the induced sorting step we needed that we can do a round of of counting sort on individual characters in the recursive call. These get bigger and bigger. So we need space proportional to the size of the alphabet. That's going to blow up. Okay. So we need to fix that as well. But luckily this is uh only um a fake problem if you want because from these triple characters there might be sigma cube different triple characters in existence but we cannot have more different ones in our actual string than our string is long.

3:55 So no matter how big the alphabet our t prime will only contain at most 23 n different such characters. So we can just give them new names as long as these names preserve the lexographic order. That's fine. Again, all we return is the ranks of the suffixes. Nothing with the strings specifically. So we can rename the alphabet and nobody notices it the difference. So we do that. Um and what we do for that is again sorting. We sort the triples. Uh that's again counting sword three rounds and replace every character the triple of three characters by a number which is the rank of that character among all the occurring characters among all the occurren sigma remains less than n in every step and then we do get the same same behavior in the recursive calls and so uh pinky promise that's it there's no more nasty surprises coming up. Here's an example for how to construct this string T prime. Um, that's the text from before. You construct the text where you leave the first two characters off and here you leave the first character off and then break it into blocks. Uh, to make it work nicely, you have to include the right number of dollar signs. But this is uh it's not a big deal.

5:23 Uh then in this small example there's almost all uh occurring triples are unique. There's just this one here Anna that's repeated. Um but fine. So here are the triples in sorted order and then you can replace every triple by its rank.

5:44 [snorts] So again that was the overall algorithm. We spent some time figuring out how to do the second and third step in linear time. And we found even the first step can actually be implemented and it's not causing more trouble but it does cause a bit more effort than it may first look like where you just say ah just do recursively. You do have to construct this um this T t prime and do the renaming of triple characters.

6:21 Now uh if you wanted to use this in practice, there's good libraries available that do suffix sorting. So it's is rarely so so necessary to implement from scratch. Um I want to show a few details of the original paper for for this algorithm how they implemented it just because it's it's a few cute tricks. um these might no longer be uh the most efficient practical solutions, but I think the the description from here there's still a certain gap from there to go to a clever implementation. And so um I'll focus on some of the the nice steps and show them in the most simple possible way. It's not the fastest possible way.

7:08 Um the key components that uh their implementation builds on is a is a clever implementation of counting sort or radic sword. One round of radics sword is what they call it. Um I think we would would say counting sort. Uh it's clear that we need this conceptually because we're doing several rounds of counting sort with specific either characters or then integers later. Uh what they figured out is what you really want is sorting some um some indices. So you're only picking this array A gives you indices in this array V and you're sorting the indices according to what value they have in V which allows you to conveniently specify sorting certain subsequences by just giving the right indices and you don't have to copy out the data you just uh copy out indices. uh k is our what what was sigma before that's the uh the range for the values and we return again an array of the same indices in a so you're sorting the indices in a with respect to the values v maybe it sounds more complicated than it is.

8:29 So first step is counting sort. You count how often each value occurs. That's this part. You take the value of uh the E index and increment that counter.

8:45 Then you do prefix sums of these counters. Then you turn the count by that you turn the counts into the target indices for the sorted order. So this just um computes the cumulative um uh sums of of the counts.

9:03 And then for the sorting we create a new array as output where we put the indices in and then we go through uh the range of values of indices um pick the first and write as many um copies of that into um so we go through the unsorted input and write that value at the right position. What we really write is the index of um of that value into the position in B. And for that we use the count array to know where to write to. And we increment uh that counter to remember that we've already used up one space. So you could you could think of the count array here as simultaneously moving through portions of the index space. And you don't know in which order you increment them because that's given by the input order. But at the end they will all have scanned over their range for the uh value v.

10:18 Okay. Um that's the specific like building block they use. Um and particularly the first step I think they solved really cleverly. Um that's the final algorithm. If you want uh you're given a text, you're outputting the rank array. Um you compute the sizes of the three parts which if you include the proper rounding are a bit annoying, but uh by and large they're equally long. N3.

10:50 Uh initially we start with R12. Um this will eventually be the rank array but you you first initialize it with the indices that are in R12. So it's all the indices that are not a multiple of three. And now you compute uh for the reduction of the alphabet the sorted order of these triple characters. And for that we use this radics pass I just showed. um we sort the integers the the indices that are in R12 but we sort them according to the last of the triple characters that's why here t is offset by two so that you're using the third of the triple characters from the result of that because this radic sword is stable you then go sort these guys according to the second character of the triple and finally the first character of the triple. So after that temp will have all the indices in here in the sorted order according to the triple that starts at that position.

12:01 It's a bit convoluted but uh kind of clever. Right now we have this in sorted order. Now comes the renaming step. You go through all the triple characters and you you check is the current one the same as the previous one. If so, it gets the same name. Otherwise, you increment the name. And then this step is another stroke of genius that you can compute the index where you should write it to from again the modulo 3.

12:33 Now after this you have in R12 the re the new names of the triple characters that started at these positions. And now comes another clever trick. If these triple characters are already unique, there's no duplicates at all. Then these determine the sorted order for the entire suffix because they already fully determine the order. And then they coincide with the rank by pure chance or genius because there start at zero and go up to whatever the number is n12. Right? So then you don't even have to recurse if you're in this lucky case. And that's also the base case. they're kind of both in one. If not, then uh you do have to do the recursive call and then you get the result back. Uh the merging and the induced sorting is actually not so interesting. It's similar to how we did it. So I didn't provide the code. If you want to see their their lovely C implementation which is deceptively short uh and has a few more tricks that I removed then um I mean there's the paper links. Uh I think it's it's impressive at at the very least. Um clever piece of engineering.

13:49 What you should take from it is more on the conceptual level that we do uh the induced sorting and merging step by uh essentially relying on this uh asymmetry between this bigger sub problem that we recurse on and the smaller that we induce from it. Uh that part I think is uh is worth remembering the implementation details as I said this maybe more for for your um for the nerd amusement I don't know all right but we do know how to sort suffixes in linear time now and there's nothing really fancy needed for it is all counting sorts in one way or another nothing uh very complicated else going on [snorts] uh let's let's take a an intermediate um conclusion uh for suffix arrays is as a data structure is just an array of numbers. So that's as plain as it can go. Uh you can have a simple uh for most for most strings you can do a simple string sort and that gets the job done.

15:00 But of course you can also go bull monty and implement the linear time solution. we'll call a library. Uh, and we can do reasonably efficient string matching with this despite having gotten rid of all the tree structure on top. Um, but it's not quite as fast as suffix trees allow you to search, right? At least string matching itself, you need to do um a binary search in the suffix array, but also each comparison takes uh worst case m character comparisons because you may have to compare two strings of length m. Uh so that's that's a good deal worse and we'll work on that in the next chapter a bit. Uh but what's more is suffix trees can do all these wonderful things for string algorithms and that seems lost for now.

15:53 Suffix arrays only give you the sorted order of the suffixes and uh all the other one remember the uh tandem repeats and all so much fun that we had before Christmas. All that seems harder to do with just suffix arrays.