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

0:00 Introduction

0:05 so welcome back in this subsection we'll look at the the overview of the algorithm and the first two steps of how to build a suffix array in in linear time as the the title says building the suffix array is the same as sorting the suffixes suffixes lexicographically

0:22 so this is also sometimes called just suffix sorting uh before we discuss this um this slide i just want to point out that the linear time sorting of of suffix arrays is a fairly recent result it's all in this millennium which i mean given that it's it's fairly fundamental um i find that always uh a bit surprising or astounding um so the algorithm will present is from a paper from 2003 so you were all alive when that happened and uh this is different from some of the other results which uh stuff from unit 2 dates back at least to the 50s 60s some of the other things are in between if you go back to that time and look at what the computers were like they were vastly different and much smaller but 2003 that come on that's that's our age right uh so the results are quite recent uh i think they're remarkable in beauty in that they have these these uh very beautiful insights that make the algorithms tick but also um none of the little tricks by itself is really impenetrably hard as you will hopefully see it's all just little tricks but you need to add quite a few of them together before this all makes one round picture so that's kind of

1:50 my motivation for you and also my warning bear with me for a while i will take most of today for getting through this algorithm but each individual step should be doable with a little bit of caffeine maybe

2:07 Inverse suffix arrays

2:10 before we discuss the actual algorithm to construct the suffix array it's convenient to introduce the inverse suffix array and that really is the inverse in the sense of a permutation so the suffix array here that's l it's the same example so you will see these numbers uh pop up on many slides in the next in the next hour uh the suffix array again uh tells you the arth entry is in sorted order in this lexicographic order of the suffixes what's the starting index of that of the earth suffix so for example the fourth smalls well the the one with rank four starting at 0 for this string is the entire text no highlight almost the entire text is the subject starting at 1 obviously because the strings also start at 0. now the inverse suffix array is the inverse permutation of this list of numbers notice that the suffix array always is a permutation every number between 0 and n occurs exactly once it's the number 0 to n somehow jumbled and so you can you can ask yourself if i look at um that's what's spelled out here if i look at what is at the position um well where's the seven the answer is position two so you would like an array that gives you at position seven the

3:36 entry two that's the the inverse suffix array there's nothing fancy in this concept it's very easy to compute one if you have one you can just iterate over it and fill the other by inverting the index and the value what i'd like to do with this slide is give you a few mnemonics to not mix those two up so i named the suffix array l for leaves because that is the leaves from left to right in the suffix tree and the entry in the suffix in the suffix array is the suffix and the suffix is the same as its starting index

4:20 the other thing the inverse suffix array r i called it r because it's the rank array it tells you for the is in text order right this is um suffix starting at zero subject starting at one and so on what is its rank in sorted order so the one starting at zero the entire text is rank sixth in the sorted list uh just the little cave yet again uh we start with zero so the ranks are also zero based okay relatively easy concept but try to keep those in mind another mnemonic is r is for going right and l is for going left in this picture i think it's a fairly natural thing to say in this picture we start on the left with uh the text in with the suffixes in text order where you just start with the entire text and then you leave off one more character that's very easy to build and then going to the right you sort them so here you have the same same strings but sorted lexicographically if you've done that then r takes you to the right if you have an entry here the zeroth it tells you where you find it on the right and l is the opposite okay so that's just a few ways hopefully

5:32 helping you to keep in mind which one is which but the slide's always there for you to look it up again and this is a question that accidentally you've seen last time already but this time you really know what we're talking about so i'll just ask them again

6:05 so this is just reinforcing the new knowledge again quite a lot to read so i'll give you a bit more time all right um i'll leave it open but here's the uh it's the distribution of answers

7:59 um quite a few things got quite a few votes uh but i am also quite a few of the answers are correct so let's just briefly go through these uh the last four um i just the the last thing i said in the previous slide that's different ways of hopefully um remembering what l and r was i found these helpful and then the these statements are just mimicked for for l and r so again l is the leaves in the suffix tree from left to right and i would like to yeah l stands for left but in the sense of this previous picture going left from the sorted suffixes back to the text the suffix in text order

