Video 6-4: §6.3 Applications of suffix trees

0:00 Intro

0:02 so in the next sub section i want to show you what you can do with the suffix tree taken for granted that we can construct it efficiently in in linear time in the length of the text

0:13 Applications of suffix trees

0:16 for that um there's one more thing we need to add that's uh written down here and just as a reminder the try is really stored like this it's a compact try so only the first label on each edge and we store the index where the next character is compared with etc on the slides i will always represent the suffix trees like this where you see the entire string that would be on this edge if we would spell out all the characters um and then i can leave out the index in the internal notes uh a second thing that will be it's a technical detail if you want but it is important for the running time statements that we make and it's also easy to achieve i assume that all internal nodes so every of these these red guys has a pointer to the leftmost leaf in its subtree so in this case it's kind of trivial but

1:24 it could be that it's not so clear how far away the next leaf is uh in particular it could be in in this example there's always the the case that you have um just a single edge to go to some leaf but you don't necessarily know which which edge that is here it always happens to be the left in the picture uh but i think that is that is coincidence in this example and doesn't necessarily have to be like that so it's just an assumption every red internal node stores one pointer which goes to the leftmost leaf in the subtree it's not super vital that it's left the leftmost a leaf is usually enough if you wonder how you could construct those if they are not already there you represent this tree somehow in memory and then you do a a bottom-up traversal and you can start start from the leaves you keep in mind in the recurs in the recursion what is the leftmost leaf and then you insert this once you go back up the tree and you can always when you go from an two internal nose back to the parents you can inherit the left most by taking it from the child

2:52 all right um not sure if i use this very often but t sub i is just the shortcut for this suffix starting at i i think that should be it um now the first application will be our good old string matching problem the text indexing version thereof and i'd like you to think about before i tell you how it's done oh the suffix trees help with that so if we if we have the suffix tree of attacks like on the left and i want you to work on this specific example you can make it a bit bigger if that's small

3:37 what does the suffix tree tell us about occurrences of this pattern ana in the text and i know this uh you can read the entire text from the suffix tree and then figure it out but that's not what i want you to do i want you to ignore that the text is known and just work on the suffix tree and try to figure out what what does the tree alone teach you about the occurrences

4:37 just have 10 votes so i'll give you a few more minutes seconds in a way this question contains all the things you've learned about tries and and suffix trees so i think it's a it's an important one so i'll give you a bit time

5:32 if you figured it out where it occurs and you figured it out on looking at the text try to go back and see if you can argue just on the suffix tree

5:52 i think i'll i'll show you the results and briefly on the screen as well um so we have a lot of votes for the fact that p occurs in t and that's true um and in addition we seem to be able to tell that it starts at index one yeah so let me switch back here um

6:26 it starts at index one but it actually also starts at index three not sure if that's uh was clear for all all of you and so let me just show you how you would come up with this conclusion in the in the tree okay so we have to find this this pattern a and a

6:47 in the suffix tree it's a try so we do what we always do in a try we search by starting at the root we follow the branch for a and a and now we stop because we ran out of pattern so what does that mean we found some internal node here now first observation we didn't get stuck we could follow the path so there are ways to continue this pattern into a suffix of the text and that means it definitely occurs somewhere in the text because the pattern is a prefix of a suffix of the text that's nothing else than fancy words for saying it occurs in the text right there's a a part of the text where the pattern occurs at the beginning moreover all of these suffixes are in the subtree of this very node that we stopped in the search with all the patterns that are extending the that all the suffixes that start with the pattern are below this because they all follow the same path up to this point at least so the number of leaves below this there's two leaves that means there's two occurrences of the pattern in the text and if you look at the index in the leaf that's the index where the where the pattern occurs

8:15 and so that's exactly the indices one and three where we find anna in the text banana band okay good so if you follow this then the algorithm on the next slide will be quite natural and that's our first application of suffix trees our good old friend string matching

8:35 Text Indexing / String Matching

