Video 6-8: §6.6 Linear-time suffix sorting (part 2)

0:00 Merging suffix lists

0:03 where we left off yesterday was the second step of the dc-3 algorithm where we induced the relative order of the suffixes that start at a multiple of three from the ranks that we recursively computed namely those blue ones the suffixes that don't start at a multiple of three what is left to do is merging these two things we have a sorted list of suffixes all of those that start at multiple of three and we have a sorted list of all those that start at other positions um and i showed these here in in green and blue and uh so these are sorted lists of strings and would like to merge them and the approach will be to use the standard merge sort merge method so we start at the beginning the first overall suffix must be one of the first of these two so we have to compare them and then the smaller of the two gets output and we move to the next one so in this case the first one will be this dollar sign because we always assume uh if nothing comes then this is sorted before anything that has another character so i've done this with a few of the first suffixes to show how we get get going in this in the general case so

1:23 here you see these are alphabetically sorted and i stopped at a certain point namely at these two so the next step we know these uh we have the first green two green ones and the first three blue ones these are the next two suffixes that we have to compare now we'd like to know which one is is earlier in the alphabet we could just compare them character by character but that's too slow we only have a constant time in our uh in our performance budget so we have to do this really really quick now we've already seen a trick just uh with just yesterday in step two how we can sometimes do this comparison very quickly by chopping off the first character so let's try the same trick here's our green string if we take the first character off we are guaranteed to land in the blue set

2:22 and we also know which of the suffixes that is because it's exactly the one that starts one character later so that's easy we can do the same thing with the blue string we chop the first character off and then uh oops we're ending up in the green set again so we know which which one it is but we are still comparing one green and one blue an apple and an orange so we still don't know which of the two is uh it comes earlier in the alphabet without spending more effort so it seems not to work in this case but don't you worry it is

3:00 just another step that we need to make and then it always works and that is just because of the fact that we have every third in this list so you occasionally get this case that chopping off one character you're still both in different sets but if you then do it another step so

3:33 right what you do is um you take one character off and you do this with another one that is positioned somewhere somewhere else um i wanted to make this a little longer so here here are two suffixes uh so sorry they should really stop at the same point and you're trying to get them both into the greens in the into the blue set and the blue set has two out of three positions maybe these two and then there's one green one so here's one green position two blue positions every position is either green or blue

3:55 Constant time comparisons

4:23 and now of course these are colored in the same way now originally this one starts green this one starts blue so they're in in different uh in different places in different classes if you chop off the first character here they're still in different classes now opposite but if you also chop off this character you're guaranteed that they're both in the in the blue set and uh you can think about this you have always have one of the two cases either you have to chop off one character and they're both in the blue set or you have to chop off two characters and then they're both in the blue set

5:01 but it always is just at most two characters that you have to take away from these strings and then you end up in a in a situation where you have two blue ranks two blue suffixes whose ranks you know so you can compare them okay that's an important um that's the key step for the merging so let me know if if this step is clear now if you have questions as always put them in the q a

5:39 so we need just um constant time for this comparison because what we do is we instead of originally comparing two suffixes we now compare one or two uh pairs of letters chopping of the first characters only if they are equal we have to continue and in the worst case we have to find the first two characters of the two suffixes are the same the second characters are the same and then what remains is two blue suffixes so we look up using r their rank and we compare the ranks as numbers and then we know the outcome of the comparison it cannot come out equal that's because we have the end of word marker so we will always find in at most three steps which of the two is uh smaller and then we can we can put this next one which is it in this in this case 17 and 13 so 17 is here 13's here so 13 would be the one so the green one should be the next one that comes here um which sounds wrong no it's the other one the 11 is this one so the the blue one is the next one of course so the next entry here would be t11 uh copying whatever that string is that

6:55 way we can get in constant time the next entry so we produce the sorted list of suffixes in constant time and that concludes how to do the overall third step of the dc 3 algorithm in constant time in linear time okay

7:15 Recursive DC3 approach

7:18 this is almost it unfortunately there's um one or two uh caveats with this so we've shown that both the inducing the ranks for r3 is linear time and the merging is linear time but if you look closely we actually cheated in the step one i simply said step one was recursively sort the suffixes that start at different positions not a multiple of three compute this r12 recursively but it's not really an instance of the same problem because uh to call this recursively we would need a single string so that these are the suffixes of this string that's the problem that we're solving with the main algorithm that's the problem that we can recurse on but what we now have is a weird set of strings it's well two out of every three suffixes of a given string how can we even apply the method to this for that we have to look a little closer it seems that this doesn't really doesn't really make doesn't really work but you can make it work with a trick i'll move out of the way for the example in a second but let me first discuss this the key insight is we don't directly use the same text we modify the text in in two ways first of all we don't

