Video 6-6: §6.5 Suffix arrays

0:00 Intro

0:02 in this section we'll talk about suffix arrays which are a modification if you like a simplification of suffix trees and we'll see how they eventually will be able to replace the suffix tree and be a little more a lightweight alternative to suffix trees but offer the same same kind of functionality eventually

0:30 Suffix trees

0:33 so the goal is to put our our suffix trees on a diet here's another time a suffix tree and uh uh it's it's for this string banana band that we've seen before so it's the same suffix tree just drawn slightly differently what i want to point out is for each note i paid attention to sort the outgoing edges alphabetically and that was done on purpose in the suffix tree there's no real order on the edges it's a tree right so there they could go either either way it's not even it's just up to us how we draw it but for now for this section i want to insist that the child links are drawn in alphabetical order if you allow me to do this and at each and every node in the suffix tree you notice something convenient if you read the leaves top down they appear in sorted order as the strings it's the suffixes in lexicographic order and so uh what about just getting rid of the tree and only keeping this order of the suffixes around it turns out that's the suffix array and it turns out that's enough for a lot of things even though it might look like you're throwing away a lot at first sight so the idea is we only store this array

1:42 Binary search

2:08 and remember that this array is really just an array of numbers we don't actually store the suffixes as strings we store the starting index but one step back if we don't have the tree let's do a simple check if we can still do something useful and what was the first non-trivial thing we did with suffix array suffix trees finding a pattern in a text for which we have the suffix tree so let's try to do the same thing if we only have this sorted list if we're looking for a pattern like anna what can we do with the sorted list well uh we can do binary search okay and so that's that's the approach that we can take here so if i do binary search i would probably start comparing in the middle now did i round up up or down not so clear maybe we start comparing here so i compare this text and anna because anna stops early this one compares bigger so i would go up right i'm trying to find the insertion position of anna so i would jump into this half then the middle would probably be this one n and the dollars a dollar comes before all the characters notice that i put this here before the characters so we

3:32 have to be consistent so this one comes before anna so we have narrowed down the search range to this one now um yeah i probably should have excluded this one here which means i should have compared it to one further up to follow our code um and now anna is bigger than that because

4:07 sorry it's smaller than that because it stops early so i you can imagine that anna is also terminated by a dollar so here we go up and oh sorry this is a band so i was talking gibberish so it's this one comes before anna so we narrowed it down to these two i would compare with this one and and dollar comes before so i would narrow it down to this one then i compare with that one and anna stops early so i would go up so i found the insertion position here that's where anna would have been inserted if i wanted to include it in this list that's what binary search gives you okay now we could do um a second search for

5:10 for anna and with a different dollar letter i don't know pound uh which comes after all the characters so you search twice you search for the pattern with a termination a dollar symbol like before that comes before all the other characters and the second time with one that comes after all those in that case you would find its insertion position here

5:39 so two binary searches give you two positions and the range between those two positions is special because that range every pattern starts with anna have a suffix so uh we found all the occurrences of anna and is even slightly more convenient we found a con a compact representation of all those uh matches because we found a beginning and an end index in the suffix array where all those occurrences start okay so it's even slightly more convenient than in a suffix tree

6:41 okay all matches of p in t and so we're back to exact matches right forget about the approximate matches that part's over at least for now so i can do two binary searches in the sorted list of suffixes and that gives me the occurrences of a pattern in the text so we can still do something useful even though we threw away most of the suffix tree we just kept the sorted list of the leaves

7:11 and so if we do that if you analyze this algorithm that i just sketched you uh we need log n plus 2 that's just the the worst case comparisons between the pattern and one of the suffixes and each of these comparisons takes up to m symbol comparisons because i have to compare strings character by character so that's the the cost for doing one binary search and we do two of them so you multiply by a factor of two but so you can still find all the occurrences in so we can still do pattern matching string matching in

8:12 log n is not constant but it's way better than n so this is still very useful and there are tricks to improve on this but let's for now stick with the simple one okay i said this before but let's officially state it again that thing is the suffix array

8:33 it is the starting positions of the suffixes as they appear if you sort them lexicographically and it happens to be if you have the suffix tree around and you draw its outgoing edges with the alphabetic order then it is the order that you see the leaves the more conventional way to draw the tree was top down and then the l array would be written from left to right finding the leaves in left to right order so that's that's how you would normally see it see it drawn

9:20 let's see what you can draw in conclusions from this definition again an awfully long list of statements so i'll probably have to give you a minute i'm sorry guys i started the wrong question right

