Video 6-8: §6.7 Linear-time suffix sorting -- DC3 recursion

0:00 Intro

0:03 In the next quick subsection, we'll put this together. We've seen the step two and step three and how they run in linear time of the DC3 algorithm. Um but there's some fix-up that we have to do. So that's what I just said. Um Unfortunately, in step one, where we said we just recurse on all those suffixes that start at a position that's not a multiple of three. We kind of cheated. Because this is not really an instance of the same problem. The problem we're solving is here's a string, sort its suffixes, all of them.

0:15 DC3/ Skew algorithm - Fix recursive call

0:44 Uh and now I'm telling you use this algorithm recursively for sorting a subset of those suffixes. That's not the same question, right? It's not giving you one string for which you sort all its suffixes. Oof. So, what can we do now? Uh no need to despair because the subset that we're recursing on has a specific structure. It's very regular. It takes every substring that starts at a certain position modulo three. So, we just have to come up with a creative way to make the recursion skip these other suffixes. If you think about it, um maybe you can come up with this one. The trick is to blow up the alphabet. Instead of taking the characters as they are, we treat triples of characters as one. I'll just draw those by drawing a box around them, but you should really think of them as one character, right? It's just a fancy way of drawing a complicated thing and claiming it is one character.

1:52 Uh for the computer, the characters are just numbers, so it's a little less awkward for a computer. So, here's our example, the short one. Instead of looking at the nanaban, you look at this string of four characters, the first of which is ban. The second of which is anna, and the third of which is is ban again. And the last is the triple dollar. So, uh we can take the suffixes of this of this T boxed where you pair characters up in in triples. Um and that would give you exactly the suffixes that started at a multiple of three. So, the suffixes of this one of this string, that's exactly the strings that's the sub the suffixes of this string T boxed, that's exactly the suffixes of the original text that started at multiples of three. So, that's great, but that's not quite what we needed. What we need is R12. We need those that don't start at a multiple of three.

2:53 But, a slight twist to this construction still works. So, you take your string, um but you start at the first at at index one, you delete the first character, and then apply this boxing operation. And then you append the string another time, but you leave off the first two characters, and then do the boxing. So, in in this string, all the boxes start at one modulo three. In this string, all the boxes start at two modulo three. So, if you take those two together, the suffixes of this text T prime, those are exactly the suffixes that start at one or two modulo three.

3:40 Um I think I have a bigger example for that on the next slide. Uh but that's pretty much the idea. We construct a new string that has a different alphabet, which just magically happens to delete the suffixes we didn't like. That we don't want to recurse on.

4:00 DC3/ Skew algorithm - Fix alphabet explosion

4:03 Before we come to the example, there is another problem that we've just created through this. And that problem has to do with um an assumption that we later later make. So so far if I compute this new alphabet the alphabet uh cubes in size each time because I take triples. I need all the combinations sigma times sigma times sigma many combinations for characters now. That by itself is fine for a while, but then remember in step in step two we used counting sort for sorting this this list uh of of pairs. And counting sort is only then linear time if the numbers are in range uh one to n or roughly the range as long as the list is. So if we keep cubing the alphabet very quickly the alphabet size will be much bigger than the number of strings we're sorting and so we can't use counting sort anymore.

5:12 Uh luckily there's uh another fix for this which makes the algorithm a little more uh contrived but solves this eventually. If we have a string of length 2/3 n as something maybe best illustrated here. Uh how long is this text T prime in terms of the number of characters? It's two times T roughly, right? We chop off some characters, but let's not be too strict. Um and maybe plus two for these dollars just to make sure that nothing overlaps. So, it has it's twice as long as T, but then we divide by three because we're counting the number of characters, and now we boxed three characters into one character. So, this this text T prime has roughly length 2/3 of N.

5:29 DC3 / Skew algorithm - Fix recursive call

6:11 And so, if it has length 2/3 of N, it can't possibly have more different characters than 2/3 N. So, instead of using those as they are, we rank reduce them, which means we sort all the occurring triples, and then replace them by their rank. Um and for that, I have an example here. So, uh the important point is, if you do this, you never have more characters than this the string is long. And that means we can keep sigma small, below N.

6:34 DC3 / Skew algorithm - Fix alphabet explosion

6:49 DC3/ Skew algorithm - Step 3. Example

6:51 So, here's an example that shows these uh these transformations um together. That's um the construction again for T prime. Here's our original text. Um and here's the text when you start uh at position two. So, here I left off the first one. That's just the construction, right? We we delete this first character, and then we pair things up in triples. And yeah, at the end we fill with dollars as needed. Uh and then for the second that second part, we left off the first two characters, pair up in triples, and fill up with dollars as needed. Okay?

7:33 So, that's our T prime in this example. Now, uh there's a few duplicate triples. Um not so many in this case because well, it happens to be that there's just these two that occur twice. But in principle, it could be more.

7:54 And so, we can take these triples and sort them lexicographically as as little strings. That's what I've done in this table. This is the smallest. Dollar comes before everything. And then these are just sorted lexicographically. Now, that again, sorting strings sounds dangerous. But it's strings of length three. So again, we can do this with counting sort because the old alphabet is small, smaller than n. So we can do a round for the last character, another round for the middle character, and a round for the first character. Three rounds of counting sorts and we have sorted these strings of length three. That is still linear time. And after we sorted them, we replace each uh triple with its position in the sorted list. That's the same as its rank.

8:45 So we go from this text T prime copied from above and replace each character triple with the rank in this table. So for example, if you look at ban that occurs here. Hence, instead of ban, we now have the character 05. And again, think of these uh these numbers, uh they're boxed and and drawn as characters, but they're really just numbers. It's uh you can say it's is an integer alphabet.

9:18 Suffix array - Discussion

9:20 Yeah, that's the end of this algorithm. That is finally all the missing pieces. Um if you kept following this, uh I guess five times I said, "Hold on, there's something missing here." And hold on, we cheated there. Uh this is the end. We we resolved all of these problems. Uh which may not be obvious after maybe not seeing the first things at the pace I threw them at you. Uh but I promise that's it. So, let's let's have a look at what what we've done. Uh remember again the algorithm it recurses on the the 2/3 only. That's why it's overall linear. And the second and third step, reducing the ranks of the ones that started multiples of three, and then merging the two lists, it was all linear. So, the overall running time is linear. And that's even true if the string has a large alphabet. It can be uh all different characters. Can be an integer alphabet.

10:18 So, what have we achieved? Uh we have reduced the fairly fat suffix tree to something that is is much uh more lightweight. The suffix array is just a list of numbers. We found um for random, so I should add this.

10:43 we can use a fairly simple algorithm that's also easy to code, this fat pivot uh um string quick sort that runs in in roughly n log n time. Uh but if you need um then it's doable in worst case linear time. And there are implementations of this algorithm around. It's um it looks it looks tough to do all the steps right, but and if you spell it out in code, it's surprisingly short and elegant. Because all you really need is integer sorting.

11:14 Um So, what what can we do with the suffix array? We can construct it efficiently, and we can do uh pattern matching, for example. We can use this binary search to find the occurrences of a pattern in a in a long text. Uh there's a few things that are not yet perfect. Uh one of them is string matching takes m times log n time as I've shown you because of the binary search. Whereas suffix trees could do it in in time linear in the pattern length. Uh there's some things that we could do with suffix trees quite easily that don't seem possible right now. Um but that's something we'll quickly tackle after the break.