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

0:00 Intro

0:03 in the next subsection i want to discuss how to compute the suffix array of a string in linear time we've seen a simple and login method using the fat pivots radix quake sword which is actually very easy to implement and gets the job done in a reasonable time but the theoretically best possible is linear time and for that we have to work a little harder

0:30 Inverse suffix array

0:35 before we can uh describe this this algorithm that gets the suffix array computed in linear time um i need to introduce the inverse suffix array because it turns out the algorithm is easier to understand when we compute the inverse suffix array and then can go back and forth between that and the suffix array itself conceptually the inverse suffix array this array r is is a very simple thing it just says uh find me the inverse permutation that is encoded by the leaf array something i haven't stressed before the suffix array is actually a permutation so it stores the numbers 0 up to n in an array of size in an array of 0 up to n and it stores every number exactly once so it just permutes these numbers in some way and every permutation is invertible there's an inverse permutation and that one's stored in r that's one way of expressing this the other way of saying it whenever we have that the r leaf in the left to right order the earth leaf in sorted order starts at position i in the text then r of i is little r uh and another way of saying this is that the suffix starting at position i has rank r because uh there's r suffixes that are smaller than it

2:09 in lexicographic order so that's why um i chose r for the inverse suffix array because it's reminiscent of rank and that's what it is it stores the rank for the suffix starting at a position whereas uh l stores the leaf in the in the left to right order so where the the suffix started

2:43 it's also if you want the left left index of the of the suffix and this picture below is i think a good way to memorize these two notions and to keep them separate because i'm i personally tended to mix those up easily so this is also for myself if we have a text banana bin we write all the suffixes in text order where we just move the like next character so you have this nice triangle shape uh if you have this here then um i is just the number zero up to n up to nine that's the starting position of the um of the suffix and then r of i tells you the rank of this suffix in the sorted order lexicographic order so the first one is actually always the one that's just the dollar by definition but then the next one who comes first that's uh depends on the text and in this case it's the suffix starting at position 5. on the right i have the same suffixes but now sorted

3:56 sorted lexicographically whereas here things are in text order how they appear in the text and having the suffixes in sorted order means that the rank goes from zero up to nine in in just counting up and then the suffix array tells you where's the starting position of that suffix so the smallest suffix in the text starts at position 9 is just the dollar and so on and so forth and you see it occasionally happens that those two numbers match but in general they they don't the second smallest suffix starts at position seven for example so those are the two two things to keep in mind keep in mind this picture the triangle on the left the jagged sorted list on the right and then um l and r have another nice meaning that luckily coincides um l means you are on the right and you want to go to the left so it tells you where to find a certain string in the left picture if you have the string here na ban it's the eighth in the sorted order and then the l entry tells you that at position 4 you find the same string on the left and same r which i took standing for rank can also mean right if you have a string

5:20 here maybe the whole text it starts at position zero so that's this one here if you look at r of zero it tells you that's the sixth smallest so it appears in at position six on the right okay i hope that these mnemonics uh stick in your mind and avoid you mixing up the two notions the two concepts

5:49 okay if that is clear then let's move on to the linear time algorithm for constructing suffix arrays there's different algorithms that do this what i will present is called the dc3 difference cover three or this q algorithm the name is a bit weird but that's that's what got stuck i don't want to explain where this comes from really that's just in case you're an expert and you see other algorithms this is the one we will talk about it proceeds in three curious steps

5:50 Lineartime suffix sorting

6:31 the first step is we make a recursive call and we compute the rank array so the inverse suffix array for some of the suffixes but not all well that wouldn't work we leave out all the suffixes that start at a multiple of three so we recurse on two thirds of the of the size right by uh leaving out every third and uh obtain the sorted order so r again the rank array tells you um if you're given the starting position in the text it tells you how many uh suffixes are smaller than this

7:18 okay that's the first step um how long that takes will depend on the other algorithm because it's recursive we will we'll see that eventually at this linear time but that only follows at the end the second step is given that we know these ranks we induce the ranks for the remaining suffixes now in both cases um because we recursively call here these ranks are only internally they only rank how the suffixes are sorted within each other and the same thing here we essentially sort the list of suffixes but only those that start at multiples of three and to speed up this sorting process we use the information from r12 and finally we have two sorted lists so we merge them together like in merge sort

8:16 and that will produce the rank array for the entire input r again the rank array is the inverse suffix array so if you have that you can easily translate it to the suffix array so that will uh construct l as well for us

8:35 okay now uh the the magic here comes in showing that step 2 and 3 both run in linear time step 3 you might believe that this is this is doable because merging is usually running in linear time but there's a caveat here because we're merging strings and merging needs pairwise comparisons so again we have to speed up comparisons here in this third step for that to run in linear time and for the second step we're sorting these are still uh n over three suffixes roughly right so um if we were to sort them with any simple means it would take n log n time we have to do it in linear time so we have to use this information that we've computed recursively for that and that will be the main trick of this algorithm

