Video 6-3: §6.2 Suffix trees

0:00 <Untitled Chapter 1>

0:02 in the next sub section i want to show you how to overcome these weaknesses of inverted indices that not all texts where we might want to search have these word boundaries and so we want to have something more flexible in a sense we want a full text search full text index

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

0:23 before we get back to the text indexing problem though i want to stress how remarkable suffix trees are and so this is a tiny bit of a history lesson as well and i want to illustrate it on this on this problem the longest common substring problem it's a is a problem where you're given a set of strings as one up to sk and you're trying to find the longest substring that occurs in all of those k strings so again substring not subsequence so it must be some contiguous range and you want to find this this part of the word in all of the strings that you're given here's a tiny example with just two strings and it's already not completely obvious at first sight what's the longest substring they have in common can someone find it button life a life

1:22 so it's it's tricky because we tend to humans tend to recognize the parts well the first is a sentence and so we're a phrase and you have to combine things but yeah a life is is the longest thing they share just because the second there's not much left to make it longer now suppose you have a hundred of strings it's not clear how to do this um and in particular it's not clear if you can do it in essentially the same time you need to just read all these strings once but it's possible at least in in big o off so you allow to read the strings a constant number of times conceptually but then you're supposed to tell me and it's remarkable that this might be possible because it seems you have to what would be a simple approach to solve the problem you could try to go through all possible substrings of the shortest string and try to search them in all the other strings but that's even even that is quadratic in the length of the shortest string and you haven't even searched the others so you would need to use some some string matching method for the other strings and this would be way slower than than just reading all the strings once in the worst case

2:41 they're all the same length all fairly long so not so clear how to do it but yeah suffix trees will allow you to to do this in in that time and we'll we'll get there it's not even that complicated it's just building on a few really cool abstractions further highlight why this is that this is even surprising for experts uh so this is a quote from dan gastfield's book which might be called the the bible on suffix trees is the most most complete collection of things you can do with suffix trees uh and and he says he he quotes um donald knuth which you may know as a the inventor of of latex tech not latex but tech this typesetting system and also the art of computer programming and it's fair to say that he's he's a founding father of computer science or theoretically computer science and also a genius in in definitely several ways definitely a smart person but in 1970 he said that he conjectures there's no linear time algorithm note algorithm with this running time for this problem finding the longest common substring of of a set of strings and it was only three to four years later that he was disproved that he was proven incorrect by the introduction of the suffix trees

4:10 but he didn't foresee that and he he didn't see how to do it with a suffix tree so it's the same canoe from the kmp algorithm all right i hope you're you're hungry for what's coming now uh i tried my best to motivate this so what is a suffix tree the definition is is just this little box and it's all built on things you already know the suffix tree for a text is the compact tri so that was the version without the unary notes of all the suffixes of this text so a suffix is a substring that takes ends at the last character now for convenience we'll always add this end of word character to our strings so our text will have n characters but actually the n index the endless first character is always set to the dollar so we will always assume this here and then we can can build this try over all the suffixes because they're then uh prefix free and yeah that's that's pretty much it uh and so maybe let's spend a minute on a small example

4:28 Suffix trees - Definition

5:30 suppose our text is is this banana then these are the indices so i take all the suffixes and insert them into a try the easiest way to build a compact tri if you have to manually do it is to first build the standard try and then compactify things uh you can also do it directly but uh for the manual execution of this algorithm let's maybe not torture us too much so we first insert banana so we start at the root then we do b

6:20 and then now and the dollar and then well uh i feel i don't repeat the string so instead i just say the starting index of that suffix that's a little more space efficient too i don't have to repeat the suffix all the time because it's always the suffix of the same text so i'll instead just store the text once and the leaf says start at zero and you will get the string that ends here so that was the first one uh how about starting at one character later that's the lovely anna so i branch out at the root with a different letter

7:18 and that brings me to the leaf with a one because it started at position one nana is the next one so let's take this down here two and now it gets more shorter and shorter so it gets a little faster anna is already in here i just have to add

7:55 and that starts at three four is na so i'm here and add a new leaf 5 is just an a so again we branch out to new leaf and well we could also include just the dollar

