Video 6-7: §6.6 Linear-time suffix sorting -- Overview

0:00 Intro

0:03 okay in the next subsection I want to start looking at the linear time suffix sorting algorithm these are among the most recent results we'll talk about in this class they're at least from this millennium there are several such algorithms um this is the one that's I think most reasonable to explain um it's quite practical you can implement it to run really fast so it's it's a really nice and good algorithm it's not the latest and greatest potentially you can tweak it further but the point of this section will be to show you how you can do suffix sorting in the near time uh on on a on the theory side if you want um and there's implementations in libraries that can do that that play a few more tricks to make it a tiny tat faster than that

0:54 Inverse suffix array: going left & right

0:59 before we go to the algorithm I have to introduce a second concept that just makes it much easier to describe the algorithm in fact instead of L the suffix array so L stands for leaves the leaves of the suffix tree from left to right instead of L we'll compute R in the algorithm which is for rank that's the rank array um you can think of that as the inverse permutation of the suffix array the suffix array is a permutation I didn't point that out but it has all the numbers from 0 up through n exactly once in some scrambled order so you can also talk about the inverse permutation where if the the value at position R in the leaf array in the suffix array is I then we'll get the value r at position I in the rank array it's just reversed

2:01 um the definition of of this was that this uh starting position I the suffix starting at I is the earth smallest in lexicographic order right and another way to say that is that TI has rank 0 base rank r and so that's uh what will be in the rank array if you have the starting position the rank array tells you how many other suffixes are sure are before that in the alphabetic order and the other way around if you have uh if you want to find what's the fifth smallest then the leaf array can give you the starting position that's how you go all right uh maybe remember this picture and hopefully then my my many mnemonics for left and right will help you remember this so you write down the text all the suffixes first the whole text then you leave off one character at a time so try to remember this triangle um then I is sorted that's the starting position of the suffix I'm leaving off one more character each time and now the rank array tells you where to find this thing on the right what's on the right on the right you have the same suffixes but in sorted order so we know here that the ranks are in sorted order

3:27 and L tells you what's the starting position of that rank so for example I don't know which one do we take this one um L of 8 is 4 which means the eighth smallest suffix second largest starts at position four index four and so if you go to the left at position four you find the same string naban and similarly if you want to know how many strings are smaller in lexicographic order than the entire text you would look at R of 0 and find okay it goes to position six on the right so there's uh six things that are smaller fine so far I spent so much time on this slide because I want you to memorize these two things so leaf and and rank array they're inverses of each other the important bit is to remember where which one's which

4:31 Clicker Question

4:35 good point yeah let's not just rely on your memorizing they're not really there to trick you it's just about memorizing the picture okay ah it's slow but eventually works

6:44 so just briefly I said this before right L leaves the Lee lists the leaves from left to right there's so many else in that sentence hopefully that sticks and R does not simply said um L also lists the indices of suffixes in lexicographic order R is a different Beast that's the defining relation between L and R inverse permutations of each other maybe you can memorize it that way so L stands for leaf and left going left so in the picture from before you had suffixes in text order suffixes in sorted order so going left means using l

7:32 uh R stands for Rank and right going right is using r that's what going right going left okay now uh last few got this right these two okay this is uh I don't know if that's correct uh I'm telling you uh it can stand for that uh hopefully it helps

8:01 Linear-time suffix sorting

8:07 all right now it's time to present the the big picture of the linear time suffix sorting algorithm it's called this Q algorithm or DC3 for uh for this difference cover three we don't have to worry about that it's just the name under which you will find it uh it has three steps and it's basically a dividing conquer style algorithm like we've discussed a few at the end of section three uh let me describe the three steps so the first is we recurse on Computing some of the rank arrays so remember I told you we're eventually interested in the leaf array the suffix array but it's more convenient to compute the rang array the inverse permutation we can always compute one from the other in linear time with the simple Loop

