Video 6-2: §6.2 Suffix trees

0:00 <Untitled Chapter 1>

0:03 Suffix Trees

0:03 in this next sub section i want to introduce suffix trees these will be the the star data structure of this unit that uh seem to magically solve a lot of interesting problems they first solve the text indexing problem but we'll see they are also applicable to many other problems on strings and they turn out to be versatile and really a threshold concept once you understood suffix trees suddenly you can you can solve more complicated problems efficiently and um they all they all start with these simple tries that we just um that we just defined so let's let's see how this works here

0:51 a magic data structure uh before i want to show you how suffix trees work or what they are really i want to motivate a little bit how formidable problems they can solve by looking at this specific problem it's the longest common substring problem it's a an intuitive question maybe it's not the most immediate that you would come up with but it does arise in in applications so you're given a list of strings these can be of different lengths and well they are over a common alphabet say but otherwise we don't have any restrictions so here's here's an example and the goal is to find the longest substring that occurs in all of these strings so in the example here we only have two and because the second is fairly short you could check that a live occurs here and here and if if you spend some more time on this example you will see that this is indeed also the the longest or a longest repeated sub common substring uh in general there could be several of the same length and then we can return any of these so this is a simple to state problem but imagine you're given these strings how would you approach this how would you find this shortest this this longest common substring

2:26 um you definitely need time to read all the strings that's no doubt about that and it it turns out you can actually solve this problem in this in asymptotically the same time only a constant factor more but how on earth would that work uh because it's it seems like you have to check all possible substrings and even then all possible substrings of one string you would have to go through all the other strings and see if they occur somewhere you could use something like our string matching algorithms so you get that part efficiently but going through all possible substrings that's already quadratic in the size of the shortest string and you would have to search through all the others so it's it's quite unclear how to do this efficiently and clearly not easy to do in this in this optimal linear time the same time as you need to scan all read all the texts all the strings once

3:28 and indeed suffix trees solve this so let me show this big so uh suffix trees allow you to do exactly that um we'll see that you can construct them in linear time um with a specific problem we'll we'll come back to that later today and uh they allow you to do exactly that even though it seems not possible at first and to give more um more weight to this claim here's a quote from from a book dan gastfield has written this this book which is essentially the bible on suffix trees it's the most comprehensive books book of applications of suffix trees and he says although the longest common substring problem looks trivial now given our knowledge of suffix trees don knuth famously known as the inventor of bladetech but also the author of the influential book series the art of computer programming in a sense uh one of the one of the fathers of theoretical computer science and the analysis of algorithms and uh a very clever person um called a genius by many etc so the in in 1970 he conjectured that a linear time algorithm for this problem uh longest common substring would not be possible he didn't see a way and he thought there is no way uh and yet he was he was proven wrong

5:01 now this this happens occasionally even very clever people um sometimes don't see a clever solution and then someone else comes up with it that's what happens in in science uh all the time or occasionally and uh repeatedly maybe not all the time but it's still remarkable because he was right with many other conjectures uh so this is this is interesting and uh it also maybe motivates you a bit more to learn about what this magic data structure really is

5:37 and um here it is this is the definition of suffix trees it's not very complicated if you read it like this a suffix tree and use this this calligraphic t to denote the the tree just to make it um make it distinguishable from the text the normal t the suffix tree of for a text is the compact tri of all the suffixes of t and we append this dollar sign again so that all the suffixes are prefix free that no suffix of t is a prefix of another suffix so we will always assume that this n character of t is set to dollar and the dollar sign again is some symbol that is not in our alphabets an artificial end of file character if you want nice and simple right um very easy in a sense to define um and maybe at this point let us uh look at a as a quick example um of uh how how this might be constructed this was also a little bit of a recap about tries again um so let me do uh a smaller example example

6:56 this might already take some time but let's do banana and see how far we get so this is our string now uh we take all the suffixes so that's banana and that's a nana

7:18 and anna and now and a dollar and you correct me if i'm making mistakes okay there were some questions that i overlooked sorry for that um maybe i'll come back to this after this example

7:42 if i make any stupid mistakes during this construction you will help me out and point it out to me right i counted you okay these are all the suffixes of the text and now we insert them into a compact try now is a bit tricky to do the compact try in one shot so at least for the manual construction let's do first the standard try and then we create the try afterwards okay so we start with the route and uh let's do the longest one first um so this is banana so i have a b then um i have an a

8:26 [Music] and uh here i'll just put um zero for the start index this starts at zero this is one at two and three f4 at five and at six and that's um zero one two three four five six that's all these are the suffixes of of banana so we've inserted the first one now we have to insert the second one and anna okay it starts with an a so we branch off in the root and uh then let's see i'm trying to think a little bit ahead of myself so let's uh branch out here do we ever have something else after an a then an n well at least a dollar at the end so let's let's keep it like that and [Music]

9:31 nah this makes for a great recording and the dollar sign and that brings us to well the suffix starting at one okay i guess you see the picture now roughly how this goes and we need another edge here for nana na um

9:50 and the dollar and that brings us to the subject starting at two uh a few more left anna it actually goes a n a and then branches off with the dollar so that was not too not too much work we didn't have to create other notes and the same for now and a we branch off with a dollar here and put in the four and a dollar is similar we branch off here a and then the dollar is starting at five and just the dollar let me put that down here that starts at six okay that is the standard try now we want the compact try so we take this standard try and do the compaction construction from from last time

