Video 6-2: §6.2 Suffix trees

0:00 <Untitled Chapter 1>

0:02 in the next subsection um we'll look at suffix trees which will turn out to be a versatile and really uh useful data structure that's very easy to Define but hard to hard to compute

0:21 Suffix trees- A 'magic' data structure

0:25 I called it a magic data structure here because very smart people essentially thought it's not possible at some point and to to motivate that uh here's a an exemplary problem that we will come back to as well it's called the longest common substring problem you're given a collection of strings K strings as one up to s k there's some example with two strings but it can be more and we want to find the longest substring that occurs in all of these strings so somehow a pattern that occurs in all of the strings at some point at some location and the longest such place so for these two or you can the second is not too long so you can can try to figure this out it turns out to be a live that occurs here and here

1:21 and don't get tricked by this being different different strings put together so the question is if you just if you just have two maybe you get around with just trying different options if you have K strings it sounds like this is even tougher and the question is can we do this by basically reading every string just once that's what this time would be it's the time to process all the characters you can take a constant Factor more but that's that's all you're allowed should that be possible it sounds like uh it sounds unlikely because it it feels like you have to test all possible combinations of positions or at least all possible substrings and check if they occur or something like that

2:11 and it turns out that the suffix trees are able to solve it in that time and if you if you haven't seen it before and but thought about this problem for a while it feels like this is this is not possible so suffix trees are are a way to do full text search in strings they're linear time and space so in in a time and space to just look at the string ones you can build this and you can solve this problem and many other problems in almost best possible ways usually and to further like um give credits to give evidence for this there's a quote from from a textbook on on suffix streets and other related problems uh that that says uh don knuth that's the same knuth from the knuth more spread algorithm and well famous for for his his books the art of computer programming also the creator of the the tech type setting system and in a way um a central figure in theoretical computer science for sure so a while ago uh but yeah so he he thought about this problem as well and said no it's it sounds like this is not doable but he was proven wrong which if you look at it from today is is awkward because it sounds so easy to do

3:39 with the building blocks we'll look at so in two weeks time you will know how to do it but there is a few conceptual jumps in between that were really hard for people to take luckily they're much easier to understand once people already know what to do it's one of these cases where inventing something is harder than than understanding it once the invention is out so what is a suffix tree the suffix 3 is defined for a text um and we'll always add this dollar sign so same same Convention as before but we have a single string a single text but we add this dollar sign at the end which will just turn out to be convenient um and what we built is a compact try what you've just seen and of what set of strings all suffixes of this extended text so you immediately see why the dollar sign is useful there it means that this set of all suffixes is prefix free which were was what we needed

4:52 that's the definition uh let's see some example so here's a text banana ban um with the dollar added these are all the suffixes so you just take the whole thing delete the first character delete the first two the first three and so on all the way down uh and you build a compact try so I've just drawn this sideways so that we can write the the labels of the leaves nicer here's a conceptual view of the compact try that we'll sometimes use because it's a bit more human friendly where I I wrote the entire string as the label on the edge remember from before compact tries they contract this this

5:36 sequences of unary nodes and then they actually just take the first label and represent in the internal notes how many characters did I skip but we can conceptually write this by writing the full label on the labels we know that in reality this is what it looks like in okay there's one more uh before that but I'll come to that in the computer it's stored like this we have the offsets in the internal nodes and just the first label on each Edge that's the compact tripart but it's convenient to write it like this for for us to reason about the second change is if you look at this it looks like it's storing this uh parts of this same text over and over again that's of course not necessary you can store the text once and instead in store storing the leaves only the starting position of the suffix that's enough then you know suffix four is is everything starting at four so it's this now ban that's what it was

6:48 so suffix tree is is that a complex compact try of all the suffixes of the text but in the leaves we store the starting index not the full string

7:00 okay there's also these these three representations that will jump between this one where the internal nodes have the numbers and just the first label is on the edge that's the computer representation the one that one would want to implement to not waste space

7:18 uh this is the version that we'll usually work with because it's easier for us to reason about with these Edge labels here and okay the the first one the third representation is where we spell this out sometimes yeah I'll also use that

7:47 uh one thing I should say about tries uh I haven't pointed this out in the previous section if you have a set of set of suffix a set of strings or a set of suffixes in this case you can insert them one after the other in a try and the resulting try doesn't change if you change the order of insertions

8:06 that's very different from the binary search trees where you remember if we had the sorted order it would be this completely degenerate case and if you balance it more then it would be nicely balanced not for tries in tries the structure is completely dictated by the strings and so the order of insertions doesn't matter that's one convenient bit and so it means we can say we just have one specific try the suffix Tree in this case is well defined for just the string you don't have to ask what's the order of insertion or anything like that

8:47 Suffix trees - Construction

8:51 so that's all the magic uh there is in the suffix tree we'll come back to how to solve this this cool problem that people thought is not possible in this in this fast time with suffix trees the tough bit about suffix trees is how to construct them quickly and let's have a look at how to construct them slowly but simple

9:17 if we have a text of length n so n characters it actually has n plus one after we added the end of word character then we can build this suffix tree in uh the simple route is

9:31 take each suffix insert it into a try and at the end you have the suffix tree so you could um the the most the most straightforward way to do it is to build the non-compact try first then compact it and then replacing the leaves all those pointers uh all the the strings by just the the starting index the problem is that this takes essentially quadratic time because the the the the first half of the suffixes they all have at least n half characters and you always have to Traverse the try so that alone already takes quadratic time even if you're not starting with the standard try so that doesn't work

