Video 6-3: §6.3 Applications of suffix trees

0:00 <Untitled Chapter 1>

0:02 we'll see that they can solve the text indexing problem but they can also solve several other interesting string problems including this uh longest common substring problem that don knuff conjectured not to be solvable in linear time but suffix trees actually make this possible

0:23 so here's again um a suffix 3 example uh as i said before you should really think about suffix trees as this thing on the right uh so suppose there were all the uh all the labels of the edges spelled out as strings like this that is just to make it um easier to think about it it's actually represented in the computer like this and this will this will be important to make sure that the space works out but for working with them we will just pretend that this is what we have and we can then in a second step we can think about how to simulate anything that these these labels can do in in the way they're actually stored in the tree a little additional technical assumption is that we'll also assume each internal node has a pointer to the left low's leftmost leaf in its subtree this is something that um you can easily once the the tree is constructed you can easily walk through the entire tree once and make sure that this is true but we'll assume that for example the root points to this one and this one points to this one so it's just an additional field in in each node and well here in this example it looks like

1:45 it's always just a child of that note but that is not in general true you can have uh cases if you if you suppose that these two branches were swapped the other way around um then you would jump down to the seven which is not a child but a grandchild and then in general it could be arbitrarily far arbitrarily deep in the tree all right

2:18 so that's um that's just a technical assumption uh it's easy to maintain and easy to make sure that this is true but this will be this will make the applications easier to discuss

2:36 i before i want to talk about text indexing in more detail here's a question for you um i'll try to leave this leave this here so that you can see the tree you're given a suffix tree here on the left and the question is how much does this tell you about whether a pattern occurs in the text here so uh take all the answers that are correct for this specific example so the text that gives this suffix tree and this given pattern

3:18 maybe show the big suffix tree instead it's the same big surprise i'd like to see a few more few more answers before we move on okay i see 15 people have voted maybe we can get to something like 20 25 it was 30 in the first poll so the magic number should be r25 right

4:15 maybe what i should have added is um i don't know i put in another option if if you feel like you have no idea what i'm asking then uh just say don't know that's also interesting um to see if if i lost you

4:50 okay we're getting close to 25 so two more come on we can do this and uh that's a lot of answers so i'll have to scroll around one more yeah there we go okay um i think i'll just show these and we will discuss them on the slides because it's a little nicer to have the tree alongside it um yeah so i probably should lock this now otherwise you keep changing your mind um it doesn't tell you nothing that would be a bit useless it does tell you that p occurs in t in this case um and uh let's see if i can nah no way okay we'll come i'll come back to it um oh that's the opposite but um it also tells you how often the pattern occurs in t and it tells you where exactly and uh for that um i'll probably want to go back to the bigger picture and make it real big so we're looking at this street and we're trying to find

6:07 the occurrences of anna this is not an a so we're trying to find anna so what we have to do is we started the root and now we find the edge with an a we follow it then follow the edge with an n and then the edge with an a that brings us to this note so we know uh because this note exists that already means there is at least one suffix of the text that starts uh with this string and that will be that will be enough to know that there is an occurrence the number of leaves is the number of occurrences and the indices in the leaves is the starting indices of all the occurrences that's why uh these are the correct answers um but uh let's go through this in in a little slower pace um again so the first application of suffix trees is the text indexing problem that we started with and this is the the simple and the simple equivalence that i implicitly already used p occurs in t if p is a prefix of a suffix in t uh and just maybe because this might be it might sound more complicated than it really is suppose there's a current of p and t so these are all matches

7:15 The Text Indexing Problem

7:42 well then of course uh you can take this suffix if there's a position i you can take this suffix of t and then p is is just a prefix of that suffix so it it starts together with this and um it's a an initial uh substring of this green part okay so p is a prefix of a suffix of t

8:22 um but there's there's more to say about this we have all our suffixes in the suffix tree so all we have to do is um follow paths and see what happens some um

8:41 well let's do it like this here's an algorithm that checks exactly what the occurrences are and this is the algorithm i briefly sketched on the example but spelled out in more detail because there are a couple of different cases in the general case what we do is we try to follow a path from the root down the tree by following the letters of p now in the case of anna we went down here and then we were in the case that we run out of pattern we're somewhere in the tree and our pattern is finished and that meant that we reach some internal node or we stop inside the middle of an edge for anna it was

