Video 6-6: §6.5 Suffix arrays

0:00 <Untitled Chapter 1>

0:04 in this next subsection i want to introduce suffix arrays they are very related to suffix trees but much much simpler both to understand and as we will see to compute uh nevertheless they capture the essence of what makes the suffix trees magic and uh they will eventually solve this problem of constructing suffix trees in a very elegant way by using suffix arrays as an intermediate result so let's see what suffix arrays are about

0:05 Suffix Arrays

0:44 one observation that we can make in a suffix tree is if uh so one assumption here is that i'm ordering the edges going out of an internal node by the lexicographic order of the first character so here the dollar is always the smallest in our alphabet that comes first then a then b then n and the same is true at at every node b comes before n if i do this and i look at my list of leaves i notice that the leaves list the suffixes of the text in sorted order their sorted lexicographically dollar is the smallest then comes a band then a n and so on and so forth okay that's a simple observation um but what we'll do now is essentially ignore all this part on the left throw away the entire tree if you want and only keep this list of sorted suffixes that is the suffix array more specifically we store um an array l and uh i tend to think of l to stand for leaves that's the leaves of the suffix array and remember um the uh okay let's let's do the algorithm first but uh remember that the leaves actually store a number not the string really right this would be i don't know whatever the last position is a nine

1:53 Suffix Array

2:25 so these these would actually store the starting index of that suffix and not a string which also means l is just an int array it's an array of numbers okay much simpler than a tree in terms of how to represent it

2:44 what can we still do if we don't have access to the suffix tree but only to this array of leaf entries the the numbers in the leaves in in left to right in in well left to right if you draw the tree in the normal way uh top down in my way of drawing it what can you do if you just have the sorted leaves it turns out that's definitely enough for string matching because we can use binary search for a pattern suppose we want to find if the text banana band contains anna the spanish anna uh how would we do this well we do a binary search for anna where we fill it with dollars in case of doubt and well how would this work we would probably start comparing here

3:08 Binary Search for a Pattern

3:36 anna is smaller than this because the first character where we have a mismatch is the n and dollar comes before that so initially we had it's somewhere here now because it's before that we know it's somewhere here and then i don't know how the type breaking is implemented maybe this is the next to compare so we compare this with anna so here the result was search in the upper half here the result is now comes after app so we go down and that means we have narrowed down the interval to these two nodes and maybe here would compare with this next and then and actually comes after this and then we're left with this with this single position and now what we do is just check if anna is a prefix of the suffix at this position

4:49 and if that is the case then we have an occurrence of the pattern and if not we don't have an occurrence of the pattern and so with a with a simple binary search we can solve the string matching problem um so uh what we need for this the complexity of doing string matching with a suffix array is log n that comes from the binary search we have to cut the

5:23 the range in half log n times or roughly log n plus 2 for rounding and each of these comparisons whenever i ask does uh is anna smaller lexicographically than than this text each of these checks needs actually m text com uh character comparisons because we have to scan from the left or in the worst case m character comparisons because we have to scan the pattern of the text uh from the left

5:57 that right all right so we can search for occurrences in the text and another little comment that i want to make is you can actually find all occurrences in the text just as easy

6:21 there you just do two binary searches and uh for the second one you use anna with i don't know another symbol that is bigger than everything in the alphabet

6:44 so it's it's just you invent you tr you search again in this in this first binary search you pretend that the next symbol of the pattern is coming before all the actual symbols and in the second search you pretend it's coming after all the symbols in the alphabet so what you will find is the first position and the first search ends here and the second search ends here and that gives you a range and all the leaves in that range if it's not empty start with anna so it's it's even in a sense it's much easier with suffix arrays to solve these variations of the problem find me the first match all matches these are these are fairly easy to do because you can conveniently find all matches grouped together like this

7:51 The Suffix Array

7:52 so we define the suffix array as as this leaf array so here it is as i said before the actual uh value stored in the suffix tree is not the string but the starting index so the suffix array is just this list of numbers and the arth entry in the suffix array is the starting index of the rf smallest suffix in in lexicographic order okay that's the suffix array let's see if you digested this uh where's my question