8:22 and so that's the standard try now we want to compactify this which means remove all the unary chains and while we're at it we can try to make it a little nicer

8:50 then here we have dollar and n a now in the compact try i should write the position that we check next so if we want to do this correctly

9:20 this is a one is a one as well and this is a one so far we haven't skipped anything but then here this n a becomes one where we skip

9:35 this goes to five okay another two three and n a dollar just goes to this straight away this one is just one long branch so this is actually not a one but leads immediately to this leaf and on this side we have sorry this n this is also another one it's a two and then dollar to four and an n brings us to the two they get quite a bit compacter i tried to do this uh in detail for this one so that you also see the the tri compactification another time i don't know how valuable it is to follow this on the slide but

10:30 um if you draw the same thing a little nicer and sideways so that we can read the strings better that's the same now uh i will usually write on the slides the full label of of the edges as they would be filled if you go to the leaf and then check just because it's for us easier to to work with but what's really stored is of course this one where um you have only the first character each and you the internal notes tell you what's the next character to compare okay so again the the three things this is what you often want to write on paper so that you can work with it as a human it has the explicit strings in the leaves and it has the full labels on the edges we don't really store the strings in the leaves we store the just the starting index as i showed you in the example and we also don't really store these edge labels instead we just store the first character okay

11:41 Suffix trees - Construction

11:42 now i've i've shown you on this example how you can construct a suffix tree uh we for let's see how long this takes if we follow this algorithm we have a text with n characters so it has n plus fun suffixes because i added this dollar sign and if i insert a string into a try that essentially takes as long as the string is so if i insert n things and they're n long so at least the longer half or at least n half long so you get this quadratic divided by four at least uh so um it's it takes theta of n squared time to construct the suffix tree using this method i've just shown you insert each suffix one after the other now that's that's really crappy because in quadratic time you can do a lot on strings and in particular you can't solve this problem with longest common substrings in linear time if it already takes you quadratic time to build this suffix tree so there's clearly something missing the definition of the suffix tree is quite natural and easy to come up with but the real achievement from from that time is that you can construct the suffix tree in linear time instead of this quadratic you can bring it down to theta n

13:03 which is again roughly the same as reading the text just once in that same time you can build this compactified version of the try and we'll eventually see how to get there but it will take us a few more steps in between before we can can conclude that part but now we'll just take this as as a magic black box you can build the suffix tree in linear time uh it's a little complicated but once you have it written up you can just reuse it many times

13:38 it's a little tricky to understand but we'll get there it was a theoretical breakthrough because it allowed to solve this this problem will i'll show you the details in in this time that don knuth conjectured is not possible uh and the construction can be done quite efficiently in practice so um a version of this is is still in use in applications like finding matches of your your rna snippets from a pcr test in in the genome database

14:12 so for now i want to take this for granted and see what can we do with it that's that would be the first step as a motivation why you want to learn why you want to see the details of how to construct them in linear time

14:32 i leave you for the break one last longish question that i maybe just leave open for for the break so let's uh let's have a look at the slider question uh there's quite a few different answers and you see all of them got some votes um

14:57 and here's the ones that deserve to have votes most of you did fine so this last part is what i just mentioned we just treat it as a black box for now but we'll we'll get there

15:11 so let me briefly comment on each of these the first one i said is just for convenience to represent the tries so we do required the text to end with a dollar or actually we just put the dollar there

15:14 Clicker Question

15:32 the size of this of the suffix tree is linear in the text size because uh it stores a linear number of suffixes and suffixes and so this quadratic size was for simple tries but for compact tries it's linear in the number of nodes is linear in the number of strings right and that's n uh t is not a standard try it is a compact try of all the suffixes and the leafs don't really need to store a copy so they shouldn't because it's waste of space instead they store just the starting index we can naively construct suffix trees and then it takes quadratic time

16:20 yeah potentially with a compact try constructed right away you don't always need quadratic time but definitely in the worst case you do but yeah the big magic step is you can do it in linear time worst case i haven't told you how yet uh and the last one is a kind of a mini it doesn't have n leaves as n plus one because it has n plus one suffixes once you add the dollar all right that one's not too important we don't really need the dollar leaf for any interesting applications but following the definitions that's that's what's there