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

0:00 Intro

0:04 in the next section I want to show you how to finish off this algorithm because it turns out a lighter bit to you in the last section we're not quite done yet

0:16 DC3/ Skew algorithm - Fix recursive call

0:20 we did manage to get step two and three done in linear time and I was not lying about that part but the recursive call I glossed over this briefly and there was a reason for that uh it doesn't quite match up so that's uh the the recursive sub problem is not quite the same as the original problem in particular uh I asked recursively to compute the ranks of certain substrings certain a certain subset of all the suffixes the same as recursing on some string and finding the rank array of that string right the original problem was here's a string take all that suffixes and sort them and give me the rank array and now I'm asking you to do something like this that's not quite matching the signature of the method so we'll have to work around that the thing is we really like to recurse on a single string because that's what the method can do and what we want is a single string that has only the suffixes starting at not a multiple of three that sounds a bit like a a problem it turns out it's not you can do it uh with the following trick so first of all you take your string and instead of looking at individual characters you

1:45 lump them together into triples so you I I drew this by by putting a box around them but you should really think of ban as one super character that's now a single thing it's one entity a single character in a larger alphabet and same for all the others that's not enough that gives you fewer suffixes now right every suffix by leaving off one more character jumps three characters in the original string so if we take this T box then we get the suffixes starting at multiples of three if we want all the suffixes that don't start the multiples of three you can do this Construction you take the original text without the first character and apply this boxing and then you append afterwards the string where the first two characters are emitted and you apply this boxing Construction

2:43 if you look at the suffix is there that will be all those that started either position one plus a multiple of three or position two plus a multiple of three and that's all that start not at a multiple of three in the original string okay again uh a bit why would you do it exactly like this how do you come up with this uh um I don't have an easy answer for that but it's doable and the construction is is a bit weird but not particularly opaque all that's involved is going to a different alphabet you take triples of characters and treat them as one thing so if we build this this text T Prime we can apply the same algorithm recursively and it will find the correct rank array so it's not such a big deal after all

3:43 DC3/Skew algorithm - Fix alphabet explosion

3:45 now as always or as often when you patch things up when you apply the duct tape you create other problems and in this case as well there is a problem that we created now and the problem is uh in each recursive step we combine triples of characters into one super character now if that doesn't sound scary think of exponential growth right in the initial you had maybe 10 10 digits uh if we'll say 20s 26 characters in the first step now you Cube that in the first recursive call so it's 26 to the third whatever that is and the next step you Cube that again probably you do that three times and you're out of whack uh you're in a uncomfortably Big Range so why is that a problem well we rely it previously in the in the inducing step we we applied counting sort to these numbers so if these become really really large numbers there's no more linear time sorting so we can't do that

4:55 it turns out there is again a patch for that and the reason is okay there may be many many possible triples but our strings are not arbitrarily big indeed our T Prime has at most two-thirds and different triples because that's the number of characters it has so most of these triples that are theoretically possible don't actually occur in our strings so what we do before we recurse is we reduce the alphabet to all the characters we really need

5:30 and we can do that because we're not really interested in the strings themselves but only in their relative order in the rank array at the end of the day so we look at all the triples that occur we sort them and we replace them by their rank so again we turn characters into numbers but the numbers are from a small range and so they will relay remain in the range that counting sort can be applied to in linear time effectively we maintain that the alphabet size is at most the length of the string that's a fairly reasonable thing to assume from the start as well

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

6:17 let's see an example how this works so both of these patching up steps together just to make it concrete same example as before if I compute the the T Prime I'm leaving off the first character here and then create groups of three and then I'm adding the same text but the first two characters gone so that's

6:44 bananas man okay I'm not stuttering that's the word right uh and you take triples and that's so you already see like the triples have an offset so you get all these uh all these suffixes in this small example there's only one triple that occurred before so there's not too many duplicates however there's many many triples of characters that do not occur right I don't see three b's or three M's or uh I don't know three s's all these don't occur so you take those occurrent triples and sort them here they are in sorted order and here is you can assign numbers to them so it's just ranks in yeah the the usual way like like we always do starting at zero

7:38 and so then you take your T Prime and turn it into t double Prime where you just replace every triple with its rank so A and N is here so you replace it with the number three

7:52 and that brings the alphabet size back to linear in the size of the text all right I don't know how clearly you see this but that's really all we need no more patches no more duct tape needed uh so first step is what I've shown you here you construct a different text again on a small alphabet reasonably small alphabet only of length to third end you recourse on that what you get back is the rank array you don't care that these characters have no connection anymore to the original text the relative order is the only thing that matters you get back this rank array R12 from that you compute R3 and then you merge the two both steps take linear time so that's that's the overall algorithm

8:49 Suffix array - Discussion

8:53 how good is this well uh at least I claim to you so far um this is much sleeker just in terms of the space if you're just storing the suffix array it's n numbers as opposed to end nodes potentially with Sigma parent Point uh child pointers and so on we have a fairly simple construction relying on just string sorting unless the text is super pathological that will work fine and you can do it in linear time the different steps I showed you maybe look scarier than they are if you code this up it's really quick and easy because it's just manipulating integer arrays and it's it's basically sorting with extra twists not much else happens in the DC3 algorithm so it's it's very efficient in practice

9:47 and you can do efficient string matching with a login overhead but that's also a downside in a way the theoretician at least feels feels the itching under the nails it's m Times log n and we we used to be able to do linear in m can't we somehow get this back and also there are other things in the suffix tree that we used before that seem gone for now