8:45 just that in this in this case we tend to think of it that the text is static and we search several times but we don't have to so one way to do string matching is construct the suffix tree for t and then exploit this fact that i mentioned before p occurs in the text exactly if and only if p is a prefix of a suffix

9:13 and so here's the algorithm spelled out again that we are following to find these occurrences we search the pattern in the try by following it down from the root and then there's there's really three different options in theory in principle that can happen if we ever get stuck so there's two options two sub cases if you want we are at an internal node and the next character of the pattern there's no edge from this node that we can follow then we're stuck at an internal node we can also get stuck inside an edge remember so here we have several characters on an edge maybe we tried to find b a a and not b a n then we would fall out of the edge with the third character now remember we would normally not discover this until we jump to the leftmost leaf and then start comparing from there but let's ignore that fact and abstract from that here and assume we have all the characters on the edges present so that's two ways how we can get stuck if we ever do get stuck that means the pattern doesn't occur in the text because but there was no single suffix that started like this so i can't continue following this path the other option is we run out of

10:36 pattern as in the previous example so we could read the entire pattern and we end at some point in the try and that can be either at an internal node like in the previous example or it could be in the middle of an edge but both are really the same in in this case if you if you check the characters inside the edge then the pattern occurs at all the indices of the leaves in the subtree of where used where you stopped

11:10 in theory there's also a third case we could run out of three so we could traverse and traverse with our pattern and then we reach a leaf and the pattern would like to keep going this can't really happen in our scenario because we added this dollar sign so if if dollar doesn't occur in the pattern and we kind of uh enforce that then we can never reach a leaf because the leaves always have us last character the dollar sign and that's forbidden in the pattern so that case doesn't occur if it if it would occur

11:48 we could still handle it by going to the the leaf that we reach and check if if we find p there so in total the algorithm follows the path of the pattern and after at most length of p steps you found one of the two cases the first or the second and so you can either say there isn't a match in the text or you can report at least one occurrence in constant time by following the next leftmost leaf pointer that was the green one before

12:50 so that's how you can find a first match in in the length of the pattern time if you want to report all matches you can also do this but you can't keep it in that time because the pattern in the worst case could occur at every position in the text so even to just produce the output you need more time but how you would do it is if you wanted to report all occurrences of an a in the text you would go from the root to a and then you would just walk through the entire subtree and report all the leaves you found that's linear in the number of occurrences so you can report all occurrences in time length of the pattern plus number of occurrences and that's again best possible you need to read at least the pattern and you need to write out all the positions where it occurs if that's the goal so you can't really beat that okay that was the the first big application of um suffix trees first string matching i have some examples that illustrate all the possible cases uh what do you feel like shall we go through those or is it clear enough without the examples who wants to see examples who does not want to see examples

14:12 um okay so i'll go for the middle and go through all of them but quickly i'll try uh let's let's do this one so a n n a n bloop i fall out of the tree so that's a case of we get stuck at an internal node okay doesn't occur ah let's see if i run out of colors baa so b a and then bloop i fall out of the edge inside the edge so that's that's this case doesn't occur right i would have had to match the n um anna was the example from before so maybe we can skip that one right that was a n a so we end at an internal node and then we can use the the green pointer to jump and report three as one match um ba okay yellow was maybe a mistake uh

15:24 we traverse the same edge as with the blue but then we stop in the middle of the edge so here it's not a mismatch but it's this case and so the occurrences are everything below here so we just follow the rest of this edge and from there on it's the same as the orange case and now the last one might be more interesting that's my color for corrections so briar

15:52 that's a tricky one we would normally say after this b we fall out of the tree because there's no r so what what this shows is if you have the the compact try you would actually just look at the first character and that matches so you would jump over these and then a

16:18 matches again so you would jump down to this leaf and so once you reach that leaf you know the text that's stored there is actually the entire text here and so you would align this like this and would notice that there's a mismatch at the second character okay so that's in a sense um the same as

