Video 8-2: §8.2 Suffix trees

0:00 Motivation and problem

0:02 in the next section we'll look at suffix trees a way to get an index built when we don't have words in our text and I want to motivate them first by showing a slightly different problem that they will in the end solve as well and where it seems um an efficient solution is is really hard to get so that's the problem of finding the longest common substring of a set of strings so you're given a set of strings uh can be many k strings uh there's a small example with two strings and your goal is to find the longest substring that occurs as consecutive characters in all of those K strings okay uh so if you have these these two uh sou California lives and sea liver um what's the longest thing that occurs in both uh I think a life

1:04 is the longest uh just because the second text is relatively short um there's not so many uh possibilities and here we have five characters and that seems seems not to be able to do better but now imagine um if you have many strings not just two and all of them are long and they might overlap in arbitrarily ways in arbitrary ways so this is all about um can be worst case uh how how should we how should we find such a longest common substring um now in principle the problem is easy you can go through all possible substrings of all strings all start endpoint Pairs and uh check for every substring if they occur in all the other strings we've seen string matching algorithms to do that in a somewhat reasonable time but it feels like this is at least quadratic in the length of these strings and maybe worse whereas the question is can you do it in linear time linear in the total length of the strings that's the same time as just reading every string once up to constant factors uh and it seems it seems if you look at this not

2:28 possible but indeed it is possible and suffix trees solve this and it's not even it's not even a complicated algorithm to do it we'll see it next time uh suffix trees are are much more versatile than that they seem to be the kind of goto um Step or the the threshold concept that you need to solve many string matching problems or string problems in general uh they're very fast to construct and use um that's not obvious but we'll come to that they can be constructed in linear time and they take up linear space in the to in the length of the string or length of the total number of strings total length of the strings uh and here's um what I alluded to earlier uh Donald canth is is one of the maybe founding fathers of theoretical computer science he wrote this uh famous book series The Art of computer programming that defined many of these things and he's also the uh the author of of tech and uh what what is behind lat Tech and uh in in the 70s Don K who has good intuition about many things maybe uh conjectured that finding this this longest common substring cannot be done in in linear time and it was proven Wrong by the invention of suffix trees

3:45 in the end but it took people a while to get the algorithms uh fast and eventually also simple okay so what is a suffix tree the definition is actually simple the suffix tree for a text is just the try of all suffixes now a few nitpicks we'll use the compact try because the other one takes too much space uh we'll always add this end of word marker to our text that's just to make sure that if I take all the suffixes of a text these are a prefix free set of strings other than that the definition is straightforward there's nothing special about it so let's have a look at a at an example I started drawing this in the break and we'll build the rest uh together so um here's a text banana I already added the dollar and I already took all the suffixes which just means deleting one more letter from the beginning one after the other until you're left with nothing and so we have the suffix starting at position zero we have the suffix starting at position one and two and three and four and five and six right so these are the indices in the string to build the compact try uh straight away is is messy but it's easier for the example to do it also if

3:58 Suffix tree definition

5:10 Building an example

5:17 you want to do it manually it's easier to First build the standard try and then compactify it afterwards I've already started inserting the the longest suffix banana and then an Nana down here uh let's do the next one Nana we start with inserting from the top um there's no n at the root so far so we add another edge with n and then um because we don't have any any other uh any other paths on on that part we just append the remaining letters and here I I'll just put the starting index in the leaf so I don't have to copy the entire string we'll use that later too uh the string is is stored once but then I don't have to copy the suffixes in each point I just know need to know where they start so that's Nana inserted then Anna for for this one we started the root a n a is already there the only thing that's missing is now the dollar so I just append that here and that was number three starting index three and these get shorter and shorter which helps over time so if you insert na we go na already in there so we just add a new Edge for the dollar symbol then five a and then the

6:55 dollar and for six we just have the dollar so that uh in that example it also shows how um the try makes use of repeated Parts in the p in this in this text right if you want to compactify this all we have to do is get rid of all the UN nodes so we start with the root at zero then we have four edges for dollar for a for B and for n all of these um or this one leads to a leaf straight away a leads to another internal note and we haven't skipped over any characters B skips actually all the way along and goes to a leaf and N skips two POS skips one position so we continue at index two uh when we read further down and we're we're actually now at this point so um Let Me Maybe indicate this so we're here this guy whereas uh this one's do node and okay it might get too messy to connect it with all but uh can try okay now let's continue with this note so you see how um how we continue There we have one edge with the dollar that goes to leave four we have the other Edge that goes to the other leave two and we only need the first letter

