Video 6-6: §6.5 Suffix arrays (part 2)

0:00 <Untitled Chapter 1>

0:02 Putting suffix trees on a diet

0:04 we already looked at this last time so just to repeat the definition a suffix array is just the starting indices of all the suffixes once you sort the suffixes in lexicographic order and one way to get that was using the suffix tree if you take every note and order the children the child edges alphabetically by the characters and we know there's only one Edge for each character so that's easy to do if you do that for all the Nerf for all the notes then in left to right order or here top down for the leaves you get the suffixes in LA in sorted order and it's convenient to assume here and throughout that this dollar symbol the end of word marker is smaller than all the real characters

0:58 then you get this sequence of numbers and that's the suffix array and I I hope I could convince you on Monday that uh some things may be lost if we forget the entire uh tree topology on top but some other things are not lost at least we can still find exact matches in the text of an of a pattern with two binary searches and the runtime for that is no longer completely independent of n the size of the text but it depends on login only which is for all practical purposes almost almost as good uh in this universe everything's finite so login is finite that's an empty statement but log of the number of atoms in the universe is probably still 300 and that's a sizable number but a manageable number compared to all the atoms in the universe okay let's see if you uh follow on this one so last chance to vote on the attendance code and then it's time for the suffix array

2:30 so I'm waiting for it for 29 ish maybe 25 answers on this at least similar question has we had for the suffix tree but now the suffix array it's it's just about hammering in the definitions I'll I'll leave you a moment of Peace for answering

3:59 hello [Music] okay as always this room I will eventually show you now it's reloading see the right answers now again resist the urge to move around too much let's go through this uh briefly so that we're on the same page so this is about the the suffix array and the suffix tree in their relation they're both built on the text T which has n characters and remember we always assume for suffix tree that we append the dollar sign and I'm assuming that the alphabet symbol the alphabet size is is constant

4:06 Clicker Question

5:06 then L essentially lists the the contents of the leaves in left to right order that's if we draw the tree in the normal normal computer science where root at the top and left is the smallest Edge smallest child Edge and so on all the way to the right if you keep doing that and then go left to right through all the leaves you find the suffix isn't sorted order and so it's the indices of the starting the starting indices of the suffixes and those are stored in the suffix array

5:42 now let's decipher with this one is um it's the text starting at the RF entry in L so it's the suffix in that position and what is that it's a path label from the root to some Leaf in the suffix tree for sure because it's a try overall the suffixes right

6:07 and it's if we take a together with this uh it must go to the R Leaf or the the leaf of index R remember we start with zero uh but it's not necessarily the leaf that stores the number r it's the inverse permutation another way to say the same thing if you take the suffix of the text that starts at this position we have this shorthand notation for that then the fact that this is the index R in the suffix array says that the Earth's smallest suffix of t

6:45 let me do this one first uh L and the text together are enough to solve the text indexing problem that's what I've just shown you with the binary searches now the tricky one maybe e and uh here the important bit is in terms of big Theta classes for a constant size alphabet also suffix trees are linear space they're Theta of n space but Theta hides a constant Factor and that constant factor is much larger for the suffix tree than for the suffix array where it's really one number for each Leaf one number for each position in the text

7:30 so anyway we shouldn't be too ambitious the suffix array is still linear space as was the suffix array but the constants matter all right how can we compute the suffix array an easy option is we take the suffix tree which we know there is this magic black box that somehow constructs the suffix tree so we might just use that and we could do a traversal so you start at the root and you do that first traversal whenever you reach a leaf you will actually visit those in left to right order if you follow the alphabetic order in each node and that would give you the suffix array however it kind of defeats the point of having this this sleeker data structure if we first have to build the fat suffix tree to get to the suffix array uh and just by the definition of the suffix array it's now much more transparent what we have to do if we build this from scratch all that we need is all the suffixes of the text in sorted order and sorting is something we know how to do so it's trivial to code by uh just if you if you just do it that way create an array of all the suffixes and pass it to your favorite sorting

7:41 Suffix arrays - Construction

8:52 algorithm that's trivial to code because the Sorting algorithm will be implemented wherever you code it but that alone will not be fast uh there's this several problems with this if you do it this the naive way then the array of suffixes would be an array of strings each is a each as a copy of the suffix so that already uses quadratic space not that great now it could be slightly smarter by um noticing if you store the text once you can sort indices starting indices of suffixes instead of copying out the strings that would avoid the space problem but you still have to do the comparisons so whenever you ask the Sorting algorithm uh to compare two things to sort them it would have to go all the way through the two suffixes until it finds um a distinguishing character and that in the worst case think again of our degenerate text where everything is just an a that's often the the worst case in this uh for such a text the comparison between any two suffixes takes as long as the shorter suffix is long and so that sorting would give you N squared login time so that's that's uh way too slow to be interesting