9:03 R12 are the ranks um of all the suffixes that start at positions in the text that are not a multiple of three why that super weird definition uh bear with me a bit but you're just out of three consecutive indices uh three consecutive starting indices for a suffix you take two and you leave out the third that's how you go then you determine the rank array for these guys recursively

9:37 from that I'll show you how we'll be able to do that you can induce the ranks for the other ones the ones that do start at multiples of three um without spending a lot of extra time there will be some tricks involved but that's that's the second step and the third step is merging those two so you have the position you have the the ranks among all those and among all those but you can't uh directly translate so you still have to merge the two sorted orders into the the full um rang array are for the entire input

10:20 now before we worry about how to do these steps um let's have a quick look at the running time how this can eventually be linear time what you'll have to believe for now is that step two and three are taking linear time in the length of the text and we'll we'll come back to that if you take that for granted then we're overall in good shape because then the total complexity is is linear for the top most recursive calls doing steps two and three plus we recourse on something that has roughly size to third n so in the first recursive call we'll do again another round of steps two and three but on an array that's just two-thirds and long or a knit string and we keep going like this so you have this geometric series and of course we stop at some point when two thirds to some Power Times n is is less than one so you can write it as this you can upper bound it by this infinite sum where we keep keep cutting into two thirds and even this infinite sum is upper bounded by 3n so that's uh your your standard geometric series we've used a similar argument for the uh the rank selection algorithm where I showed you

11:37 this uh Square spiral maybe you remember that's effective for the same argument so assuming that we can do steps two and three in linear time uh we're in good shape

11:56 and once we have R we can easily get L from it and in fact we'll do this in between in the different steps whenever we have computed R we can easily get l in linear time that's a simple Loop to invert the permutation

12:11 DC3/ Skew algorithm - Step 2: Inducing ranks

12:16 let's first have a look at step two so we assume that we already know the relative order of all the Indus of all the suffixes that started indices not a multiple of three and we try to get the relative order of all those that do start at multiples of three that sounds super weird but if you just pick some uh if you just look at some examples um it becomes a bit more clear I think so suppose we want to take the entire text otherwise known as t0 and T3 the suffix that starts at position three how could we compare those two knowing or using the knowledge we have about these other suffixes well simple trick every suffix is another suffix with something with some additional character in front so if we just get rid of this then we turn that into T1 and T4 and 1 and 4 are not multiples of three right so we can use the information about T1 and T4 from the R12 array to decide which of these two following parts is smaller in lexicographic origin and so we only have to take care of this one additional character that we prepend and there's really two options right either the first character already decides if t0 is smaller or T3 is

13:47 smaller then we're fine or the first character of these two is equal and that we have then we have to look at the suffixes but we know how they compare so everything's done in short t0 comes before T3 if and only if this ordered pair so the first character and then this number the rank of The Following part comes before this pair another character and a number and that's it okay

14:22 now uh this only allows us to um compare two things that's not the same as as sorting yet to get this into the full linear time solution we have to apply a trick about sorting that we've seen before so before we get to that let me do a concrete example and show the step that I've Illustrated on two suffixes for all the ones that we need and so I just thought for this one it's useful if the example is not too small so that you can see things in action but I I don't want to go through reading all these strings so we have our our text Hannah bands bananas man and we add a few more dollars just to be sure that when we're cut with multiples of three that we always have enough dollars at the end to sort things out that's for convenience um here are the strings that we want to sort these are the ones that start at a multiple of three here are all the other strings and we assume recursively we know how they are sorted what's the sorted order in particular we have the the rank array given here now it's it's listed in this weird order because here they are in the sorted order the should have maybe put it on

14:33 DC3/ Skew algorithm - Inducing ranks example

15:43 this side all right so far so good so what we're doing now is try to get these sorted using that knowledge and so uh we replace I don't know if you can see this maybe a bit too subtle I split off the first character and then the rest slightly so we copy the First Column here that's just the first character of all those suffixes and then the rest of that suffix were replaced by a number and the number is the rank of what's left so for example in this case T15 when I split off the first character it's t16 what's left the S Man part then I look up rank of 16 is here so I find that's 14. so I take that Rank and put that as a number here and the last slide hopefully convinced you that this retains the relative order of all those