8:50 consider the original alphabet but we make new compound characters that each consist of three of the original characters and i'll denote these by these little boxes now if you take so this is where the example is important here's our original text banana ban and we fill up with dollars as convenient and then i'll denote with t box the boxed string where you uh just take triples um and make one character out of these if you take the suffixes of this t boxed then these are exactly the original sub the original suffixes that start at a multiple of three because uh the suffixes of this thing they start with everything and then the next thing leaves out the third the third first third three characters ah the first three characters the first six characters omitted and so on okay so i hope this that's the um that's the easy part uh we can emulate this skipping suffixes by grouping characters together and making these boxes around them so instead of the alphabet b a n and dollar we now have the alphabet of ban of anna of another band of triple dollar and all the other triples that might occur in your text so this would be fine for recursing on all those we want to recurse on all others so you

10:24 have to apply a slight additional trick and the trick is is this instead of the original text you could you generate this weird text where you start you take the suffix of t where you start at the first position and take the box version of that so that would give you t1 and t4 and t [Music]

10:54 7 and so on all the ones that are one modulo three and then you append another copy of t where you start with the second character so from this you get t2 t5 t8 and so on and you insert dollar triples in the middle so that you can you can separate those two okay so uh that means um even though so suffixes of this text they're either starting with something here or they're starting something with here and there will always be a dollar so that uh for those one that start here they have this long tail of the entire copy of the text but we can ignore that because we know once we see the dollar we can actually stop comparing okay so we recursively compute the suffix array uh the inverse suffix array rang ray and leaf array on this t prime and if you check the math works out we took two copies of t but we grouped um triples of characters so that still has roughly two-thirds n characters now so it's the same uh reduction in the input size and now uh the problem fits the r the original description and we can recursively call the very same algorithm on this

12:27 Alphabet size management

12:31 that's brilliant now because of this fix we actually created a new problem and to illustrate the problem you have to really look carefully so is this something that's very easy to overlook when you first think about it so this this seems to work fine right we know how to do step two in step three and we know how to do step one and we have reduced it in a way to compute suffix and rank and leaf array on another string so why where should there be a problem in this um maybe you can think about it and throw it in the in the q a uh this would be a good time to pause the video if you're watching this offline um but because we have some um some more material for today on on the list i want to go on and just tell you what happens so what obviously happens because we take triples is that our alphabet cubes in every recursive call right we uh we start with sigma characters that's the original string and that can be any number but you can assume that sigma is at most n because uh it doesn't make much sense to have an alphabet with more characters than ever occur in your text you could always um reduce that to the

13:53 characters that are only the characters that occur in your text but then in the first recursive call we make triples out of that and there sigma cubed triples of three letters from this from this alphabet the next recursive call we would take sigma cubed and cube that again that's sigma to the nine and you keep doing this so even if if originally sigma was two just a binary alphabet after ten steps you have a thousand uh sorry cubed so whatever that is uh what's 2 to the

14:39 30 that's already um in the billions that's almost the capacity of an end and that's 4 billion so it's roughly a billion so already really bad and that's just 10 recursive calls you will need you'll need a few more if your text is long so this will completely explode your alphabet will be big now that is not by itself a problem but we relied implicitly on this linear time sorting let me just briefly go back to that step to make this very clear we rely on linear size alphabets in this in this step we induce the ranks in step 2 from the ranks that we recursively compute by replacing the long suffixes by these pairs a character and the rank from the the remaining suffix the rank is fine that's always a number between i don't know 0 and n but the first here is one character from out from our alphabet and if the alphabet explodes becomes bigger and bigger then this becomes much longer and we cannot do this this linear time sorting anymore because that only works if we're sorting something where the range is roughly as big as the list we're sorting okay i hope the problem is clear now

16:16 so this is this is the problem what's the solution for this the solution is to observe that yes the alphabet can become very big but there's no way we can use all these different triples in each step remember our t prime the text that we recurse on it only has third n different characters that's the length of this text so that can be at most that many different triples that are actually occurring in our text so what we do is an alphabet reduction a step where we replace the actual triples by a number or by a different alphabet if you want but it's convenient to think of these as numbers so what we do is we take all the triples that actually occur make a list of these and then we sort them this can be done in linear time because in the initial step sigma is say a constant or even bounded by n is order n so we have triples of numbers that are each from order n so three steps radix worked with three steps or three rounds of counting sort same thing can sort any list of such triples that can be done in linear time and then we have a sorted list of these triples and we replace every triple by its rank