8:56 l also lists the starting index indices of suffixes in lexicographic order so both of these statements were true for l and not for r the true thing that you could have said about r is that r gives you the rank of the suffix starting at at a position so it's the rank array that's why it stands for rank all right

9:23 Skew algorithm

9:28 so uh i said before if we want to have any chance of sorting suffixes in linear time worst case or not um we have to exploit the fact that these are not arbitrary strings but they are the suffixes of of one text if you uh sort arbitrary strings you can't break this n log n barrier and in in many cases you can't even quite achieve that because you need to compare all the common prefixes but we do have a text and all that stuff exists so we can sort it more efficiently and here's this this algorithm that we'll discuss is called the dc3 algorithm or the skew algorithm if you want to know why these names are are there you will have to read the additional reading

10:17 it's a recursive algorithm and it does three simple steps and that together will sort the problem remember we are sorting it's all about sorting the suffixes what we'll do is we first recursively sort two thirds of the suffixes and which ones well we sort those that start at positions

10:43 um two one two so we take those let's start at position one and two we don't take the multiples of uh three but then we take four and five and so that's how you take uh out of all every three consecutive ones you take two okay so we take the suffixes let's start at these positions that i that i marked in this another way to say it all the indices that are not equivalent to zero modulo three these restored recursively we'll we'll show in a second why this is fast enough for now i'll just i'll just throw these steps at you for each and every one of these steps there will be more details later okay this is just a big overview for now uh the second step is all the uh suffixes we left out those that start at multiples of three we still have to sort them somehow and we can infer their order from these these ones that start at positions one two modulo three so i'll abbreviate with um r12 the rank array for this subset of suffixes those that start at these positions and then r3 is those that started at multiples of three could have called it r0 but it's the same modular three i guess

12:19 and so it turns out you can induce this rank array r3 from the other one and we'll see how and then we have two um we have two sorted lists of suffixes remember suffix is in a sense just strings so we have two sorted lists of strings so what we can do with them is just merge them and then we get the entire sorted list and that's the third step again to make this fast we'll have to make proper use of these rank arrays and you'll see in a second why or how now this this smells a little bit like merge sort but there's a key difference it only does one recursive step it only recurses on two thirds of the lists unlike merge sort which split the list in two but it recurs on n elements again and that's why merge sort is n log n and this algorithm hopefully isn't but there's something fishy maybe it sounds how can you possibly do this second step that sounds where the magic is happening

13:19 so that's where we'll use that we're sorting suffixes and not arbitrary strings but let's first analyze the overall algorithm why does it make such a big difference that we don't recurse on the entire list

13:35 probably i've seen this in in master theorems etc but i want to just give a the graphical representation so the total cost if we uh okay i should have said this first we will show that the steps two and three take linear time they take time that is proportional to the length of the the current list and this will this will keep us busy for a while but let's take it for granted for now then the total complexity of the entire algorithm is what you need in the first step and what you need in all the recursive calls and so for the first step we have a linear contribution from the steps two and three and that is for the entire list

14:28 and then we make a recursive call on two thirds of that list so that's something like this that's the next recursive call and that again has a contribution that's linear in that size and then you do this one more time i need to keep going now at some point you reach an individual just a singleton and you stop

14:53 but this is if you always lose i think i should draw it slightly more carefully maybe if you always lose a constant fraction in the recursive call what you get if you spell it out is a geometric series or it's upper bounded by a geometric series and the sum of these things uh a number less than one to the is on the wall i that's bounded by a constant so in this case it's it's bounded by three okay

15:33 and so the overall uh running time of this algorithm is linear that's something you you will have seen for other algorithms uh quick select is is similar in a sense um what are other typical algorithms where you just recurse on one side

15:51 yeah there's other examples it'll come back at some point uh so this is this is a fairly standard analysis the interesting part is showing that the steps two and three have linear time okay

16:07 is the is the derivation here roughly clear how we get to this um the recursion you can spell it out as a recursive formula i've immediately unrolled it and and then upper bounded