9:33 in an internal node and if we say look for ba we would be stopping in the middle of this edge right we run out of pattern and we're still in the middle of one edge both cases are essentially the same they just mean that p occurs at all the um leaves in the subtree that are below the point where we stopped so if we read a and a

10:09 that means everything in the subtree here all leaves in there are occurrences of the pattern in particular at three and one as you've seen in the example and uh similarly if if you look for ba you would just get to here but then everything in the subtree again would be an occurrence of ba

10:38 that's probably the easy and intuitive case that we can run into when we're looking for a pattern in the suffix tree there are two other cases though um one is that we cannot continue we are stuck in some sense and um well that's what that means is we're at an internal node and there's no edge with the next character that we would like to read or we are inside an edge and then the next character doesn't match so uh two examples for the two cases could be if we look for nb that's not it

11:21 if we look for nb we read n and then we cannot continue with a b then we fall out of the tree in a sense or we are inside an edge that can happen if we look for baa

11:35 we start reading like here like for band but then the next character is not an n so uh we're again falling out of the tree and that means p does not occur in the text that's the other case if if you get stuck in whatever way you fall out of the tree then the pattern does not occur there's the last subtle case which is we run out of tree we keep we have more pattern but we um reach the end of the tree we reach the leaf um in general this this can happen but it doesn't happen in our case with the dollar sign if we assume that the pattern cannot contain the dollar sign we cannot run out of tree because we would have a mismatch with the dollar at this point so uh the only option how this could happen is if we you somehow scan past the dollar but if that doesn't occur in the pattern it cannot happen so this case is not really relevant for the text indexing problem but in general it can happen if you're using tries for uh for more general problems so it's uh that's why i listed it here

13:00 but for the text indexing problem and the way we use suffix trees at the moment this is not an issue as a final remark is how long does this take if we reach this internal node we can either immediately declare there is a first occurrence remember this is every such node store stores a pointer to the leftmost leaf so we can jump to the leftmost leaf and get its index and that is a position in the text where the pattern occurs

13:32 if we fall out of the tree then there's no such pointer and there's nothing to return we just return no match both is possible in time linear in the size of the pattern and i want to stress how amazing this is one more time you're you're building a web search engine that stores the entire web but the time to search for a phrase i don't know you search for banana because i'm it's all banana in this mod in this unit it only takes time proportional to the length of this string banana it doesn't matter at all how big the data set is it can be the entire uh the entire worldwide web and that's that's quite um that's quite remarkable it's innocent to state it's just depending on the pattern but it's really an amazing result and suffix trees allow you to get this once you've built your suffix tree for the entire internet

14:31 that's only one application of suffix trees we've already seen a second problem namely well this is almost almost the same that's the longest repeated substring so here we're given a single string t and we are interested in finding a string that occurs at two different positions it starts at i and it also starts at j so again you know my favorite pictures uh we want the one occurrence at i and one occurrence at j um in principle we don't we don't object to the fact that these two occurrences can overlap so inj could be so that the two occurrences overlap that's not not principally unthinkable it would mean that the pattern has a certain periodicity think back to unit 5. but that's um that's not the main the main point for this application here again the question seems to be how to use it how to do this efficiently um it seems like you have to check all the substrings in in the text

14:42 Longest Repeated Substring

15:44 but it turns out suffix trees can do this for you and let me make this remark and then i'll show you the example whenever you have a repeated substring anything like this so again uh because that was erased some position where the same pattern occurs at at one position i and at another position j

16:09 that means there's two suffixes in in the suffix tree one that starts at i the entire thing here and one that starts at j and uh they both start with the same shared uh substring now that means they both lead to a certain point in the suffix tree and then branch off in a different potentially branch of in in a different direction and in this application we know they branch off in a different direction otherwise we would have a longer substring that is also shared so we could just go one one more character so for example here um again our favorite my favorite example banana band a longest common um two two suffixes are are t5 and t7 um a ban and an and uh they have the longest common prefix of a they only share the a obviously then they differ in the second letter now how does that um how is that reflected in the tree if you take the two suffixes they correspond to these leaves then their pass from the root they actually go via here and then here so they split at this point and this is exactly an internal node that corresponds to the shared common prefix okay it's a single edge and a single letter here but uh

17:42 in in principle it could be a longer example if you take three and one then they would share anna all the way down here and you would have a longer a longer path to the the last common ancestor okay so this is in general true if you have repeated substrings in a text that will mean there's shared paths in the suffix tree and if if there are longest such shared substrings there will be an internal node in the suffix tree corresponding to this longest shared repeated substring okay