10:46 so uh let's move this slightly over here and make it a little smaller so i can fit this next to me um the con can the contraction is now i'm okay i should leave room we start with zero here and then the a b and dollar they stay because these are leading to nodes sorry the a and the dollar stay because these are leading to notes that don't have exactly one child okay

11:23 and then this leads to a note with one the dollar leads immediately to a leaf with six um and uh here the banana is actually contracted into a single edge and leads immediately to the lead okay so this here we got rid of a lot of nodes and in the last case um we branch off to a node that now looks at the second letter it starts with an n we get rid of the a here okay uh so let's let's go to this node a that's this one now uh there's two branches the one with the dollar is is leading immediately to a leaf so that's one thing that's easy the other one again leads to a branching note here and so that looks at the third character then the character at position three and starts with an n from that we branch off with a dollar to the subject starting at position three and the in the other direction we have an n and that leads us immediately to another leave okay so you see how these are connected and how we get many fewer nodes in this case we're left with this node over here and that one is you don't see my mouse anymore right that one here uh has the n a so that has a child with the

12:58 dollar that leads to the four and it has another child also leading to a leaf that's this okay and if you want you can draw the connection between the corresponding nodes so this is the root this corresponds to that one this corresponds to that one and i'm not doing all of them just the internal ones so you can see how these correspond to each other

13:34 i just wanted to give a very slow example again of how tries work because many people haven't seen tries before there were a few questions that i wanted to address let's do the easy one first um the comments on the class test i suppose this refers to comments that you give on the evaluation

14:04 i'm not sure if i get flacked when these are added so i'm i can i can try to look over them uh if you mind something else maybe you have to clarify

14:19 um the other question was i suppose uh when we had the earlier example from for the tries so let me go back a little bit on the slides to the try example so the question was if we search for a a do we the first step have to compare the first character with both a and b or do we go to a right away um if you search for a a in this try uh well if if this was not the example you're referring to franco um let me know um if we go a a dollar in in either of the tries we have to follow the edges down

15:13 i see the question might be um do we have to compare all these characters or do we just jump in the right direction uh that's a detail that depends a bit on how you represent tries but we will usually assume that you implement uh the children of a try with an array and the array is in this indexed by the letters so you can in one step jump to exactly the right child in in constant time or find out that this child pointer is null and there is no such child i hope this was this was the question um you had in mind here

15:51 so this is uh this is about how to represent tries internally in a computer and there's basically two options you can either have um as i said an array indexed by the alphabet then you hopefully have a not too big alphabet to do that the other option is to store another dictionary in each node that maps alphabet characters to a child link that's also possible you could do a binary search tree inside each little node but you would have an additional running time factor log of the the number of children then so log sigma in the worst case so people usually think of tries as having

16:37 a way to go to the children in constant time looking only at one character not comparing the characters one by one but that's uh that's an important point yeah thanks for the question

16:52 all right um back to the other try we were looking at um this one i hope i didn't goof in the example um but you see what i want to get across at this stage is suffix trees are not by themselves magic the definition is very simple just build a try of all the suffixes uh we do obsess about it being a compact try but other than that there's no magic at this stage and here's a slightly bigger example my uh okay it doesn't work my my favorite string that you will see many times in this um in this unit is banana ban because it has lots of self-similarity if you take all the suffixes of that string and build the same type of tribe um you get this picture just drawn sideways so that um it nicely fits on the slide this is the compact try in the standard way um we draw it except that um here i cheated a bit and put the long labels on the edges we don't really have that um and and the first thing is we don't have to store all the strings in the leaves again because we know there are suffixes of one fixed string so we store that fixed string instead and a starting index

18:20 and of course this is not how we represent it in the computer i mentioned this before the compact tri is actually storing just the first letter of all the edge labels and then stores what is the next index that is compared so this is a again what we what we think of is often this this is what you should have in mind when you try to work with suffix trees but if you program them what you really do is is this uh the compact dry as we've seen it before and the leaves only store the starting index of the suffix

19:02 How Can We Construct a Suffix Tree

19:05 how can we construct a suffix tree and this is where the magic starts we can do something like what i've just shown you on an example we insert all the suffixes one by one in a try that works but it takes um quadratic time because uh you have to start you have to follow the search path for each suffix so it's essentially inserting one of length and one of length n minus one one of length n minus two all the way down to one but half of them are at least n half so those already give you a n squared over 4 of of total time in quadratic time you can do a lot of string problems already some are not even obvious how to do in quadratic time but many are this is not interesting if your string is the whole human genome you cannot afford quadratic time it's just not it just won't finish so the suffix tree by itself the definition is very simple and not matching at all but uh the straightforward way to construct it doesn't help then it's not really useful the amazing result that people found is you can actually construct the suffix tree in linear time the same time asymptotically only a constant factor difference than just reading the text once that's

20:20 The Suffix Tree in Linear Time

20:32 in essence the time you need to construct this this complicated tree uh the algorithms are a bit tricky uh they date back to um shortly after knuth made this conjecture i think in the 70s they were uh improved successively they started out to be very complicated uh they were certainly a theoretical breakthrough but they also by now have heavy influence in practice and um towards the end of this module of this unit i will i will actually show you a way how to do this how to construct suffix trees in in linear time and uh by now the algorithms have become much cleaner so that they're actually definitely understandable but they build on several steps and we'll have to work our way through there before we finally get to this result what we'll do for now is we just take the linear time construction granted and uh first ask the question let's suppose we have this this magic box so suppose there is a way to get this um as a treat this as a black box and there's a way to construct suffix trees in linear time what can we do with this