17:39 i'll have an example on the next slide so that ensures that in all recursive calls we always have an alphabet that's at most as big as the text is long that's always sufficient it always makes sense but we need this extra step because we computed the text um over a very large alphabet so we have to do this alphabet reduction step in between so as promised um here's an example for that um here's our um the my favorite um example from from this subsection where we need a bit longer text hannah ben's bananas man and uh so here's the t prime here you see t1 it omits the first character t2 omits the first two characters

18:03 Implementing the DC3 steps

18:34 and then you just um well you fill up with dollars here in the text whenever you need it so you just fill that up with dollars so that it aligns with um multiples of three that's easy to do if you actually compute the the triples so here's t prime how it actually looks uh it has lots of these triples but that's way fewer than what's the alphabet size we have h a n b s m so maybe

19:10 six six different characters if i can count uh six to the power of three is already uh i don't know a big number um something like almost uh 200 there's definitely not 200 different triples that occur here the occurring triples are actually these that is anna that's occurring twice and the the dollar that's occurring twice there's not many duplicates here but there's many triples that don't occur here like triple s or triple n or whatever right then you sort those triples that occur three rounds of counting sort then you get the ranks of these and finally you take every triple and replace it by its rank so just do this in slow mo if you have the triple a n you find that in the list

20:09 and um the way to do this is um you probably want to do some some hashing trick in in this uh to implement this mapping efficiently but let's um let's submit that detail so suppose you have a way to quickly find we didn't talk about hashing in this module suppose you have an efficient way to find oh we could just use a try a depth three try okay you insert all these into a try and store the rank there so in constant time because it's just depth three uh you can find this um and so you replace this by its rank three let's do another example ahb in the sorted list is here so you replace it by its rank etc you will also notice that the triple dollar necessarily is the first character in the new alphabet because it comes before all the other triples so this will always get a rank of zero and so we'll will serve the role of a new dollar character in the reduction okay that's how you get the the t double prime which is the actual string that you do the recursive call on where you can say the alphabet is is bounded in size in the length of the string but that is that is really it that's all

21:29 there is to the dc3 algorithm so the steps are first you do the recursive call for this you construct t prime as shown here then you sort the triples and reduce them to the rank that gives you t double prime on that you really recurse when you come back you have computed the r12 the ranks of all the suffixes of this string which can be mapped back to the suffixes of t that start at not the multiples of three positions from that you induce the ranks of all the suffixes that start at multiples of three and then you do the merging step in both step two and step three again use the tricks i've shown before to run in linear time that's how you construct a suffix array in linear time no matter how big the alphabets no matter what the string looks like this is worst case always works the algorithm is a bit complicated because of the different steps you have to combine but each of the individual steps is not very hard to do and you can implement this in in fairly concise code also the paper that presented this algorithm has a an implementation in the paper that fits in the appendix so this is fairly efficient in practice and close to the methods

22:52 that are used there are further tweaks to make it slightly more efficient but that's that's the core method that's behind these so that brings me to the end of the suffix array section we've seen that uh compared with the suffix tree that has all these pointers and the worries how to represent the try in memory etc in a memory efficient way the suffix array is just an array of numbers and that's very easy to work with and space efficient as well it's very simple to construct it on random strings

23:04 Suffix array conclusions

23:41 i just want to add this here again so this is this is the the fat pivot radix quicksort which is working very well if you just apply it to usual text but the guarantee is is much weaker than this in the worst case but we've also seen we can do it in optimal linear time up to a constant factor at the same time as you need to read the text and unlike for the suffix tree algorithms that were known before that this is actually with a reasonable constant you can do this on really large strings and the suffix array in isolation is already enough to support efficient string matching we've seen that at the very beginning you have a sorted list of strings so you just use binary search that is already pretty good you can speed up that search a little bit that's something we didn't talk about but we'll we'll get to something that's better than this anyway so a slight slight downside in the in the pure form like i've shown i've shown it string matching takes m times log n not the optimal order m time but even if the text is very big log n is not unreasonable the more the more important downside is as it stands um the suffix tree had all

24:54 these applications remember i listed six application and gas fields book has over 20. and the simplest one might have been string matching or pattern matching but there's many others and it seems for those we can't easily use suffix arrays so there's still something to add to make them as versatile and powerful as suffix trees and that's what we will actually look at next