18:26 and that means we can exploit this fact if you look at the if you look at the tree a little closer then indeed the uh the connection is is can be made more explicit the longest common prefix between two suffixes is exactly this uh lowest common ancestor

18:46 um okay sorry i'm jumping ahead of myself i'm not talking about these yet um the longest repeated substring is simply the longest common prefix of two suffixes and uh i was i was confused by the abbreviation but this is just the longest common prefix uh the connection to what i mentioned is if you have two such

19:13 suffixes the ones starting at one the one starting at three their longest common prefix will be this uh shared part and it turns out that this is the label of the lowest common ancestor of those two notes it's the the lowest ancestor in the tree that they have in common but the point i'm making here is if you're looking for the longest repeated substring in the entire string that is the longest common prefix of any two suffixes so how do we find this and that's that's this algorithm here the first step is we compute the string depth of all the notes in the suffix tree so what what should that mean um let's make that blue the string depth is simply how many characters did i have to follow to reach a certain note and uh we can start with the root that's at zero we have didn't read any characters to get here if we go down here we are at one two three for this note now that looks like it's just the ordinary depth um but it differs if edges have a whole string as a label then we jump right from zero to three okay so that's that's the string depth that's the string depth of internal nodes in a suffix stream

20:39 um the second step is we just find any internal node with the maximal string depth so in our case that would be either this one or this one they actually both have a string depth three and then the label from the root to any of these maximal string depth notes that is your longest repeated substring so we can either take anna or we can take band both have three letters and both are repeated and maximal and that's the longest we can find so these are very easy algorithms once you're given the suffix tree that would be fairly easy to implement you walk down the tree once and you can you can remember what the current spring gap is and then you just um advance that when you walk down and then you do a second traversal visit all the notes and keep track of what's the the largest string depth you've ever seen very simple to implement once you're given the suffix tree so you can solve this problem in linear time using the black box that you can also build the suffix stream in your time okay that was the application of the longest repeated substring i i initially mixed it up with a different a different problem the one that i mentioned in the introduction that of

22:00 the longest shared substring the longest common substring and we would really like to apply the same same kind of technique to this one so obviously these look similar the longest repeated substring in one string it feels like it should have to do with this longest common substring of several strings there's some subtle differences we do have restrictions that this common substring must lie entirely inside these others so it's not useful to have to know that there's two two occurrences in t1 but none in the others so it's a bit more restricted but uh it's a very similar question we try to ask for something repeated but in different strings so maybe we can solve it in roughly the same way but an obvious approach would be you build the suffix tree for all the texts 140 152 etc

23:03 but that doesn't really seem to help because what you need is connect the information about different texts you somehow need a single big tree that can represent all the strings and this exists that's called the generalized suffix trees and

23:21 Generalized Suffix Trees

23:32 these are again a little magic device that is often very helpful and again it's uh the definition is very simple um but uh they they have very profound applications then so let's look at what this is the key idea is you make one large text out of the different texts but you don't just concatenate them you put a dollar symbol between the texts and it has to be a different end of the end of text marker for each of the texts so you try to distinguish them all you just invent new dollars a dollar one dollar two etc so you can keep all the different original texts separate but they are embedded in one big string t now

24:23 The Suffix Tree

24:25 and then we construct the suffix tree for this big string and now if you look at such a i'll show an example in a second um but even without that it's it's clear that because all these dollars are uh unique and different whenever you see a dollar j edge it has to leave it has to lead to a leaf there's no other way um there's no way any other string can share this any other suffix can share this so we essentially have a leaf for every of the for every of the text for every tj and every starting position in the text tj we have one leaf

25:11 and that's the generalized suffix trees we don't take a single text we take the suffixes of several texts and all put them into a joined suffix tree and by building this long text concatenating the text and separating them we can use a black box construction for a single suffix tree for a single string suffix tree to also get the generalized suffix tree without investing uh extra brain power

25:40 so before we get going with this a little question for you to wake up again um this time i just put it as a as a tag cloud so you can put in any string the question is what is the longest common substring of these three strings that are given here um we'll use this as an example in a second for the generalized suffix tree and then you will see how we arrive at the same at the same answer but i first want to see if you know what the problem is so remember the longest common substring has to be a substring of all three strings you have to find a single string that occurs in all of those three and then among all of those you want to find the longest one you will see that even for this very small instance that just these three strings and they're not even very long it's not completely obvious on first side what is the longest repeated substring but

