Video 8-4: §8.3 Applications of suffix trees (part 2): longest repeated substring, longest common substring

0:00 Longest repeated substring

0:03 we left off last time with solving string matching with suffix trees but we've already knew we already knew a solution for that so now let's look at a new problem and this is one step in between to this problem I took as motivation initially this longest common pre common uh substring problem and this is the longest repeated substring slightly different um here we have a a single text and in this text we try to find some part some some substring that occurs at least twice so uh there's a substring in the text starting at position I of length L and there's a second occurrence so another starting index J where this also occurs okay the definition allows that these two overlap that's fine um you can Define variant where this is not allowed but here we we uh we are happy with that so in a way this the trivial Brute Force algorithm could just try for every I you could try every J and then see how long you can read uh that sounds like it could even go cubic it's very slow uh and it seems that we have to at least check all possible substrings you can do better than cubic if you check all start and end indices and check if

1:25 they occur another time in the string that's essentially string matching in Disguise so we could could solve that so quadratic time is is easily doable and is still somewhat trivial but that's still way too slow I'm still not happy with that all of these Simple Solutions seem to rely on checking every possible substring of a text if we start an end position explicitly and as long as we're doing that we're too slow we have to uh spend quadratic time to do that but it turns out with a suff tree we can avoid that and the reason is that we don't really care about all substrings all we care about are the repeated strings anyways so there are in a sense many substrings where we can easily exclude them as not being interesting because they only occur once and to motivate why the suffix tree helps look at the example here from from the small um text that we had last time it's it's a small example so the overlap is only small um but maybe you can imagine how this generalizes so in this in this word banana ban um we have two parts aan and an that's two suffixes and they both start with a they have a common prefix so two suffixes and start somewhere in the word

2:52 go until the end if they have a common prefix that's a repeated string because it occurs at the beginning of two suffixes so it occurs at two positions let maybe uh draw this briefly so I have two positions I and J the whole thing from here to the end that's TI and the whole thing from here to the end that's TJ now if they if they have a common prefix that means there's a substring in the text that occurs

3:31 twice because I could put TJ again here and then I would have matches in some some prefix here where these characters are the same okay fine but what does that mean in the suffix tree uh because the suffix tree is a try of all the suffixes there must be a path for these two suffixes as well namely there's the path going to five and there's the path going to seven it's the starting indices now in these two paths they are starting at the same the same node namely the root and then they end somewhere different so at some point they Branch out from each other so they have this shared segment here and then they're differ and that shared segment is exactly the longest common prefix because that's the part of the string that they share where they are the same and uh in this case um it means the suffix tree has to have such an internal Noe because if they have a shared path and then they Branch out they have to Branch out at something and that's always a node so there's an internal node um that you reach with this with this common uh sub with this common prefix now the thing is also true in Reverse any uh internal node in the

4:57 suffix tree is is also the common prefix of two at least two suffixes namely some leaf that is where the paths split at this Noe if there were none of those if all the leaves were in the same child remember it's a it's a compact triy so then this would have been eliminated uh all our nodes have at least two children why does that help us well we've thought we we've analyzed this earlier the number of internal nodes in suffix 3 is at most linear is at most the number of suffixes and so I only have a linear number of long of longest common prefixes to check at most so even though there are many more sub many more substrings in the text if I restrict myself to the repeated Parts there's only a linear number of them that are candidates for being the longest this longest repeated substring in a way that's the magic of the suffix tree that it nicely uh Narrows down this list of candidates for us all right so uh to put that on the slides what we what we discussed the longest repeated substring in the text always has to be also the longest common prefix of two suffixes I don't know which ones but there is there's a

6:20 two indices so that this is uh the longest common prefix um and so as algorithm to find the longest repeated substring is compute the suffix tree there it is takes linear time by the blackbox construction that we haven't shown yet but you can take my word for it then we compute What's called the string depth of all the nodes and uh that's something that'll come up so um let me highlight that and let's do it also here here on on our example it's nothing but the length of the string that leads you to this internal node so it's just reading along here I have one character red so I have string depth one the root always has string depth zero here is also one but here's three because I have three things on the edge going down there there's two and three and here's another two okay now

7:27 systematically Computing those would be uh a search from the root you have a recursive algorithm if you say a recursive function that starts at the root remembers how deep it currently is and whenever you Branch down you just increment that depth by whatever how long the The Edge label