8:27 N uh then what's left is is this node so we jump here we again have a branch of two either we go with dollar to the leaf five or we go with n to another internal note but we jump two down so we go to index three if I want to highlight this yeah now it's getting messy I guess uh let me get rid of those the leaves are clear because they have the same label so that note here again we have a branch of two notes we have the dollar for a leaf and we have another LEF

9:10 indeed where we go with n and that's it so the compact TR is visually much smaller as well right it's much shorter so that's a way to build the suffix tree this this guy here on the right is the suffix tree for the text banana the only problem with the procedure I've shown you is we first built this standard try which is quadratic in size n * m but M here is the number of suffixes that's another n so this guy here can have uh N squared nodes uh internal nodes as we've seen before so even if I'm smart about the second step and the first step of building this tree the intermediate step makes something so big that the overall time will be quadratic so this procedure is is fine on small examples but it doesn't scale well to large

9:20 Construction complexities

10:11 texts uh here's another example um drawn a bit more nicely and slightly bigger uh and I I've drawn it sideways so I can write the text in the normal way uh other than that there's um there's nothing different now this shows you the the human representation of suffix trees that I'll use on the slides um to introduce algorithms uh the human

10:43 version differs from the actual one that we represent in memory in a few in a few cases um we store the actual suffix in the leaves so that that you can read the text instead of having to jump to the starting

11:06 and on the uh edges I write down the entire string that they represent remember this is a compact try there's only one string that they represent but it would normally not be stored explicitly we would just store the first character uh but to make it nicer to read for us and and reason about it for us um we'll have the entire Edge labels what's actually stored is

11:30 is this right so uh Step One is we represent the leaves by the starting index not the string and step two is use the convention for compact tries we've had earlier so uh these are all hidden but we'll use the the human readable version to design algorithms because it's uh it's much clearer to um to see in the examples what happens but you should keep in mind this is what actually is stored

12:05 I've mostly discussed this already in on our example but to have it in in proper writing um if I have a text and I append the dollar sign it has n plus one suffixes because I added one more symbol we can build the suffix tree easily via the route I've shown you by uh inserting one suffix after the other in a compact try or for that matter build the standard try first and then compactify it uh both gives you quadratic time and it turns out that that's not interesting you can do in quadratic time you can do other things and flip side is most interesting applications become un infeasible if you require quadratic time in the text size so for example your genome is is two billion characters if you square that uh it'll just never finish

13:00 Linear time potential

13:00 now the amazing result I already alluded to is you can find the suffix Tree in linear time even though it it seems to need inserting many many suffixes um we'll come back to this we'll at the very end actually see an algorithm to do that um it was long conjectured or it was long it was a surprise when it was first uh first discovered and uh we've seen the this comment from from Don Donald K that he conjectured it not possible um and by now there're a staple method in in practice especially for genomic analysis uh they they build on on techniques that we'll discover here uh routinely for the moment what we'll do is just assume that we have some magic black box that gives us the suffix Tree in linear time and uh before I tell you lengthily how they are constructed I want you to be able to see why they are useful so for now we'll just take that for granted and um look at some applications of suffix

14:16 trees uh before we go to that um we should probably uh make sure that this definition is clear so this a lengthy question but uh it's a good prompt to discuss a few nitpicks as well

14:51 and uh I'll go back to the example I think that's would be lovely to get to 60 again five more missing and one more yay so most answers got some votes um not all are correct but quite a few are uh let's briefly go through those uh to discuss so uh we said this that's just our convention always for suffix trees and that that's something most of you got right uh the size of the suffix tree is never quadratic because it's a compact try and uh that one even in the worst case is linear size uh linear number of nodes and uh constant size per node if we assume the alphabet is is constant uh it is true that the suffix tree is the compact TR of all suffixes but not the standard try that would exactly be too big um the leaves kind of represent the suffixes but they don't store a copy that's why uh uh with with that addition uh that's clearly not what we want again otherwise we'd need quadratic space that just store an index the starting index of the suffix uh we've seen the naive construction I commented on this many times and uh I added the claim that it's do possible to do it faster the last one is kind of

16:52 Review and discussion

18:34 mean it's n plus one leaves because we have n plus one suffixes because we added this uh end of word marker other than that it's is almost correct right but yeah not quite good