10:23 but that's very pessimistic I will say that most of the time you will not see this quadratic Behavior it only happens if the text is sufficiently self-similar so for standards types of inputs uh what was the standard type of input for many types of inputs it wouldn't be that bad and so it's it's a first start maybe it's it's good enough for some depending on the application it might be good enough

10:54 now if you know this module you of course guess that we can do better and we will look at that the first way is to still keep the Fairly basic sorting algorithm and do a general purpose sorting algorithm but one that's Geared for Strings so it's general purpose in the sense that you can sort any list of strings but its special purpose in that it is string stepper sorting we haven't talked about that in unit 3 because I felt that unit was long enough in unit 3 everything was about some abstract object you're sorting things and you don't know anything more about those apart from the little detour on Integer sorting but if we sort strings with the usual lexicographic order there are a few tricks we can play to speed things up and so one one such trick is what's used in in this algorithm fat pivot Radix quicksort it's at least um I like to call it because it's a bit more more graphic it's a quick sort algorithm I'll comment on the second part in a moment the fat pivot part just means um if you partition with quicksort remember you pick a pivot element and then there were two options an element could be smaller than the pivot or larger than the pivot now actually

11:05 Fat-pivot radix quicksort - Example

12:22 there's a third option right it could be equal to the pivot in unit 3 we kind of treated that case as don't care you can put it left or right I don't really uh obsess about that and we assume that the keys are distinct most of the time now if you expect to see many equal elements it is actually smarter to say we do a three-fold partition the things that are strictly smaller than the pivot go left strictly larger than pivot go right and in the middle we collect all the equals all the elements that are equal to the pivot and that gives you a fat partition a fat pivot segment in the middle that you can exclude from recursive calls hence the name

13:08 was for sorting strings we'll combine that idea with another little trick which is we only compare the first character of the strings in each step but we remember which character we're looking at I'll just show you this on an example I think that's the uh the quickest way to grasp the idea so here's um a collection of strings as I said these are not suffixes of some text that's just some strings and we I highlighted the very first character of each

13:40 in the first partitioning round we pick our pivot element and for the partitioning you only look at the first character ignore everything that comes after that so we partition around s so there's b t etc those go before s after s and there's many occurrences of s itself so if you do that you find there's only two strings in this list that are starting with something smaller than S and two that are starting with something larger and the rest is actually starting with s so we have three recursive calls because these are equal to the pivot according to the first character but not everything and we have two recursive calls here now the difference for this middle recursive call is we know that they start with the same character so why would you want to compare that over and over again it's not useful instead you remember that you're now looking at character at the correct red index 1. instead of zero

14:39 otherwise the recursion is s in quick sort so again you have this little sub problem you pick your pivot and you partition according to this pivot into the three classes but one is empty in this case and once you have Singleton classes you can stop you don't need to recurse further well this one you again pick a pivot um the second character of this one is H so now the partition is everything that has a character is smaller than h everything that has a character equal H at position one and everything has a character bigger than h okay and again for these for these middle ones we know they all start with S and H no need to compare that over and over again

15:28 for the last part we have a recursive call and then here you see some potential uh for improvement Maybe um we partition and we find both are in this fat pivot partition they both have the same second character and of course you see that the strings are entirely the same in this case but the algorithm is blind to that

15:50 that's the second round and we do these ones don't need further recursions they're already singled elements same for this one we partitioned further we pick a pivot we look at the next character to look at um and that's that's the second character in this point position still and now again everything has the same character so they all stay in this middle partition but we remember that they all start with SE so that we don't compare this over again in this one we do have some partitions there's the ones that are smaller and the one that has an e at the third position

16:34 uh sorry sorry I told you garbage so there's three that have an e at this position and one that's bigger right so you have to keep you have to look at this to get the partition here okay it can be confusing the last example you pick this as pivot and again so you compare the the H and it's the same in both so you have another another round of this everyone stays in the middle partition

17:04 okay but now I I hope you get the game so we pick a pivot partition according to this character gives you three that are smaller and two that are equal where we advance to the next character same happens here if we run out of a string we fill it up with this end of string marker which is smaller than anything else that's the same as we always did so these two end up being equal to the pivot that's these two and shells is bigger