16:53 and the way to sort those is using two rounds of Radix sword which is uh you first sort by the the first component and then within those that are equal by the second component now the the trick why we do this um is that we can do it in linear time using counting sort because in both cases we're effectively sorting integers the First Column is is individual characters now we have letters written there but you all know there are ASCII characters they're they're converted to numbers anyways in a computer and the second is is pure strings from the start also the numbers are within a reasonable range because they are ranks right these go from zero up to what the number of these is which is 2 3 n so we won't run out of out of bits in our word Ram or something like that the numbers are not too big they're within zero and n okay so we can do this with two rounds of counting sword in linear time and from that we get our rank array r0 for all the suffixes that start at a multiple of zero

18:19 questions about this step two inducing the ranks for are zero if not let's look at the second non-recursive step three which is assume we have our zero in art one two which is effectively giving us the sorted order of the screen and blue suffixes I have these separate now at the moment the green ones are those that started at multiples of three the blue ones are still those that started an index not a multiple of three and we'd like to merge these two sorted lists so in a way this is a standard application of ours of our emerging algorithm we can just go through uh from the top and always take the smaller one the tricky bit is that we want to not spend a lot of time in the comparisons because these are strings they could have long Common prefixes so we might have to compare a lot of characters if we do this naively what will turn out to work is we use the standard sorting algorithm sorry the standard merging algorithm from merge sort but we use a trick to speed up comparisons which is similar to what we've done just in step two before

18:29 DC3/Skew algorithm - Step 3: Merging

19:47 so let's try to do that so here's a assorted prefix this is the overall smallest taken from here then this then this uh the first interesting one is this one where we have to see that ah comes before h n a n and then comes a n and now what's the next is it an anus man or as man well I guess you know but let's suppose the algorithm doesn't so it has to compare these two suffixes and the idea will be to apply the same trick as before the trick being look at the first character if they are not equal you're a happy man and you know what to do if they are equal you chop off that first character and keep looking so in this case they are the same characters so we have to keep looking so we we chop off the first character and look what happens and so in this case we end up from a green with a blue one and from a blue with a green one and we have gained nothing because we still cannot compare those two um that's a bummer

21:03 the trick here is to go one for the character and then it always works I'll comment on that after the example so if you take those two that we still could not compare and you do the trick one more time you're always guaranteed to end up with two Blues either after the first or after both steps and once we have the two Blues we can use our rank array and look which one's smaller and well in this case then that went all the way back no that's not what I wanted

21:37 DC3/ Skew algorithm - Step 3: Merging

21:48 I thought I put the exam the result up there too bad we can always use at most two steps and then we know what the smaller of the two is and if you don't see why um it helps to draw the the picture of the different cases so you have to um suffixes that are of some different length now remember there's always two positions

22:19 that are blue and then comes one green position the way I'm the reason why I'm drawing these lines across both is to emphasize that these are the same positions if you right align the strings these are the same characters and so the pattern of two two blue one green is the same across the two strings

22:57 uh this is green I guess this is green again blue blue blue blue blue blue blue blue blue blue so you can have different cases uh you can start one one string will be blue one will be green otherwise you already know the result so uh you can either have two Blues here or one blue if you have one if you have two Blues like in this case and you chop off the first character you end up with blue blue so that's the case where it immediately works uh and the other case is when you have just a single blue

23:51 if that's the case and you chop off the first two you just reverse the colors you have green blue but if you do it another time you're again into two Blues right and these are really all all cases that are possible apart from symmetry

24:10 so the the same step the same trick works for this step you just have to go one more character before you can decide it but then you can still do merging in linear time because each comparison takes constant time overall it might be comparing the first character maybe looking at the next maybe looking at the next but after three steps you're done