7:52 is um that's Computing the string depths so you do one traversal of the tree that's linear in the size of the tree so it's linear time in the length of the text as well the second step is among all those notes we have to find one that has a longest shared path so it has maximal string depth and that's also easy you just reverse the tree a second time and keep track of the maximum number you ever see as as string depth so the maximal string depth in our example is is not unique there's two places right these two nodes both have string depth three and um so they correspond to the string span or Anna and both of those occur twice in our text you can check this right ban is here and

8:49 here and Anna is a bit more interesting Anna is here and here so this is an overlapping occurrence where it shares the a in the middle as I said that's okay that's allowed uh if you wanted to disallow those then um you have to modify the algorithm a bit but we'll we'll keep it with this straightforward version so we all want have a linear time algorithm as long as we can construct the suffix tree first the rest is all uh done in linear

9:25 Generalized suffix trees

9:27 time now this problem already feels somewhat similar to um the motivational problem a repeated substring in one large text is similar to having this common substring in several texts it's not exactly the same but at least uh you can maybe uh see that there's some some similarity uh so maybe you can hope that a similar trick works and if you start thinking about this maybe you could just take the text in isolation and build the suffix tree for each uh but if you if you play with this a bit you kind of uh don't see that going anywhere um instead what we seem to need is somehow uh a single suffix tree that covers all the texts and to motivate that let me go back briefly again so this this correspondence that an internal node corresponds to a repeated string right that was because there were two paths going to different leaves that are shared until this point and then they Branch off um if I want to find common substrings in different texts then I also need this kind of shared path and then branching off into different strings and uh for that we somehow need something that puts puts all the texts in one big tree but it's maybe not so clear how to

10:59 to do that without losing the information where things come from and so that's a a second little uh concept is actually a simple trick that works um but I think it's it's very useful to um to see have this one in mind uh you can define a generalized suffix tree that works for several texts and conceptually um it it can be thought of as just the suffix tree for the text where you concatenate all the texts if you also um have special markers in between that tell you where each each of the original strings ends uh if you don't if you don't do that then uh a few things um break uh but it's easy to add these extra special markers uh a different marker for each string and then you can use the construction for a standard suffix tree as a black boox it doesn't need to be modified

12:03 um the reason for these for these dollars is that if you take a suffix of all the of this of this uh concatenation of all the strings they can be of different length that's

12:22 fine so here's here's my dollar one dollar two dollar three and so on because these these are all new symbols that don't occur anywhere else if I take any suffix of this say this one okay don't want to run into the car if I take any suffix like this every suffix of this long text will have a leaf in the suffix Tree in t the curly T so there will be a leaf corresponding to this suffix now because all these dollar symbols are are uh are different there's no way that this dollar two symbol occurs in any other part in the text so this Leaf will be a branch on its own at the very latest when this dollar two comes along it's an edge that is that is only once there and you will never have um anything anything else occurring there uh there's no no way to have that shared um so these these dollar edges always lead to a leave that's um that's what this here uh what this here says and that means conceptually I can I can ignore that this suffix contains a copy of all the later texts as soon as I have a unique Leaf here I could say that leaf corresponds to the cha text and the I position in

13:54 that text so there a little bit of doing arithmetic back and forth for from the coordinates in the global text to the local text but you just subtract all the lengths of those before it um we'll see an example in a second but in a way uh what you should take from this slide is uh there's a simple way to generalize the suffix tree so that the same is true as before we have a compact try of the suffixes of all the texts in the in the tree and and now the leaves don't just tell me where the suffix starts but they also tell me which of the texts it was that's what I conceptually want from this generalized suffix stream um and algorithmically it it works by just doing a standard suffix Tree on this on this artificial text concatenating everything with special symbols in

14:55 between uh before I move on to the example time to wake you up with a little question question this one's not a trick question it's just about being sure that we have the the same definition in

15:18 mind and then you also know uh what the answer should be when we look at the uh right almost have our 50 people together by the time I switch I guess we have

16:18 it um yeah a vast majority is the same opinion there always these these word pictures make it look like oh there's a few people put P BCA but it's actually 50 votes for BCA and that's that's of course also the right answer um because this last string is so short there's really not much uh not much else we can do unless we can fit the entire string of length four into the others which we cannot uh the longest common substring can have length three right and so because BCA occurs in all three and the first um even twice that's that's the answer now how can we find this algorithmically uh it is similar to the longest repeated string but uh there are two changes one is we have to use the generalized suffix Tre because we have different texts and the second is we're not happy if the text just occurs twice anywhere it should somehow occur so that it occurs in each of the text T that's a second constraint and we can check both of these so the algorithm works as follows it it computes the generalized suffix tree for our collection of uh of texts then [Music] um we uh we compute the string depths uh in the Second Step same as