17:34 and for this in the last round we finally found that the two strings are really equal maybe we need another round with comparing the two dollars I left that out here I think that's it's not quite true

17:53 and here we reach the end and here and uh with this one you would have to go all the way to the end of the strings seems a bit wasteful but that's that's how the algorithm discovers that the strings are equal

18:10 if you want to read this in more detail including code Etc there's that's discussed in the book question they were thinking about women with this matter to sort instead of some string but some integers but we right separate integers into different bytes like 10 different that like six digits yep

18:38 yeah so the question was can we use this method also to sort integers if we just effectively treat an integer as a string right if it's written in decimal or pick your favorite Radix uh definitely you can absolutely do that it's not such a bad method for that as well um you have to be you have to play a bit around uh with what Radix you pick

19:09 well would it work if you pick a to match up something like what we discussed at the time counting sword or things like that you would have to pick a really big Radix

19:25 um what you could also think of is replacing this partitioning round with one round of counting sword then in a way where we're doing one round of counting sort but split over several stages so this this the partitioning according to the first character or first digit is partly done here but then here's complete but here we split it over the next round again so we now have to combine this and this down here to get the full distribution over just the first character so quicksort here needs several stages counting sword could do it in one I mean the short answer is yes you can use that method for sorting strings um and working out exactly how well it is how well it does for that depends a bit how you choose the Radix Etc uh but it's yeah it works fine it's not too hard to code and doesn't use this humongous extra space that counting sword used at least the way we presented it now if you code this up you have apart from the two parameters of quick sort for what's the left and right endpoint of the current part segment you're sorting you have a third um parameter which is the position in the string that you're comparing next and you can only really make use of that

20:55 if you use the fat pivot partitioning where you produce the third partition now if you think about the methods uh by remembering where where prefixes were equal you will never compare two characters that are part of an equal prefix equal between two strings twice because as soon as you detect that they are equal you exclude them for the next partitioning round and so uh in a way the costs for sorting this is a combination of two things um it's on one hand it's the sum of all the common prefixes so that would be the cost to insert all these strings into a try and you can show that that's that's basically the best you can do you have to detect all the common prefixes and the second term is um a cost that comes from the quick sort style recursion because you're not using counting sword in the partitioning stage and you can prove things like like this statement which is explained in a bit more detail in the book if your strings come from a random source so you have random strings where each character is just randomly Chosen and they're all independent Etc uh then you can show that this the second part the quicksort contribution dominates the rest and you basically need as many character comparisons as

22:24 standard quick so it needed comparisons to sort a list so the fact that you're sometimes comparing um these common prefixes vanishes in this case now in a way that's because for random strings you don't expect to see long Common prefixes in many applications and for sure in some suffixes if we're sorting the suffixes of one text you will sometimes have these long Common prefixes so it's something to worry about that's um that's one thing and for sure you can't expect this to be better than n log n because we're still operating on comparisons imagine the strings are just one character long then we don't really use the fact that the characters are integers or anything like that so we're still in the realm of the comparison based lower bound uh so we're definitely in the end lock end regime and usually a bit worse so even if you assume some some Randomness on the strings now in terms of practical applications I would usually go with this method and give it a try unless your string is really pathological this would do well but there's two reasons to look further one is sometimes you can't guarantee you don't run on pathological inputs and second it's about uh the algorithmic possibility can you do it in linear time

23:58 the answer will be yes and so it's at least from on the intellectual academic side um I think it's not satisf satisfying to to stop at this point question

24:30 so the question was uh will this be quadratic for for the application on suffix sorting the answer is not usually it can be so the problem will again Be Strings like this a to the n if you have that's what I would call pathological inputs if you have that then there's a maximal amount of long of common prefixes and the poor sorting algorithm without knowing that these are suffixes of one text it has no chance of figuring out the order without finding all the common prefixes so in a way it's best possible for that but still for this one it would be quadratic

25:16 but for most other texts where you don't have these massive common prefixes it wouldn't be quadratic so there's there's many instances where it works fine and the benefit from what we've had before well okay I don't want to go over the animation again I started the section on suffix sorting saying oh you could just use any general purpose sorting method uh the difference between between this and the general purpose sorting method is that this one at least detects the common prefixes only once whereas the other ones might scan it over and over again so you might have a lock Factor difference something like that