9:35 but let's first suppose we have already convinced ourselves that this is the case what is the total complexity then for the recursive calls well this is the step two and three on the on the top level so we spend linear time here linear time here let's just renormalize that so that the constant is one that's the uh the top level

10:08 we make a recursive call and now on this next level we only have two thirds of the strings we will have another step two and three and they take

10:19 together they take two-thirds n but that second step also has a recursive call and it takes two-thirds of two-thirds and so on and so on so you see what we get here is is this geometric sum in every step we get rid of a constant factor of a constant fraction of the input so that means after we factor out n we have this

10:53 geometric series and that is bounded by a constant in this times three so that shows that the total cost is linear in n as well okay so that is if the steps two and three take linear time the entire algorithm takes linear time that is a simple application of solving recurrences like you've practiced it in in unit one

11:23 also in the tutorials or unit zero whatever it was and that that proves that the entire algorithm is linear but we have to show that these two steps can be implemented in linear time

11:40 okay uh that's just the remark this algorithm actually computes r but we can use it to compute l and we can go back and forth between those that's always doable in linear time

11:54 for the rest of today i want to discuss this second step so we assume we have remember the recursive call computes sorts the suffixes computes the ranks for the suffixes that don't start at a multiple of three and we would like to use that information to compute the other ranks okay a little more formally

12:19 what i sub what i assume here just uh to make make the notation nicer is that this array r12 contains the rank of the suffix starting at i among those ranks that are not multiples of three if i is such an such a not multiple of three and for the other ones we just never access this so what what that says is just um we spread out the array so that it doesn't use the indices at position at positions that are multiples of three uh that's just makes the the notation convenient

13:08 now uh our task is to sort this list of suffixes in linear time and that's that looks like the same problem we originally started with um so uh it looks just as hard as the original problem but here's the trick suppose we compare the two suffixes t0 and t3 these are very long strings we don't have the time to compare them character by character but what we can do is compare the first character just one and after we stripped off the first character in t0 there's some character and then a long remainder but that remainder is just t1 the suffix starting at position 1. and the same thing happens for t3 there is some other character

14:02 i don't know if that's the same or not we don't know in general okay this is um should be shorter so that's t4 because we split off the first character now t1 and t4 1 and 4 are not multiples of 3. so we can take their ranks from what we've previously computed and compare them by just comparing the ranks that's the magic trick by splitting off one character we fall back into the set of suffixes that we know how to compare and we can use that information to compare these other long suffixes that we didn't know anything about up to that point so to summarize this t0 comes before t3 in lexicographic order if and only if this pair as a as a small string if you want with the first character of t0 and then the rank of t1 comes before the pair where we take the third character of the first character of t3 and then the rank of the remainder okay

15:21 that's the main magic step and that allows us to induce the ranks in in constant time per per comparison so let's um let's briefly look at how we do this in an example because there's one step uh that's still missing we would still i've shown you how we can do a single comparison in constant time but we still have to sort and doesn't sorting always take n log n time

16:01 well remember what we discussed when we were talking about the lower bound for sorting it only needs analog and time if we don't know anything about the objects that we're sorting and in particular for small integers we can sort in linear time and this is what will come back here we will use that as a black box here but you actually know how it works it's just counting sort but let me finish with this overall picture here first so this is the list of suffixes that we now have and we want to sort them lexicographically we recursively found for all the other suffixes those that don't start at a multiple of three we found the sorted order and in particular we know this r12 the rank array okay

16:53 now what we do is suppose we take this t15 we will transform this string which is too long to sort efficiently into something short that we do know how to sort efficiently and the way to do that is split off the first character that is just copy down and then for the rest s man turns out to be um well from t15 we go to t16 so we find that in this list and in particular uh we can look up the rank of this so t16 is here and on the other side if we go to 16 we know its rank is 14. so what we put in here is a 14 as the second component of this pair and we do that for all the uh the other the suffixes that start at multiples of three

18:00 and then we use radix sort to sort these in linear time because they now consist of one character that's even if the alphabet is bound it's even a constant size so this is very easy to sort and the second component is a number that's bounded by n and uh this we already know how to sort um using using counting sort so uh that's this result here we can sort these pairs in linear time by two iterations of counting sort first sort by the second component and then stability by the first that's that's how you would usually do this and then we get the sorted list of uh these suffixes that start at a multiple of three and from that we can find the rank array

18:58 that's the the second step of the dc3 algorithm given the ranks of the suffixes that don't start at multiples of three we could find the ranks of those that start at multiples of three one little caveat here is that these are these are ranks within that set we still have to merge we still have to do step three and that i i will reserve for tomorrow