Video 8-7: §8.6 Linear-time suffix sorting -- Induced sorting and merging

0:00 Introduction to suffix sorting

0:03 in the next section we'll look at a linear time worst case linear time algorithm for suffix sorting and uh I want to Hype it up a bit again or um make you uh make you aware of it that's it's a it's the most complicated algorithm we'll see in this module um but it's it's very nice that each individual step is not complicated it's one of those uh cases where coming up with this idea in the first place was really tricky or it took people a long while it's also one of the newest results we we're seeing this was published in 2000 I know uh some of the authors personally this is all not not that uh long and old decades old results uh this is closer to Cutting Edge research um but still still very Elementary in each individual step uh but the algorithm accomplishes this this this feat that we somehow avoided so far uh you have to somehow take a leap to to do this in linear time and maybe by the end of it you'll say ha hold on where where actually was the magic step that made this they made this do something that people first believ wasn't possible and I guess there will not be such a step every single step makes makes sense

1:20 and it's uh it's totally understandable anyways um uh it'll take us take us through today to get there so let's start with a bit of an an overview first to make this to make this algorithm clear um I have to introduce a helper definition um just because it's more convenient to formulate the algorithm for that uh helper algorithm for that helper result instead of the suffix array itself so remember L stands for leaves because the suffix array really is the leaves of the suffix tree ins sorted in in left to right order um and what we'll introduce is the inverse suffix array and it's it's essentially all that all you need for the definition formul is in this line it's the array that stores the inverse permutation um I didn't didn't mention this so far uh the suffix array always stores a permutation of the numbers zero up to n just because the leaves in the suffix array are numbered by the starting indices these are from 0er up to n and the leaves come in some order so it's some permutation there's no duplicate numbers and there's no missing numbers uh that's what that's uh supposed to mean and this array R the inverse suffix array just stores the inverse permutation which means if the r entry

1:52 Defining L and R arrays

2:49 in the L array is I then the I entry in the r array is r with uh small than Capital RS another another way to express this so remember um from the definition of of suffix array this meant that if you if you look at the suffix starting at position I then there's our suffixes

3:14 that come earlier in the alphabetic order another way to say the same thing is TI has rank R starting at zero that's how we defined it and so um you can you can interpret this r as the rank of a suffix so here you give me the rank in the leaf array you tell me the index is the rank the how many of in sorted order do you want and I'll tell you where it starts uh for the r array you tell me where the suffix starts and I'll tell you its rank okay it's the inverse of the two things uh there's another way to memorize lnr it's convenient that it comes down to the same same convention same letters uh that's this picture here and if you're more graphically inclined maybe that's easier to keep in memory and we'll we'll use this picture a few times so let me go through what it shows we have our text then here that just shows all the suffixes nicely aligned so we have the suffix that starts at zero 1 two all the way up through the last position uh and there's nothing happened right this is Trivial to proi use you just leave one more letter off at each point now uh there's the r array showing

4:37 here which is for each um for each suffix it tells you its rank in the sorted order on the right hand side are the same suffixes but this time sorted alphabetically that's what suffix sorting produces uh and uh then that also matches the leave array the suffix array because these uh suffixes will will appear in the suffix tree the leaves will appear in that order so here we have ordered the suffixes by their rank the first second and so we zero uh we start with zero the zero suffix is always just the dollar because we defined that to be smaller than anything and so on and so the second meaning for these L and R could be R takes you to the right and L takes you to the left if you have uh if you know where your suffix starts say I want want this one I know it starts at index one then R takes you to the right it tells you you should find it on the right at position four so you would go over here and indeed there you find an an ofan again and vice versa okay so that's is not a complicated definition uh I droned on about it for a bit because I want you to memorize it

6:00 well uh because we'll work work back and forth between those two it turns out that these algorithms to compute the suffix array are more conveniently formulated to compute r instead of L uh but if you have this relation you can compute one from the other quickly as that's a simple simple for Loop where you iterate through the positions and then you access the array with the with the result um so may be a nice exercise to program that but that takes linear time and it's a simple quick algorithm so if we can compute R in in linear time uh we can compute L from it whenever we need

6:53 it to make double sure that uh you remember this stuff let's go through some some Corner cases again uh so this is not really a trick question it is just um double-checking that the terms are

7:39 okay we had a phenomenal 88 votes for the attendance code um let's see how many Quest how many answers we get for this so about these options L or R stands for uh it doesn't need to be exclusive like uh they uh they don't need to ex they don't exclude each

8:53 other okay let's wait till 50 oh okay there we are not much waiting needed um it's again a lot of answers so in this case almost all are correct let's just quickly go through go through