17:03 Finding common substrings

17:51 before another thing we compute is um the subset of texts that have a leaf below a certain internal node so uh here's how to do this in a bottomup traversal but just to explain what this this label this annotation should mean every internal note or every note in general has a set of indices of texts so that there's some way to run through that Noe with um a suffix of that text which also means the path from the rout to that node occurs in that text and you you just compute for every note which texts does that uh occur in I'll show an example then I guess it's uh it's much clearer uh but let's first look at the running time so this here is

18:57 um this is order n for the size of the generalized text but the size of the generalized text is just a the text is the concatenation so the size is the sum of the

19:11 sizes I guess plus K but uh we assume that the texts are not empty so in terms of bigo that's the same for that second step if we look at how it is implemented as a traversal you can do a bottomup traversal this is again uh we haven't discussed um depth research in tree TR in detail in this module but uh you'll you'll either do it next year or you have done it in the python module um so you there's a recursive function you start at the root and then you recurse to all children and bottom up traversal means you do something after um you do something uh coming back so when you reach a leaf you know this because you don't recurse further um then if you have a leaf ji meant it's starting position I in text TJ and so we just put the Singleton set j a leaf of that type corresponds to just text the text shape if I come back up from the recursion and I have computed those sets for all my children I can now compute the set for myself for this internal node by taking the union of all those sets and if you do this in that way as a recursive procedure it's time is linear

20:26 in the number of nodes in the suffix tree and that's again uh overall order and time because we have order n uh nodes in the suffix tree the computation of the string deps is like before that hasn't changed um it's just a using using the generalized suffix tree but it looks for that computation the same as as an ordinary suffix tree and the last step is also the same except that we have to check this additional constraint so we want to find a note that has largest string depth the longest repeated thing but we only include those internal notes where we have the full set of all texts where the set of indices of texts that have a leaf below them is the entire set one up to

21:21 K and here's here's the promised example it looks a bit wild maybe because it's a larger larger text that's the generalized suffix 3 for these three example strings so you see um let's take example for example CA and then dollar two there must be a path from for this because it's a suffix of the second second string so if I go down with

21:54 BC uh sorry CA C A and then dollar two brings me to this leaf and that's that's the leaf that corresponds to that suffix um and similarly you can do it for all the others now I've uh already put the string depth in the nodes um which by the way if you represent the suffix tree as a compact try the numbers in the nodes that we KN that we need anyways for the try is also the string depth I don't know if you made that connection already but they are really the same so when the algorithm says compute the string dep it actually doesn't have to do anything um the representation of the suffix tree would already know that number it's just on the human version that we didn't show them the green numbers we still have to compute so let's uh look at an example there as well uh for comp for completeness every leaf would have a green number that corresponds to the dollar that is at at its end so this is a leaf that corresponds to a substring from or suffix from text 2 this is a leaf that corresponds to a suffix from text x one that means this internal node corresponds to a repeated string so a BCA is a string that occurs in both text

23:10 one and text two let's double check that a BCA I can find that here and I can find that here okay it does not occur in text three that's why this is only one and two and not also index three another example this one here there's a leaf that corresponds to text three and two so this corresponds to t uh two and three but not one and the path down here is AA so indeed there's AA in this and AA in this text but there's no repeated a in the first text okay so you see how this how this is going the bottom up traversal is then just annotate all the leaves and for every internal node take the union of the of the the sets added at the children now from all those from all those notes that really have all three which are just these we now have to pick the one with maximal string depth and in this case that's clearly this one is the only one with three that is circled in blue and that corresponds to the string BCA that you identified in the question before okay

24:31 yeah I wonder if starting with the example made would have made this clearer maybe I'll swap it around so let's wrap up we uh we learned two things um we learned there is a generalized suffix tree so you can essentially treat it conceptually as having the same kind of structure as a normal one but it also remembers the suffix of what text are we talking about and you can get that for free second trick we learned we can do some extra annotations in the tree we can get the string depth of a node so the number of characters on the path to that node we can get that for free with a linear time extra pre-processing and we can do things like this find the set of all indices of texts that are below a certain a certain node we can also do that in in a linear ter I'm pre-processing

24:40 Summary and conclusions