17:09 so if you go by the the proper implementation as compact dry then you wouldn't really check these other characters until you reach the leaf and so that's something to keep in mind for the conceptual algorithms on the slides i'll assume we have the old labels on the edges and you can always handle these two cases in an implementation separately so that you you fall out of the edge or that you run all the way to a leaf but actually have jumped over mismatches okay

17:57 Longest repeated substring

18:05 have more applications and this one is slightly related to the motivating question but we're one step ahead one step away from from that one so in this case we ask for the longest repeated substring of a single text so we have a text and we would like to find two indices i and j so that

18:33 if you start reading at i and j you see the same the same substring so maybe for illustration a little picture this is this is your text you're trying to find positions i and j and when you read here you read the same string up to a certain point so there's a length l

18:56 so that this and this is the same string and you try to find the longest l so that you find this positions i and j uh this indeed something will essentially come back to in disguise it'll be a sub problem for something later in compression but we don't need to worry about that for now it's also just an interesting question i mean a curious question you have a text what's the longest thing that that occurs at least twice as a literal copy again if you if you think from first principles it looks like one of these problems where you have to go through all uh substrings and so it smells quadratic but you can actually do it with suffix trees again in linear time uh it's a lovely thing to ponder about if if we have more time but i think for this one i'll just have to give you the key inside away the the trick here is that if there is some repeated string in the text like in in this one that means there's a suffix starting at i and a suffix starting at j which both start with the same string namely this green part

20:31 what does that mean in the suffix tree well there's a suffix for there's the two suffixes that are stored in the try and if they start with the same string they share a path from the root up to a certain point and then they diverge so there must be

20:49 a shared path in the suffix tree and if it's the longest shared path where they diverge it actually ends in an internal node so let's see on an example what that could look like in this short example the okay here the two here are two suffixes and they have the longest common prefix of just the single a uh well if you try to find a bigger example things get a bit unwieldy so bear with me that the example's a bit small but because those two have the longest shared prefix a they share a path up to this point and then they branch off so there must be an internal node at this position that we reach with the path a and of course if we go down to a here is this internal node it's not so surprising here but in general it could be further down it could be a long shared path and indeed there are other examples here of longer shared paths we'll come back to that in a second

21:54 now how do we find the longest repeated substring first observation any internal node corresponds to some repeated substring because the path from the root lies on at least two paths to a leaf so if we want the longest we want the one that has the longest path from the root okay so in other words that's the longest common prefix of any two suffixes

22:28 this brings us to what is called the string depth of a note that's just the length of the path from the root so maybe let's annotate the tree with these string depths the root is at zero then here this one has just a so it's at one a n is two a and a is three this one has three it's just a single edge but three characters and so that's it so we can do this in a bottom-up traversal again sorry in a top-down traversal in a depth-first search from the root we start with the root at zero and then indeed the compact try in a sense already stores the string depth because it stores the index that we compare next that's exactly the string depth so we don't even have to really compute this uh if you represent the the suffix tree as on the slide it seems like this is another step

23:27 and then the second is you just look for a note with maximal string depth so in this case we have two examples so there's two longest repeated substrings ban and anna okay and so how much time does this take in total we need to construct the suffix tree takes linear time using the magic black box algorithm we need to find the string depths of all the notes but they're actually already there and we need to find a note with the max with a maximal string depth uh and that can be done by just walking through the three ones and keeping track of the the deepest so that's linear time overall okay that's pretty cool and it's already quite close to this longest common substring between different strings uh but there's there's one thing that stands in in our way to solving this this motivate motivating problem the motivating problem where you find the longest common substring talks about several texts and so far our suffix tree was always just for a single text for a single string

24:40 Generalized suffix trees

24:42 there is a way though fairly conceptually easy to get from a suffix tree for one text to suffix trees for several texts and that's called the generalized suffix tree