26:10 Longest Common Substring

26:40 i'm sure you will figure it out i see 10 answers again if you feel like you have no idea what i'm talking about a valid answer is i'm lost or don't know and otherwise uh try to find the longest common substring of b c a b c a c a a b c a and b c a a great words to pronounce

27:20 more can we get our usual 25 and in case you have no idea you just submit anything random i like the fff someone send a number don't don't send the the length sent the actual string maybe you can still edit this come on guys 25 i want to see 25 we got 26 in the previous 31 of the first there must be some people hidden

28:03 20 is good 25 but it'd be better yeah yeah results are coming in that's great two more one more tension is rising there we go awesome okay we have lots of rows for bca and that is that is correct uh for all the other examples um i think a a is no all the other examples are not common substrings they're not um substrings of all the three

28:51 yeah so bca is is the correct answer and um let's see how how would you prove this well you can see the occurrence here in all the three strings

29:06 and uh well it actually occurs twice in the first one so you can take any of the two occurrences um and there's there's no longer such string it's easy in this example to see well the the only longer option would be bcaa because that's the entire last string and there's no no double a in the first one so that won't work with all three strings so how can we do this now systematically and using suffix trees um here's an algorithm and again this might be a bit small

29:40 Generalized Suffix Tree

29:40 so of course we start with computing the generalized suffix tree uh there will be an example on the next slide but i want to give you the the algorithm first you compute the generalized suffix tree for all the strings

29:48 Compute the Generalized Suffix Tree

29:55 that is the core information is in the tree but you have to add a little extra information to find a substring that is common to all substrings maybe let me go back um very briefly to this one what we did here is we asked for the longest repeated substring we asked for any string that occurs at least twice for that um because we use a compact try any internal node of these little dots here any internal node will have at least two different leaves in its subtree two different descent leaf descendants and so any internal node was fine for getting a repeated substring okay now in this new problem of the longest common substring this is not enough we want that this substring occurs in all of the strings so we have to work a little extra for that and what we do is we traverse the suffix tree and we store at each node the subset of all the strings

31:24 the set of numbers j so that um j comma i so uh that's not an i started the the suffix that starts at i in position in in string j

31:56 in the subtree okay that's that's the idea uh once i have this computed and once i have the string depth um i know that i only have to find the deepest the the the note that has uh that stores the set of all strings and among those the one with the deepest with the largest string depth okay remember uh every repeated string gives rise to an internal node but we want an internal node where there is a continuation in all of the strings so we try to find one the deepest node that is labeled with all of this of the strings and deepest in terms of the string depth okay if you go through this algorithm computing the suffix tree takes time proportional to the length of all the texts because that's the text we compute and that we can do this the single suffix tree on and both of the other things are linear in the size of the subject's tree and the suffix tree is linear in the number of characters so again here's this here's this quote from before we found this linear time algorithm now for this problem and uh that's um that's proving a famous computer scientist wrong so here's here's an example that might make this algorithm a little clearer

33:29 it's from the same three strings that i asked you about and um you can see so uh there are different there are different leaves i labeled them here with the actual um string instead of just the the the pair ji but you see that the dollar sign at the end tells you what string it is from right so if if it says here i don't know let's pick um a dollar two that must be this a as opposed to this a because it's followed by dollar two that indicates it's from the second string okay and similarly for all the others and what you see in green these are these subsets

34:21 um so maybe make the entire thing green uh the notes store these these subsets in green that is simply what indices of dollars do i have below me this node has only dollar two and dollar one so it stores one two this node has dollar two dollar three and dollar one so it stores all three and so on for all the others and you compute you can compute this bottom up um if you're if you're a note that only has leaves you just walk through all the leaves and check what dollars are there and you take note of the result if you're an internal node with several children then you just take the union of all of these you have dollar 1.2.3 that would already be enough but you take the union also with 2 3 and 1 2.

35:11 i hope the example is enough to help you see what this algorithm is doing by computing these green sets uh there's the collection of all uh dollar indices in the leaves below this node the second step is computing the string depths again and that's exactly as we've seen it before so let me just add these here and that's two that's a four and here another two and now we try to find the deepest note that has all all three letters all three strings in its label so we can only take this node this node this node this node this node and uh clearly this one is the one that's deepest and it's labeled by bca our longest common substring

35:24 Computing the String Depths