16:24 okay so what we still have to do is look at these two steps how can we do those in in linear time one point that i glossed over here is we compute r the rank array at the end at least we want l the suffix array but as i as i claimed on the last slide already you can always if you have one compute the other in linear time uh by just filling the array uh iterate over the one and fill the other jumping around so we can in the formulation of the algorithm i'll allow myself to use l and r whenever it's convenient and you can always at the beginning of each step compute the other one if you need it

17:18 so now let's look at step two first which was we have the recursion done for these suffixes that start at positions one or two modulo three and we would like to sort these suffixes that start at multiples of three and we somehow have to use the knowledge that we got from from these ones from sorting those ones so how could we possibly do this

17:43 Sort method

17:45 and the the answer is uh let's do let's start the obvious if we want to know if you want to sort these suffixes we could start comparing and do some some sorting method that works on on pairwise comparisons we can't afford to compare long suffixes character by character because they can be linear in the size of the text so this would take linear time for just a single comparison and we want to sort the entire list but after we've removed from a suffix one character if it previously started at say position three if you take off the first let's maybe do this so if that is t3 if i remove that first character what i'm left with is t4 the suffix that starts at position four and four is not a multiple of three so that's a suffix i have in the list that i've sorted already if i compare t3 with t0

18:57 and also chop off the first character i'm left with t1 and those two i can compare by looking at their ranks so t1 comes before t4 if and only if it has a smaller rank in in the rank array so if if

19:27 r12 of one is smaller than r12 r4 okay so we have the following statement that we can use where any two suffixes is spelled out for this example but it works it works for any indus index that's a multiple of three this one comes before this one in lexicographic order if and only if this pair comes before this pair in which means we start comparing the first component of the pair which is a single character that's this first character that i just deleted now for sorting i can't simply delete it and ignore it i have to look at it but this is a this is a constant time operation either those two characters are different and then the one that comes earlier in the alphabet determines which of the two strings comes earlier in the sorted list or they are the same in which case i have to go to comparing t4 to t1 is that idea clear so you look at the first character if they're equal you have to continue but if so the remaining suffix is one that you have already sorted and so you can reduce the problem of just sorting these pairs

20:40 Example

20:42 let's see an example on a slightly bigger text that illustrates this so we have this lovely text hannah bans bananas man and it's convenient to add a few more dollars at the end so that we don't uh run into comparisons of something with empty

21:03 these are all the suffixes that started at a multiple of three so these are the ones that we want to sort now and we don't know yet how their ranks are and these are all the other suffixes those that start at not a multiple of three and those we already have sorted so here's in text order here's the sorted list the suffix is inserted order and here well might be small to read if you have good eyes you can read this is the rank array and so uh it's it's listed so that the ranks are zero up to 14 because they're sorted here but of course you could put that rank on on the other side then uh it's it's just a just an array okay so we we know all the ranks for these suffixes that start not at a multiple of three and now we um we reduce this list of strings which is tough to sort to something that is efficient to sort namely a list of pairs or short strings if you if you prefer and what we do here is we take the first letters you see that this this row of first letters is the same as above just copied down and then the remaining part here so in this in this example of of t15 the

22:21 remaining part is just s man and dollars that is t16 so we go into our list and look up what's the rank of of t16 and the rank of t16 here is 14 because it happens to be the last in the sorted order among those others and so we replace this long suffix with just its rank and so that brings us to this list and sorting this list gives us the same order as sorting this list of suffixes

23:01 and how can we sort these in in linear time because they are short we can use and and they don't have a big range we can use something like counting sort that we've seen in unit three that was this algorithm where at the time i told you um keep keep this box in mind we can sort these these pairs by two iterations of counting sword in in the first iteration we sort by the by the last component and these are literally numbers uh the ranks here and then in the second component in the second run we sort by the first character of the pair and that's characters but we can always reduce the alphabet to all the characters that occur and so it's never more than the strings number of strings in the list

24:03 okay so in a sense using the single method we've seen for sorting in linear time is what we do here we reduce the problem of sorting lists of strings to something that is pair a list of pairs of integers and so with two rounds we can get this done in linear time and then we have the the rank array for uh for these