24:56 so uh that's just the observation we would like to uh put down close the loop to this motivational problem so we need something that works for several texts what does not seem to help is to build the suffix tree of all the texts individually so you could build one suffix tree each but i don't know of a way to make use of that really because what we need is the information combined of the texts we need to find the things that are repeated between texts so i can find all the repetitions inside a single text with this but that's not really that's like a wrong wrong wrong question so instead what we'll do is we'll force all the texts into one big text using a little hack if you want we create an arbitrary an artificial new text where we concatenate all the strings that we have but we separate them with new dollar signs which are different for each text so we create k new characters so that this dollar i tells you which of the substrings ends there so at the expense of k new end of word symbols we can construct a single text and construct the single suffix tree for this concatenation of texts and that's it that's called the generalized suffix tree

26:29 uh there's a slight simplification you can make if you have an edge in this generalized suffix tree that has some some dollar j you know that it will always lead to a leaf because these dollars are unique they occur at only one place so there's no way how they can be shared um with different positions so they will always lead to leaves

27:00 we will have for every text for every text j and every position in the text j i we will have one suffix so that's the suffix starting at position i of text j

27:22 we will have a leave for each of these of of these pairs right for each for each text in each position we will have one leaf and you can figure out that this is a certain starting position in this text t you just sum up the text the lengths of all the previous texts and add i

27:44 so there's a way to translate between the the indices in t and these pairs which text and which index inside that's uh use for take for granted okay a short one to wake you up that one has has nothing to do with suffix trees yet

27:55 Clicker Question

28:14 just reminding you of the definition of the problem before i'll show you how this works with suffix trees i want to show you the algorithm before we run out of time so i'll

29:07 pca is is the right answer right that occurs here and here and here and here it occurs actually twice so you can okay i didn't show it and this first string even occurs twice but that doesn't hurt so we hope to find this pca

29:28 i'll show you an example of the generalized suffix tree for these three strings on the next slide um i want to briefly first highlight what we need to do so by building the generalized suffix tree we basically have the information that's needed there there's only one piece missing

29:47 any path from the root to an internal node corresponds to some repeated string but that's not good enough i don't know where this repeated string is it could be just in in two texts not all or it could be two occurrences within one text so i need one one second piece of information

30:11 and so i annotate all the notes in this generalized suffix tree by all the substrings that have some leaf from this substring below it we can do this bottom up by for the leaves just take the single string they correspond to and when you go from children back to parent you just take the union of all the substrings that's how you can compute this in in linear time

30:42 then we also compute the string depths as before and finally we report the path to the deepest node in in terms of string depth that is annotated with all the strings so there is a leaf for all the strings below this node and that means it's a shared substring that occurs in all the strings okay

31:11 and here what i what i noted here is is the total length of all the strings they don't necessarily have the same length but you just sum up all their lengths and that's roughly the time you need to build the suffix tree as well and all the rest also runs in this same time so here's um here's the example how this looks like for the three texts from the question so here are these three you concatenate them with the dollars in between in in this order left to right and you build the suffix tree for them and i guess you'll have to take my word for it for this one that this is what what comes out of it and these these green numbers here these are sets of numbers one two or three and there can be one missing and you see how this is formed uh you have a dollar a two here so this is a leaf that corresponds to the second respectively the first text so you have a leaf for text one and text two below four but none for below this note but none for text three you do this for all the nodes here you have something from three and two so that's why there's two and three

31:26 Longest common substring - Example

32:21 if you go to this node you take the union of these and you don't even need the other leaves to see that there's something from all three strings below it so that means the path from the root to this node occurs in all three strings that's brilliant but it's not the longest such repeated one indeed we find here is one that has string depth three and that's the biggest string that we find in this example where all three are present and the path from the root to this node is pca that's our longest repeated substring that you also found okay

33:04 so it's uh it's only a small step from a suffix tree from one text to one for several texts and with that little trick of adding these dollars in between you can use the construction as a black box for one text by creating the concatenation and thereby solve this is really a challenging problem that at first seems to require quadratic time or more

33:30 cool that's the end of the first round of applications there's more to come but that will reserve for next week