9:17 them so first of all um a few things are essentially just the definition the suffix array lists the leaves of the suffix Tree in left to right order that is correct that's one way to define it um so R does not have any direct relation with that order it's the inverse permutation so uh this is not true it sounds like left and right so um be careful but um that would mean r is the the mirror image of L right if you uh you would swap everything around that might also be useful it turns out not to be useful here so uh R is just something else um our list the starting indices of suffixes in lexicographic order um that's also that's the other way around that's what L does uh as you see below uh that was the definition of the relation between the two so not much more to say about that and the pneumonics uh I didn't want to throw anything in to confuse you so these are all correct you can take l l to stand for the leaf array or for going left in that picture from earlier and R can be the rank array or going right um so if you if you keep keep in mind that these are the directions of

10:39 where we go then uh that's that's the way to memorize it okay so time for the actual algorithm uh we'll go through in in stages so this is the the high level overview first uh the algorithm is called DC3 or Q let stands for this difference cover uh because you can generalize the algorithm but that's not relevant for us uh it does something fairly peculiar so first of all it recursively computes a part of the a part of the answer namely all the ranks that start at indices that are not a multiple of three right so we have indices 0 1 two three and those that that started at zero and at three and at six these are excluded but all the others we compute recursively to so 2/3 of the of the answer is computed recursively okay uh let's suppose that works we'll use that recursively computed part of the answer to induce so to derive from that the other ranks so the relative order of those that start at positions uh a multiple of three now what what I should say about about these ranks so um this R12 and R3 these are only ranking relatively within their set of indices so R12 tells you among all those that don't start at a multiple of

10:45 The DC3 algorithm overview

12:15 three which is the first second third and so on it doesn't put this in relation to the total set of all suffixes and similarly for R3 of course the final answer that we want is uh in a way the combination of these two where we can for every pair of indices say which one comes earlier or we can determine the rank for every every index in the entire set and it turns out that you can do this with a merging step which is not too dissimilar from the merge sword algorithm that we've had um but it will we have a few extra tweaks to it so that's the high level thing solve two 2/3 of the problem recursively for the other third we'll use a trick to get them cheaply from that and then the overall result we also get cheaply from these two things now let's first suppose all of that is is done and solved why does that give us the required time uh it's similar to what we've seen about um the selection problem finding an element by rank there we had this I was drawing this picture where you have the you have one then you have 1/2 then you have a quarter then you have e and so on so you have always

13:38 enough maybe you remember this snake picture that's a geometric sum and we have something similar here if we assume that um this step and this step takes linear time the second and third step then we by and large spend linear time on the first recursive call the topmost one for doing this these two steps but we recursively have the same cost in the recursive call on the first part but only on 2/3 of the input and so if you keep going like this you always have a mult a factor of 2/3 you can upper bound this by going all the way to Infinity with that sum and uh that sum turns out to be three so you upper bound the overall cost by three three times the cost of of these two steps assuming that they take linear time in their in their input size which is I mean we'll have to we'll have to show how to do that but if we can if we can show that they're in in linear time then the overall algorithm also just takes linear time so that's the easy part um the rest of the time we'll spend arguing how we can do this and um

15:01 Sorting the recursive step

15:03 note that all the formulation here is for r as I said before um it turns out to be more convenient to compute the rank array instead of the leaf array but we can compute that from can compute the suffix array from our when we're

15:24 done the first step is just recursing so in a way we'll uh that's that's not the hardest part let's look at at the Second Step so the Second Step again remember we've computed this R12 and now we want to get R3 out of it so R12 is known for every suffix who starting index is among those numbers not a multiple of three uh we know the rank and we can by comparing the ranks we can in in constant time decide which of these two suffixes comes earlier in in alphabetic order now uh for all the others uh we don't know anything so far and our task is to you can you can reformulate the task to sort these suffixes in linear time if we have their sorted order if they're in the list in in sorted order we can produce the rank array from that by just iterating through the thing that occurs first gets the rank zero the second gets the rank one and what's at position I gets gets rank I so it's a sorting task but a strange one because we have this weird extra information again in general you would not be able to sort in linear time under these circumstances it's not one of those cases uh it's only possible

16:47 because we have this extra information so suppose we um we would like to compare two uh two suffixes so one that starts at zero and then another one that starts at at

17:10 three we can't just go character by character because that that will definitely be too expensive in the worst case if the text is really strange it could take linear time but if I chop off the first character then I have something that starts at position one and at position four in this case and now while zero and three were multiples of three if I remove one thing and so I increase the index by one that's not a multiple of three anymore for sure not so I can take T1 and T4 and those two I can compare in constant time because I can use their ranks from this R12 array so I I can actually use this to do comparisons in constant time um if I want to figure out whether t0 or T3 comes earlier in the alphabetic order I explicitly compare the first character now if that one's different I already know which comes earlier whatever car character is earli in the alphabet but if they're the same then um I instead look at the suffixes that remain after that and those two I have already all information I need to I need need for that so in a way you can rewrite this instead of comparing the whole suffixes you take the first character and then