24:30 now i want to point out that the rank arrays the r12 and r3 r0 oh here i did call it r0 instead of r3 i guess it's a mistake on the first slide then the rank race r12 and r0 are ranks within their subset of suffixes so these are the numbers 0 up to 14 these are the numbers 0 up to 7. so they only rank suffixes from within the same group okay but that was what we wanted for the for the second step we wanted to sort those the third of suffixes that we did not recurse on using the information from the recursive step

25:21 and now comes the last step of this algorithm step three where we have the two sorted lists of strings and we want to merge them into one big sorted list so let's see what we have in green this is the list that we just produced that's the multiple of three suffixes in sorted order that's the one that we got from the recursion in blue that's the the suffixes starting at 1 2 modulo 3. and now we want to merge them what we'll try is use the standard merging method from merge sort like i illustrated it on the slide back then so we just go through these sort through these runs and pick the smallest of each and try to compare them and whatever it comes out smaller goes to the output and we continue it's exactly what you've seen before the only the only trick that we need is make this comparison fast because again it's strings it would take us potential linear time to do one comparison we can't afford that

26:22 i already started this merge and i want to show what the next step looks like so uh these are the next potential candidates for the the next output element so we have to compare this this uh suffix and this suffix i started a bit later in the merge because i wanted to compare two longer suffixes the first always the ones that have lots of dollars so they are they're not so interesting

26:52 so we've been successful with sorting the the r0 suffixes by just chopping off the first character so let's try the same trick again so in this case we have to compare t15 and t11 let's try chopping off the first character so t15 is a green one chopping up the first character gives us t16 and that's a blue one if we do the same to t11 we go from from blue to green

27:24 and that does not help us at all because we can't compare green and blue directly what we can is if i have two blue elements i can look up in the in the sorted list which comes earlier if i have two green i can look up in the sorted list which comes earlier but if i have one green one blue i don't know which one's better so it looks like this doesn't work here we still can't compare these suffixes that we got after chopping off one character that's a bummer but we can do it just one more time if we chop off a second character we're guaranteed to succeed and we can have a look at that in a second so if we do that to the example we take the ones that we were left with 16 and 12. if we chop off another character we get 17 which is blue and we get 13 which is blue and so

28:19 i can sort those two by looking up where they occur in the blue list so in this case the rank of 17 is well whatever that is 13 comes earlier so 13 wins and that should be the next one that goes here uh did i put that here no um let's just spend a very brief moment thinking why two steps should always succeed that might not be quite obvious yet but if you draw the array it becomes clear

29:05 so let me color those um like they are in the picture so we have and in a sense we have to go through nine different cases the first run can start at zero one or two modulo three and the second run can start at zero one or two modulo three but many of these cases are boring if they both start at zero that actually never happens because we're merging two lists where this never occurs so it can only happen that we have one green one blue and it's really just two cases because there's two types of blue there's those that start at one modulo three and those that start at two modulo three and we have the case here where

30:03 11 is 2 modulo 3 right and so the other case maybe we can yeah so we have 0 mod 3 versus 2 mod 3. that one we have already done that's that's one the example down there and then we can only have the one other case uh where we have zero versus one so one is here and one is here

30:44 now if we chop off one character we move this arrow one to the right so we jump to this one and they're both black ah blue and because they're both blue we can compare them okay so that's the one other case that we have to check so no matter which two runs from green and blue you're trying to compare if you chop off one or two characters you always know you end up with two suffixes in the blue range and so you can take the array the rank array one two to check which one comes earlier

31:21 so in total you need constant time for each of these comparisons it's chopping off one or two characters and you can compute with the indices modulo 3 which case it is and then maybe look up one comparison of ranks so each step of the merge takes constant time and merge overall uses a linear number of comparisons so that together means we merge the two lists in linear time okay

31:54 as i said both of the steps are a little tricky but there's no huge quantum leaps in either of them it is using in a smart way the the fact that we have suffixes of a given string