8:39 a multiple choice you can take as many answers as you want and some of these are correct all of these are correct i'll wait for the 25 answers again i know these these questions need a little extra time because it's a lot of text to read

10:07 okay 24 one more to go and then i can tell you which ones are the correct answers there we go so here are your votes and as always let me lock it now so uh

10:30 the first statement says that the suffix array lists the start indices of the leaves in left to right order now left to right as i said before if you draw the tree in the normal way and not tilt it to the side like i did but that's that's correct um if you order the children of every internal node in the suffix tree so that the edges are sorted as well uh you have to do this in a try you don't usually insist on this the tree doesn't have to be ordered in that sense but for this correspondence to hold it it's necessary

11:12 this suffix well t starting at l r is the path label in t to the leaf storing r that's not quite correct but a slightly different statement is correct it's this is the path labeled to the earth leaf in t in left to right order the leaf storing r well that's the uh suffix starting at position r that's a different beast okay these these can sometimes be the same but they're not in general the same um different way of saying this uh t l r so the suffix of t starting at position l of r is the r smallest suffix in lexicographic order that is correct that's the same as as saying the as the first statement if you want

12:11 the next one's an interesting one it's not correct um if if more needs it means strictly more in terms of the theta class if you ignore constant factors then the suffix tree and the suffix array need the same amount of space uh the the difference is only in the constant factors but the factors are substantial so in a sense here um the theta classes are are betraying us in in this instance they don't really give us um the interesting distinction here uh but it's true uh the two have the same theta class in terms of space um and the last question l and t well one of them suffices to solve the text indexing problem that is true because we defined the problem as supporting efficient searches for patterns you can be what efficient means maybe you can be catholic about this but i marked it as correct because a running time of log n times m is is very efficient compared to the n times m log n is much much smaller than n so this in practice is very efficient okay

13:42 uh if you have more questions about the definition then please use the the q a other than that um yeah keep keep in mind this this definition here the one that also most people voted for think of the suffix array as storing [Music] the where's the what's the our smallest in in sorted order i'll later have another picture how to remember these things we'll we'll come to that what i want to talk about next is how to construct suffix arrays uh it's fine we can if we have the suffix tree then we can just read the uh the leaves from the tree but i mean hold on we wanted to compute the tree and didn't know anything except my statement that there is a magic black box that does it but we want to dig into this so relying on suffix trees to construct suffix trees that sounds like it's not going to work

14:30 How To Construct Suffix Arrays

15:05 but we now have a much simpler object instead of this complicated tree we just have a sorted list and sorting is something we know how to do so we could just take all the suffixes of t put them in an array and send that to your favorite library method for sorting use the java sorting method that's a handful of lines of code very easy to do and it's for small examples not even that bad but it can be very slow and the reason is that if this is a general purpose sorting method it relies on pairwise comparisons and comparing two strings essentially means comparing them letter by letter and in the worst case you have to scan the entire two strings before you find uh which ones smaller and well if if they differ and if so um which one is smaller because we're talking about suffixes here and we always have the end of word marker they would always differ they cannot be equal we know that but because suffixes are potentially as long as the text or just slightly shorter this comparison is very expensive

15:23 Java Sorting

16:23 so we might need n squared login time in the worst case and that is that is a bit slow now what can we do uh we can do much better by in two ways the fancy version that we will just start looking at today and finish off tomorrow but we can also do something that gets us a fairly long way and is much simpler by just exploiting that we're sorting strings and not arbitrary objects and this is what i want to talk about first

17:07 i call this fat pivot radix quicksort that's a fancy name for a fairly simple idea you remember a quick story quicksort was essentially taking a pivot element and then you take your list and partition it into classes that are well by comparing with the pivot you can have elements that are smaller and bigger here we do something slightly more slightly more refined we don't split everything into smaller and bigger we split it into three groups and we look at just the first character of the pivot so this first list is all the strings that have a smaller character at the first position than the pivot b and a are both smaller than s and the last list is the same thing but now uh with the strings that have a letter that's bigger than the first of the of the pivot and then the middle list is all the strings that have the same first character as the pivot and this is all that we do we never in this radix quicksort we never go beyond the first character we don't do a full comparison until we can decide it but we allow to keep these these uh equal results for now and fat pivot just means this is essentially the fad pivot partition these are all equal

