Video 8-8: §8.7 Linear-time suffix sorting -- DC3 algorithm

0:00 Refining the recursive step

0:02 At this point it feels like we've solved step two and step three both in linear time, so we should be done. Unfortunately, there's a a little thing I'd glossed over. So, for the overall algorithm we're have to uh pay a pay one attention a little bit of attention to step one again. So, what we've done so far is step two and step three can indeed be done in in worst-case linear time.

0:32 So, uh in step one, all we should really need is recurse. But, if you look at close if you look closely at what we've done there, uh I cheated a bit. In this first step, I said, "Let's recurse on all the ranks um that are not a multiple of three." But, uh I can't just take an arbitrary subset of indices and claim that's again a problem of the same form. The overall problem was, "Here's a string, sort its suffixes." Or more specifically, "Here's the string, give me the rank array that tells me for each suffix its rank." That was the original problem. That's what we're solving. But, now I'm trying to call the algorithm recursively on "Here's a string, take all the indices at uh take all the indices not a multiple of three and sort those." That's not quite the same.

1:33 Constructing string triples

1:36 To do that recursively, we would need a string some string T prime that's uh if I call the problem recursively on that string, would give me exactly uh the ranks I need. So, we need a string that somehow skips suffixes. If that sounds odd, um uh I mean you need to modify the string to make that work. And luckily, there's a a relatively simple trick to make that work. Instead of taking the original alphabet, we form triples of triplets of characters. Uh, we've seen that kind of notation before in the compression unit. So, all that means is I'm blowing up my alphabet. Instead of having all the letters that I had before, I now have all triples of possible characters in principle.

2:26 And um, I'm transforming my string by grouping characters in in these in these triples. So, if my original string was this, my new string T box is always three characters boxed together. So, in particular, I would write that the length of T box, the number of characters here is just four, right? There's four boxes. But there's stuff inside the box is kind of hidden in the definition of the alphabet.

2:59 Now, the main trick is if you take the suffixes of T box, these are exactly the suffixes that start at 0 3 6 9, so on. All the suffixes that start at multiples of three.

3:13 Okay, that's kind of the opposite of what we wanted. We wanted to have all those that don't start at a multiple of three. Uh, but that you can get by just shifting things a bit around. So, our actual T prime is not T box, but it's leaving off the first character of T and making the boxing construction on that. Make some some dollar boxes in between to make sure we separate things. And then you take the first two characters away from T and apply the boxing construction, and you append all that. And the result of that, I'll show you an example on the next slide. The result of that is that all the suffixes of this T prime are the suffixes of T that start not at a multiple of of three. It's a little bit of a a sneaky trick, but um by modifying the alphabets, you can indeed give the algorithm a different string on a different alphabet that looks quite different from the string you started with, but it solves the problem that you that you need to be solved.

3:24 Example of T prime

4:21 And then it's a proper recursion. Um let me see if I can do Okay, let me let me jump over this and first show the example just briefly. So, here's our original text, same as before. What I need is the first character chopped off, so I I removed the H. And then in the second part, I removed the first two characters. And then I apply the boxing construction to those. Okay? And I was generous enough I If there's if there's a box that has not enough characters, we'll just fill it up with dollars whenever needed. So, that's the construction. That would be our T prime. Now, if you were quick enough to read, I again uh cheated a little bit. But again, we can fix it. So, um by by this by this trick with boxing things up, we created a new problem. And the problem is that the alphabet size explodes now. If I start with 26 characters in the first step, some some Latin alphabet, in the recursive call, I make triples of that. So, that's 23 cubed.

5:09 Alphabet explosion problem

5:40 Uh I don't even know from the top of my head what that is, but it's a thousand It's more than a thousand, right? Um And if you go one step further, then you take 1,000 cubed. And uh that's a billion. And then one more step, you take a billion cubed, and then uh that's the end of the story, right? So, it's exponential growth is not good, especially if it's uh cubed each time. Um that's even worse than as well. Uh it's it's pretty dire. So, uh that wouldn't work. Now, the solution is that uh well, the the algorithmic way it breaks, um apart from needing space to store those, uh the linear time sorting step doesn't work anymore. Remember step two started out with taking the suffixes of just take the first character, then append the rank, and then sort that. And we said, "Ah, that can be done in linear time with counting sort because that first column is just a single character."

6:49 But now my characters are actually blown up triples of triples of triples of characters, so they're entire long strings. And so, the whole linear time sorting uh breaks apart at that point. Okay.

7:03 Alphabet and rank reduction

7:06 Now, of course, um our actual string doesn't really get bigger. Uh so, if we had this this 24 characters in the original string, we don't magically make up new characters. Uh and in particular, because this T' prime has roughly length 2/3 of n in numbers of characters, uh there can be at most so many different triples that occur in that string. There's just not enough enough space to have all of those triple the triples that are possible. So, instead of using these nice boxes that I've drawn for you, we replace those by numbers. And for that, um this is called a an alphabet reduction or rank reduction. So, what we do is we sort all the triples that actually occur in our string. And I replace them by their rank. So, we compress the alphabet down to all the characters that really occur in the string as opposed to having space for all possible triples.

8:08 Now, that sorting step can be done in in linear time by three rounds of counting sort. So, no cheating involved here. And this means that the alphabet size never grows beyond the length of the string. We never have a character that doesn't occur, so we never have more than n characters.

8:31 So, let's do that on the on the example. Here's the the triplet representation. The triples that actually occur in that string are almost the same. There's just one that's repeated. But that is um because the example is fairly small and has a large alphabet. If you have a longer text, then necessarily you will have many more triples that are repeated. But here's here's all that occur. We sort those. So, in alphabetic order they're listed here, and they all have a rank. And this is the very same trick we've had before in in in disguise. And so, we replace every triplet by its rank. And again, you should uh you should treat this as one number, um not as a string of decimal digits, but uh in the standard way, uh an array of numbers. So, the real string we recurse on is T double prime, which is obtained from this boxing construction and then replace every every character by its rank.

9:23 Conclusion and takeaways

9:38 And with that, uh indeed, all the all the cheats have been resolved. Uh we've reduced it to a proper recursion. It is now exactly the same problem we had before, a single string over a reasonably sized alphabet. So, recursively the same same running times hold. And the rest of the algorithm is as I showed you.

10:01 So, to discuss some what we've achieved, uh we found that we can compute this suffix array in linear time, and the algorithm is a bit intricate, but it's actually very little code. If you code this up, it's not much. You need some counting sort, and you need a little bit of operations to produce these triples. Uh but it's all just arrays and sorting. Both can be uh in little code and and fast in practice. Um if you don't want to go that far, the uh fat pivot uh string quick sort is also uh relatively quick for many arrays from from many texts, and is much easier to code. And we can use this uh to do string text indexing or string matching in in a very good time, just logarithmic in the length of the text. Uh only slightly slower than what the suffix trees uh gave us. But it is slower. So, at least from the theoretical perspective, you might not be 100% happy yet.

11:06 Uh and what's more, there's a lot of things I tried to show you different applications of suffix trees to prove their versatility. They can be used for many different string problems. And uh so far, we can't really use that full power.

11:22 So, that's so far that's a a disadvantage of of using suffix arrays.