Video 8-6: §8.5 Suffix arrays

0:01 in the next subsection we'll look at suffix arrays sounds similar to suffix trees and has relations but first of all looks like um an entirely different Beast uh the ultimate goal will be to put our our suffix trees on a diet by getting rid of most of the pointers so um here's our suffix tree the way I've drawn it before in some examples to the growing to the side uh and what I've done here is um um put the leaves one one below the other um I didn't stress this earlier but we've actually had that before if you make sure that all the child edges from each node are ordered by the alphabetic order of the of the letters then you actually get all those suffixes in lexicographic order the dollar comes first because that's always the smallest character in our ordering then there's a Noe with a so everything that starts with an A will be in the range of that sub tree and that comes before everything that starts with a B which is in this sub tree and so on right so uh there's a there's an inherent connection between suffix trees and ordering the suffixes or sorting all the suffixes in in the standard lexicographic order if at least if you

1:25 draw the child edges uh in the right order and so how about forgetting about this fancy tree with all its pointers and just keeping that sorted order sounds maybe a bit crazy because uh we've used a lot from the tree structure in these applications uh but let's see how far we get um I'll call the I'll call this L for leaves so um you should think of

1:58 it uh basically basically as as L of Zer is the index for this Leaf which always is the last so in banana ban would be 0 1 2 3 4 five 6 7 8 nine hope that's correct l0 would be nine because the first leave in leic graphic order is the leaf that has starting index 9 and so on so we can represent this this lexographic ordering as just an array of numbers now it turns out that's enough to do some of the questions to answer some of the questions that we've answered before with the suffix tree for example we can still do string matching if I have a pattern like Anna how do I find the occurrences of that pattern in our text I do a binary search in this sorted list so how would binary search work well we'll start in the middle um now I would compare is Anna smaller or bigger than this in alphabetic order and okay we're straight bang into the special case it depends now what I add to Anna at the end let's let's suppose I add the dollar sign then it would be smaller so now instead of the whole range I have this as the range of possibilities for the binary search I compare it with the with the middle one

3:35 a and dollar is smaller so now I'm in this range and I would do another example another comparison here so I would find that if Anna dollar was in this list it would go between those two I could do um a second I don't know uh an a pound where pound is bigger than all dollars of course pound's bigger than dollars uh if you do this this binary search again you would find that it should go in between

4:17 here what does that mean it means all this all the words that start with Anna are between those two positions and if I look in my array what the numbers there are in in this L array it would be the starting indices of these suffixes which is nothing but the occurrences the first index of the occurrence of an of Anna so by two binary searches I can find all the indices where this string occurs so I could do the same kind of trick as in the suffix tree but without all the tree I've I've not looked at all that stuff I've forgotten all the point find and all all of the nodes I just kept the sorted order of the suffixes uh so that's that's a bit of my um motivation for uh why you you don't actually need much from the suffix tree for this

5:21 application so formally the suffix array is just this list of of indices one array of of numbers um I've explained this already but here uh it's listed again um note that it has indices from zero up to n inclusive uh because we add this dollar symbol so we have n plus one characters in the text right same as before and yeah to say it again so the AR entry in the suffix array is the AR smallest suffix in lexicographic order and what we have in the array is the starting index of that suffix uh the algorithm that I sketched on the example for finding finding uh the occurrences of a pattern it does two binary searches now you will remember binary search takes log n plus two if we want to be worst case on the safe side uh steps to to rec of recurs of recursing down until you found a position but each of the comparisons can take up to M character comparison so the overall time is log n * m okay and you should compare this in the suffix tree we had essentially M as our matching time so we have a log n overhead which comes from Forgetting all of the tree so in a way uh I mean that's it's

6:52 not nothing but log n is much much smaller than n so you could say that's that's tolerable to be a bit slower when now all you need is just an array of numbers and not this dozens times larger suffix tree so as a first step uh that already looks promising and what I'll convince you in the rest of this unit is you can base on this suffix array you can base all the algorithms that we've seen for suffix trees with a few extra tricks you can simulate what they do with much less

7:35 memory okay uh there's a few nitpicks on the definitions that um I'd like to hammer in so as soon as this works yep it's come up now um I'll leave it here then you have the nice rendering um actually you can see the you can see the question maybe it's useful to keep that slide up then you have the definitions