18:42 to the pivot if you only look at the first character and the rest is just as in quicksort you recurse with the same idea keeping track of which position you have to check next so the important point here that's why i grade the s out the important point here to remember is in this middle partition these were all the strings that had the same character as the pivot that also means they all have the same first character so we can ignore the first character for now we know it's equal they have a common prefix and we start comparing with the next character okay let's see how this continues

19:25 we'd have this little tiny list uh we do the same process with this pivot so uh well these are obviously in the wrong order sorting is is hard uh apart from that um this is an easy case because um we end with two lists of just a single element so we don't have to uh further recurse now we split the second list this is more interesting we pick the pivot sheet and we're looking at the second character now so there's a couple of strings that are have a smaller character than h there's one string that has a bigger character than h and there's a couple of strings that have the same character as h and now look uh what happens here is in this list well we as human we see these all have the same second character but the algorithm doesn't know that for now it only knows that they all have a character that's smaller than h but we still have to compare this so we're still looking at the second character in these in this string in this uh sub list whereas here this this is the partition that had the same character as the pivot so here we know these are all h so we can advance to the next character in

20:37 this list and again in the last list something funny happens this happens to be the same characters the same strings but the algorithm doesn't know it it uses the next pivot and finds that the first characters are equal so it only produces the equal partition but that's where it stops then the next round of recursive calls splits the non-singleton lists further up so we have a pivot here and it turns out as we've seen all of these have the same first the same second character so they all just move to the next position there's no splitting going on

21:26 and for this list we have one that's bigger and the others move on to the next um [Music] i think i made a mistake this one this should be this should be done we're looking at the l and we're looking at nothing here so uh sorry i goofed in this example this should have moved on and in the last list we again find only equals so we move on to the next position and here we do this one more time we partition around this there's a couple of strings that have a smaller third character and there's some that have the same so here we move on to the next position uh and here i just uh i should have omitted this uh this one step but now uh comes the right version so we move past the last character in the pivot really so this is we fill that with dollars um in that case and um well again

22:32 this should have been here i don't know some something went wrong on the slides i think and uh with these i'll i'll fix the slides for that but um so here we scanned past the entire strings in both cases that's where we notice that the two are actually equal but we have to scan the entire strings for that um and uh one more here so here we have to um

23:00 we have to continue uh with the pivot again we find these are all the same so we move to the next position in the string same happens for these and here we split off the the two equal ones go here and then um

23:22 that's a bigger one it's a singleton list so we don't have to further partition and well in this case we split one string off and then these two are equal but the algorithm doesn't know that yet it has to continue scanning through the entire string and only at the very end it will notice that these two are the same so what we did is quick sort but we partition only on the d character and initially d is zero but then it gets bigger in the middle partition we do three we create three segments those strings that are smaller equal or larger in this div symbol and recurse where in the middle recursion call we increment d so in code this algorithm looks looks very very similar to quicksort and is very easy to code an important observation here is we never compare equal prefixes twice if two strings have a common prefix we will compare that we will have to find out that they have different they have this shared prefix but we never scanned them several times and this is what made the the direct call to a string method slow

25:04 um [Music] because we never compare uh this uh the same well the other way around for a standard sorting method we repeatedly compare strings and it could happen that we compare the same shared prefix many times and we have to scan over this many times

25:37 okay so if your video has stopped refresh but if you can hear this then it hasn't stopped so it's not very useful that i'm saying this what we can say about this fat pivot radius quick sword is that um

25:56 for a certain model of strings um if the strings are are random then we only need n log n time instead of the n squared login that the standard sorting method might have in the worst case it's very simple to code and well this this expectation is about the choice of pivots but it works for all texts so

26:36 if you choose random pivots you will usually see expert behavior in in this realm it's very simple to code it's very efficient for sorting strings um even if they're not suffixes and we can also apply it to find the suffix array in n log n time that's already quite good because we started with something quadratic reducing that to n log n gets you most of the way um and uh because it's so easy to code it might actually be a method of choice if if it's not a performance critical application uh but still um sometimes this is this is still a bit too slow and from a theoretical perspective it's more time than we than we need because we can actually do linear time and uh this is what we'll look at in the next subsection