10:26 and for now we'll just leave it as a magic Black Box the amazing result that will eventually come back to is you can construct the suffix Tree in linear time you're given the string and there's a magic procedure that spits out this thing without going through a lot of effort

10:50 it's a little tricky to go into the details but we'll build up to this and this was the part that was not clear if it's possible because um this this Construction taking all the suffixes and building a try on that that's straightforward enough for researchers to come up with um before the time but whether you can build it quickly that was the part that wasn't clear and so uh that's that's the that's the big box to look out for uh for the moment we'll just take that for granted and see what we can do with it but we'll come back to it

11:38 now because um many of you haven't seen tries before uh I wonder if it's useful if we construct this try from scratch to see how you come to this um essentially to reinforce uh the definitions of tries Etc so this is not specifically about suffix trees really but to give you a feeling how to do that

12:16 okay I probably want the indices but let's try so we'll start with the standard try because these are these are easier to construct or for humans and so again the the procedure I'm showing you now that's the crappy slow algorithm that's not what we want to use at the end but it's the one that is uh easier to follow so we start by just inserting the whole string so I'll need a lot of space for that let's try to be small

12:56 [Music] um nah okay I'll first try it done and nah okay I can make it a bit bit bigger right it's a bit extreme can't see much Ben okay now I'm foreign

13:36 it will probably be taller than than white so let's let's see and we need the dollar okay this will this will be messy at the end that's one string inserted now let's do another one that's the one that starts with an A so NN of n that's going down this route with a

14:34 and then we have another another Leaf I'm leaving out the the contents of the leaves but what should go there is is zero and then one so that's uh that's already the indices where we started so the next one is nanoband that's again another link from the root so that was B n ah

15:02 nah and the dollar it's really tedious but it gets faster because the strings become shorter and now the first thing uh the first time something interesting happens if we start with with this one we have anaban which reuses parts we've already built we do a and a but then comes span

15:40 and the dollar right okay now naban goes down this path n a and then we fall off with Ben there's nothing more uh educated than doing a quadratic algorithm by hand and suffering real hard

16:09 shows you much more why you don't want to use them so we've done now Ben Nexus a band so we go down here and then we fall off with Ben

16:23 it also shows you that there's some pattern that is uh live there's always this band at the end that seems to fall out of the tree now here's another one just Ben this is actually in the tree but we fall off with just the dollar

16:44 then and would go here and then fall off with the dollar it's not seven and just n fall off with the dollar and well just the dollar if we want falls off right at the top that's the standard try now we have to contract that to get the compact one uh fortunately that's not quite as bad

17:17 and I'm drawing the human version so we don't have to figure out the indices so we have one two three four children at the root let's try to draw that a bit meaner a bit neater and so we can do a b n dollar sort them alphabetically while we're at it

17:44 now let's take the a branch there's two children one that needs a lot of space with an a and the other is just band dollar so that will all be contracted into one Edge

18:06 then let's continue like a depth first search uh a a brings us so that's that's an N right that was an N I read it as an a a n brings us down here and then that has another two children a and dollar

18:35 and here we continue we have uh two children one with n one with B the B is just one long chain so we can directly write band Dollar on the edge and go to leave three and the other one is actually also one long chain I'll I'll need more space on that edge because it's naban

19:06 dollar and it goes to one okay you see how this goes should we continue the rest I'll try to speed up a little so we go B that's actually a whole ban so we're down here fall off with a dollar for six and then we have a one long and a band

19:34 that was the whole string then for the N branch two children again one with a one with dollar and that falls off right away and this one branches out another time into [Music] n and B

20:00 so I'm at n a and a B goes down to ban no note just one long Edge that was this one four and the other one is also one long Edge going down to naban

20:28 and the dollar and two and that's good so you both see in this example that it's painful to do the full thing it's also visible that it has much less notes this compact Joy and apart from the human based version that we write all the strings on the edges that's the suffix tree okay so it's it's not too hard to construct these manually it's just tedious but that's the slow algorithm we don't we don't get the magic results from using that one that doesn't scale with large strings

21:17 good so just assuming that this fast construction does exist what can we do with it before we uh bother to learn about it more I have a fairly mean summary question that's trying to test you on

21:29 Clicker Question

21:42 your understanding of this definition okay I'd love to start it it's basically just to have that fresh and fresh in mind before we use it it's an interesting even split I wait for a few more people

24:19 one more okay so uh let's see we have some votes for most things there's also many correct answers let me briefly recap so um uh we we always put dollar sign at the end of T that's correct the size of the suffix tree is never quadratic it's always linear if it were quadratic we can't possibly build it in linear time we just need that time to write it out the trick here is the the tries uh could be big but the compact try never is especially if we store the leaf labels just with an index the whole thing is is linear time so Theta Theta n space

25:15 uh okay T is a standard Tri of all suffixes of T of T dollar is not correct because the standard is wrong but a compact try is is correct with this little like use the index in the leaves not the full string uh the leaves store a copy of the entire string no we can't do that that would use too much space so we just use an index the naive construction where you've seen me struggle so much it takes quadratic time in the worst case but we can't do much much better uh T has n leaves that was a meaner a mini mean one it's n plus one because we have added one more character but yeah apart from that it has one leaf for each of the suffixes