8:44 I don't want to rush this question because there's a lot of insight to be had from from that one so I take your okay let let me start discussing uh so we don't overrun too

11:14 badly actually a lot of lot of stuff is correct on this one uh okay let's see first of all uh L lists the start indices of of leaves or the the start indes of the suffixes corresponding to the leaves uh in left to right order if we draw the tree in the normal way where smaller goes to the left and larger goes to the right for each children for each child um in my uh upside down World here you have to kind of tilt your head to the left otherwise this is correct um the path label here um it's not the leaf storing R but it's the AR smallest leaf or lexicographic order um so it's kind of the other way around and this one is the is the right answer another way to say that same thing is if you take the suffix that starts at position L of R then that's the AR smallest among those um the last is maybe uh I don't know maybe a bit surprising but I think I've said it uh said it quite explicitly both the suffix array and the suffix tree take um under the assumption that the alphabet is constant take a linear amount of space Theta of NW of space uh but the constant

12:51 for the suffix tree will be will be much bigger and indeed for the suffix array the alphabet doesn't even make a difference all that I'm storing is n numbers and indices between between zero and N uh so for the suffix for the suffix array the alphabet size is irrelevant and for the suffix tree that certainly plays a role right and uh We've we've just seen um both can be used to solve string mat uh text indexing or string matching text indexing is the same as string matching but with the pre-processing on the text explicitly allowed okay um maybe apart from the last question most most people agreed on this so maybe it was just a maybe it should have said string matching to be more

13:45 clear now we've seen this suffix array could be useful but how do we get it uh that we still have to find out one option is compute the suffix tree and then read off the order of the leaves uh but we're trying to avoid to have this these complicated construction algorithms for the suffix tree H so it would be a bit uh a bit disappointing if we had to construct the tree as an intermediate step uh instead we can go more directly by the definition the suffix array needs all the suffixes in sorted order so we might as well produce that by sorting and we could just use any of the general purpose sorting methods uh unit three is as high um that's trivial to code up you just have a comparison functions for Strings that's usually built in into libraries anyways so this takes takes two lines of code uh unfortunately this is not so great because the comparison of any two suffixes could take a linear time uh as often if you take a boring text like uh everything is a um that gives you the the worst case in this for this stupid algorithm um if you if you're not careful then um that extreme case for a text Will Will usually screw you over and so while it's

15:12 easy to code it's it's worse than quadratic in the worst case so uh that's that's not not quite so great um and indeed we can do better we can do even better without going very far into the the world of suffixes the first thing I want to show you is just a general purpose method to sort strings that's better than that at least on average um before we get to that um another short connection that uh it's worth

15:55 making uh this time it's unit unit five that says high that was the bir wheeler transform and uh it's worth is worth pointing um I want to I want to point out this says very easily so it should be a a trivial algorithm both fast and conceptually super easy um that's important here because if you strike that out uh it's it's possible either way uh by just Computing it from scratch but that's not that's not the uh what the question is getting

17:39 we pass the magic 50 so there's a roughly evil equal not evil split between between options two and three uh well now now things shift okay anyways um the majority is right so here it's true that you can compute the the burs wheeler transform from from the suffix array or from the suffix tree uh the reason for that is if you have uh let me show show you uh the connection so this is a slide I I just borrowed back from uh unit five remember what the bur wheer transform was doing is it takes all the cyclic shifts and sorts them and then it takes this last column that was the bwt um and to uh to compute that uh not when we do the Sorting we never have to look past the dollar symbol because the dollar symbol in all of the cyclic shifts occurs at a different position so there's no way we'll ever get with our comparisons behind that we would only get behind that symbol if there was the same dollar symbol in both strings that we're comparing but that can never happen here here so in a way sorting these cyclic shifts is the same as sorting just the suff ex this ah you don't see the slides didn't switch back