11:08 sorry that was one early one later we haven't talked about the inverse suffix array have we were you very confused or not so much i mean this is this is what i wanted

11:38 you did reasonably well on the other stuff even though you didn't know what we're talking about another way of saying my teaching has no impact right i'll go by the other the other implication that you're just brilliant

12:57 it looks like many people are done so i'll leave it open but i'll show you the uh not all are correct but everything got some votes ah it's a tough one um let's go to those indeed most are correct indeed so

13:34 right uh what can we say about the suffix array first of all uh l is l is indeed the list of starting indices that are written in the leaves as you see them if you go from left to right in the tree if you draw the tree like every normal computer scientist does with the root at the top and growing into the ground well we got used to that i guess and then the leaves come left to right uh this quest this is essentially the same as this just with the last part changed so let me say the correct thing and don't repeat the wrong one if you want to go to the earth leaf in t the earth from the left so first second and so on or well zero first second and so on then you will see the suffix starting at position r so at position l of r in the path from the root to this leaf okay maybe let me say this again if you take some rank r that's the position from the left of the leaf you're looking at some leaf here it starts at some position i but it is the earth from the left then l of r gives you i and i is the starting index of that

15:01 suffix in the text which means text starting at that position until the end that's the suffix that's what you see from the root down to this leaf okay that was what we said before if you take the suffixes and you sort them lexicographically you get them in the order that they appear in l so l0 is the index starting index of the smallest suffix l1 is the next l2 lf2 is the third and so on and so forth

15:41 you can use the suffix array by binary search to find patterns uh this one is a little tricky and i smuggled in to make it a little more clear if the alphabet is constant it's quite clear even in the suffix tree you would only need at most sigma pointers for each node so it's still the space is linear in n or in general n log sigma is doable with some disadvantages and that's the same for the for the suffix array it also needs space n but the difference is in the constants the suffix array is just a list of numbers whereas the suffix tree is this pointered structure where each node has sigma pointers in the simple representation and so it's a it's a much bigger constant factor and even if you play with this you don't get this completely down but if you just look at big theta classes the two aren't different the space is the same for those two so that's why sometimes these asymptotic notations are useful but you have to take them with a with a pinch of salt they are not an exact representation this ignoring constant factors is sometimes not good enough

17:00 Suffix tree

17:03 so we know what a suffix array is the list of starting indices in like in lexicographic order of the suffixes leaves us with the question how we can compute them

17:18 if we know the suffix tree i just told you if you draw it the right way all you have to do is traverse the suffix tree and note in what order the leafs appear but we are starting we started this section trying to avoid to build the suffix tree in the first place so that's not really that useful but it's doable the other option is we reduce the problem from this complicated tree on strings to just sorting the suffixes sorting is something we know how to do right so you could just do literally that construct all the suffixes of a of a tree of a text and sort them with whatever sorting method is provided by the programming libraries the downside is that comparisons now are not a constant time operation but they can be quite expensive you have to compare strings by comparing them from the beginning to the first differing positions and in weird cases like if the text is is all a's

18:25 then you would potentially need a linear number of comparisons uh simple comparisons for each comparison which of two strings is lexicographically smaller and so that would be would be even worse than the simple way to construct a suffix tree so that's not not that great at least in the worst case it's not an option

18:47 String sorting

18:53 but we can do better in in various ways we'll look at two two things first is a better method for sorting strings specifically suffix sorting so the first thing is really generic for strings and you could use it to sort an arbitrary list of strings so it in a sense would have belonged into unit 3 but i felt it's it's more useful here where we have a use case for it and the second is really exploiting that we're not sorting an arbitrary list of strings these are exactly all the suffixes of one text and that will help us at the end but let's first look at this because i think it's uh it's insightful and is actually quite good in practice there's still some worst case problem but you don't often see this unless you run on a on a text like this so that has a caveat up front if the text is like this don't use the next method or any reasonable text that doesn't completely repeat itself all the time the method on the next slide might be a very simple to implement and use an useful way to compute the suffix array

20:17 and if you have to sort strings in general use the next method it's almost always pretty good the method is called fat pivot radix quicksort that's a mouthful but let's just do an example and you'll see what it is like it is like quicksort so let's recap that just very briefly you have a list you pick a pivot element and you rearrange the list into smaller than the pivot bigger than the pivot recurse now we do the same with strings but what we don't want is compare all the characters do to comparisons that completely settle if one string is lexicographically smaller than another because that was expensive so instead what we'll do is just look at one character at a time so here's a list of strings chosen so that it has some non-trivial common prefixes that's our list in the first recursive call we pick a pivot string but what we really look at is only the red characters i hope you can make out the color that these are red and these are black so we only only compare the first character of each string and so s is our pivot