18:35 the rank of the remaining suffix so you formulate these pairs these are pairs of one character and one number so those can be ordered in constant time okay that's the first trick and to turn that into a sorting algorithm all you really need is the counting sord algorithm from from back then in unit three uh so here's a concrete example that shows that uh how's that how that works so we have a slightly longer text and um to make life convenient where we're chopping off Parts multiples of three so it's convenient to add a few more dollars at the end to make sure that we're uh we always have enough characters to compare here are the suffixes that we would like to sort now that's the ones that start at multiples of three and here are all the others which we have recursively sorted so here they are in sorted order and here's their rank array I don't know if you can if it's uh big enough to read uh but you can you can check at the slides if you

19:49 want now taking um I don't know if that's visible here I've uh separated the first character of those suffixes so if you take the first character and copy that down as a column and all the rest of the suffixes you replace by the rank so for example here an anab banana man bananas man so if I chop off H I only have anab bananas man and anaband bananas man is here it has rank five so that's why we get the five over here that's the forming those pairs that I mentioned on the previous slide and just visually you see now instead of sorting these long strings you have these uh much smaller objects and we can use radic sort which means two rounds of counting sort I can first sort by uh the first character with one round of counting sort and then uh the second round on among all those with the same character I sort by the numbers that's one way to do it and then you get all of these in sorted order and from that you can just read off the ranks right this one t21 gets rank zero 18 is the ne next it gets rank one and so on

21:19 okay and that's that's the result of this step that's R Zer it's the ranks of everything that starts at um a multiples of three and we overall take take linear time for this just because each of those steps constructing that list takes linear Time by just accessing the rank array that we got from the recursion and the two rounds of counting sword take linear time so it's overall linear time so

21:51 Merging the results

21:54 far let's look let's now look have uh let's now have a look at the third step uh we have at this point we have t0 and we have T12 so we know the relative order of all the suffixes that either start with multiples of three or not with multiples of three so these are like two sorted runs you have a sorted list of strings and you have another sorted list of strings so in a way what we can do is apply the standard merging algorithm from merge sword and uh indeed we'll do exactly that algorithm what we need is a trick to speed up comparisons again what would not work is at each point I have to decide which one is smaller the single dollar or the two dollars for those short strings fine uh it's a single dollar but if you compare some long string what you cannot do is go through character by character that would give you a linear time for just one comparison but we'll have to speed things up let's see we saw a trick just before by um splitting off the first character and let's see how far that gets us so let's suppose we have started the merging so um I start let's briefly uh simulate that so we start at the first

23:17 position I'll take the smaller of the two that's this one put it to the output then I move move one position down this time this one wins $2 is smaller than the $3 then this time that one wins dollar is earlier than any other character and now things start to get a little more interesting both starts with an A but then H gets comes before n so move that one down and um Now we move this one out because a and dollar comes before a and

23:58 a so I I sketch how you would do the character by character wise comparison just to get us to this point but this is not what the algorithm would do so the next step is uh to compare these two it's a general situation where you could have some long strings so let's try the same trick that worked for step two this is one one from the green run this is one from the blue run if I remove the first character what's left is some suffix from the blue group so it's it's a followed by t16 if I do that with 11 it's also a followed by T12 but somehow the trick failed Us in this case because what we started with was two suffixes from opposite colors and by removing a character we got two new suffixes they swapped roles but they're still from opposite colors

25:02 so it it didn't work in this case but if you go one step further if you remove a second character then it always works so in this case um if you take 16 and 12 and you chop off one more character on either side you're you're guaranteed to get two blue ones and this this works in general because uh think about uh a general situation so I have my two suffix is I don't know exactly where they start but they always have this pattern one green character and then two

25:42 blue in the sense of I'm coloring characters if you start the suffix at this position you would get a suffix of that color right so this is this is a multiple of

25:55 three and these two are not a multiple of three so if you you just write the indices in modulo 3 you always get a zero one two and the one and two are blue and the zero is green now there's different options how things could align uh but suppose this one starts with

26:26 green and then two blue so I have green and blue I can not compare them directly but if I remove one character I have blue here and green here ah still doesn't work as in this case if I remove another character then I'm I'm back to both blue the other option that you could have could have had was uh would have been here two

26:57 blues and in this case one step is in enough if I remove the green here and the first blue then I have two blues and that's the only two cases you can have you start with two opposite colors so that one has to start with green and then the one that starts with blue it could either be a one or a two module or three that you start with and in both cases either you remove one character or you remove two characters after that you have two suffixes that are both from the blue group and so you know how to compare them so what what the outcome here is uh I can use R12 to resolve any comparison after checking one or two characters up front and so um I can do every comparison in constant

28:17 so by checking whether your starting index of the one is modulo 3 a one or a two you can determine whether you have to check one or two characters and if they're the same then you have to compare what R12 gives you but then you've resolved the comparison if every comparison takes constant time then the overall merging algorithm takes time linear in the size of the output that's uh the same analysis as we've we've looked at in in unit three so with that we could actually do the merging in linear time