19:16 here uh that was what you were supposed to see um the Boris wheeler transform takes all the cyclic shifts sorts those and takes the last column that's exactly the slide from back then and uh if you compare any of the two cyclic shifts then you always stop comparing at the dollar symbol or earlier you never go further because the dollar symbol is never aligned at the same position and so sorting these cyclic shifts is the same as sorting the suffixes the order will be exactly the same and so um if we have the all the suffixes sorted how do we get the bwt the Formal Connection is is here um I can take the position that is in the corresponding entry of the suffix array and now I would I would want instead of the starting index I want the letter that is wrapped around and in the last column that is actually the character that comes one before that character so what I have to do is I subtract one and then look in the string or in the text maybe it should be uh okay it was it was called The Source text in unit five so uh you look at the position that comes before that starting pos position of the suffix um that's how you can compute the

20:42 bir wheeler transform in linear time from the suffix array now the other direction seems unclear um just because you have these these characters is is not at least not very easy to figure out what the order of the suffix is should be

21:10 um yeah I want to briefly show this this sorting algorithm there's no code it's just an example so we can go over this fairly quickly uh it's not a it's not the most Central Central thing I just want to show before we go to the more sophisticated algorithm tomorrow uh for many cases you get with a simpler solution um a fair bit uh so think about the general problem you're given a list of of strings like these uh how would you sort them efficiently what's not so great an idea is to use comparison based sorting uh say merge sword or quick sword as a blackbox and whenever you not need to compare two strings you just do the comparison from start to beginning to the end the reason that's not so great is if the strings agree on a long Common prefix you repeatedly scan that long Common prefix and you pay for that each time whenever you do a comparison so the extreme case is suppose all the strings start with some long prefix that is the same for all strings and then they differ say you're sorting URLs and they're all within the university domain then you would have that easily and so there's an easy way to do better than that and that is based

22:25 on quick swort but uh it takes Vantage of the fact that we're sorting strings and it works like this we uh we pick a pivot element that's always in quick swort but we'll only look at the first character in this round that's why these are highlighted so the pivot character tells us there's words that start with a character smaller than this character and those that start with a letter larger than that character and those that start with that character that's why it's called fat pivot because there's a a partition that uh has everything that's equal to the pivot according to the first character right these have a a starting character smaller than S these larger than S and these have S now the trick is for all those that start with an S I know that they all start with an S so no need to look at that s ever again instead I'll just remember for these strings the first character is definitely the same start looking at the second that's the main trick uh the way the example would continue here you pick a pivot okay it's this tiny example so you just have these two sorted here it's more ex more more interesting the pivot says I have H as the second character so I split by the

23:44 second character into those that have a character before Ag and after Ag and those that have Ag and again for those that have an AG as the second character I know they have S as the the first two characters for all of them never look at them again

24:08 okay uh in the last example we have the degenerate case that they are all equal so I just read over all the t's never look at them again and there's no strings that have a a smaller or larger

24:23 character these are done these are Sub sub problems of size one for these um I pick another pivot and I again have this degenerate case they all have the same next character so I just advance and never look at the E

24:48 again uh for these I have some excuse me some that are smaller um no these all have e and one that's larger so again I never look at the E again and here I just Advance one more because the algorithm doesn't see it yet but of course the strings are just the

25:11 same uh one more round here okay L I have two that start with L and three that are smaller I guess you see how this how this continues now uh the trick with all of those okay these these continue for a while until they discover that indeed the two strings are the same uh but if you if you Analyze This globally you never read for two strings if they have some shared prefix you never read that shared prefix twice you only read it once because uh you always remember if you go into this middle round this middle partition you remember that they were the same so when you discovered once that two strings have a common prefix you're not going to look at it again

26:02 uh that's pad pivot radic quick sort if you want to see the details and code and so on in in uh more slow pace uh it's in the red book that we used for for other units um I I'll skip the details for the code here so you don't need to know that part uh you can show that if the texts are somewhat random this is uh a very fast method um is also very simple to code and work well for for many types of texts um it's still fairly slow if your text is completely degenerate if your text is all A's you would always have this middle partition and you would read through uh the entire text so it would be quadratic still um but you've reduced it for uh for many more interesting cases where it's not suffixes of a text this is a good

26:59 method now for the concrete case that we're concerned with sorting the suffixes of a fixed text we can do much better even in the worst case and for that we'll work we'll have to work a bit harder and we won't do that tonight um but that that's what's coming up