20:22 Quicksort

21:36 and we split this list into three parts not two there's the strings whose first character is smaller than s strictly smaller than s and there's the strings whose first character is strictly bigger than s but there's also all the strings quite a few in this example whose first character is s and these go into a separate segment in the middle okay

22:01 now the crucial thing that makes this algorithm more efficient than the other alternatives we discussed before is in this middle segment i know they all start with an s i don't have to compare this in the recursive call again and again instead i remember in this recursive call start looking at the first character i promise you they don't differ before that whereas in these in these segments before and after they happen to coincide in the first character but we don't know that yet and these don't coincide so a recursive call now is a range of the array and the number telling you at which index you start comparing which character index so let's see um the next the next recursive step here we have a small list we pick a pivot we partition according to the first character nothing really fancy happens here there's one string that's smaller and there's one string that has this first character these are all just singletons so there will no will be no further recursion

23:07 for the middle list we pick another pivot i always pick just the first pivot you really want the random one in practice but uh that makes the example nasty so here we pick she but we look at the second characters this time and the second characters of all those strings then we'll have quite a few strings that have a second character that is smaller than h we have quite a few that have h as their second character and and one lonely one that has a bigger character than h okay and so again we were cursed on all the lists that are not just a single element remembering what is the character we look at next in this part smaller than h we still have to look at the second character because they might have different ones except that in this example they don't but that something we don't know yet uh whereas here all these strings start with sh no need to compare that again and again and again

24:10 in this one something funny happens they all go to the middle segment and we don't make any progress we don't split anything up but we have excluded this first character from the further consideration

24:24 one more recursive step here again they all have an e so nothing really happens they stay together but we've excluded e from the consideration in this one we have a few strings that have a character smaller than e for example l okay did i want to pick another pivot here oh sorry i should have checked the third character no these are sorry i confused myself so the pivot is e and it's the third character so you have to look at these ones there's three strings that have an e as the third character and these all go here and then we go to the next character because their e is all the same good the slide's correct i was mistaken and there's one string that has a third character bigger than e that's the o for the last one again nothing really happens but we get rid of one more character i think you see how this goes shall i fast forward through the example so another round where we have things smaller and equal and same here

25:39 so you see for some [Music] you keep comparing for quite a while and especially in this case the these two strings are the same but the algorithm will only find out by moving uh through all the recursive steps and keeping them in the middle partition all the time so this is not the not the end of the example this part would recurse four more times or five more times before it reaches the end

26:08 one thing you may have noticed whenever a string was actually finished and i needed another character compared to compare with i smuggled in a dollar sign but it just occurred in this point it's just a way of saying if the string is is over you just make it compare smaller with the next character than all the actual characters

26:36 okay that's that's how this works so again in a nutshell it's like quick sort but you keep also track of which character to next compare with and you make three partitions not just two where you have one for all the elements that are equal to the pivot that's why it's called fat pivot because you make this big partition in the middle that has all the duplicates of the pivot element

27:01 so how good is this if you want to read a few more details about this look at the book from or the videos from from cedric and wayne they discussed this algorithm in a bit more detail

27:15 that's just explaining how the algorithm works in general i think i've done this now the interesting statement is if let me circle this to make it really really stand out if you apply this sorting algorithm on a list of random strings where random means each character is just generated according to some distribution and independent of the others that's not quite what we have for suffixes of a given text and is also maybe not quite what you have for english language texts say but under the simplifying assumption you can show that this algorithm essentially takes as many symbol comparisons as standard quicksort took for normal comparisons so this fact that you sometimes have to compare these these long middle partitions that you have to keep going with these two c shells that's just very very unlikely if you have random strings as an input

28:23 and so that's that's that said if the strings do have some some common prefixes we at least make sure that we never compare these twice so in a sense the algorithm is still doing almost as well as is possible in this case because a sorting method if it's given arbitrary strings it will have to find out which strings have a common prefix to sort them so it's a good algorithm to sort lists of strings and it's quite efficient for many types of texts to suffix sort

28:59 but it is still not the end of the story for us because the the worst case for suffix sorting and you get this for again our our boring text that just consists of ace all over if you think about the suffixes for this text they will essentially always fill the middle partition and just one is split off each time so you compare all those and it's inevitable if you just apply a string sorting method as long as you don't take advantage of the fact that the list of strings are suffixes you will not get away from this worst case

29:52 but i promise you we can do it with linear worst case running time by taking into account that we're sorting suffixes