Video 6-3: §6.3 Applications of suffix trees

0:00 <Untitled Chapter 1>

0:02 with that let's look at some applications of the suffix tree now that it's fresh in everyone's memory what suffix trees are let's motivate why they are so so useful and popular before we spend more time on thinking about how to construct them

0:18 Applications of suffix trees

0:21 just to reiterate we're storing suffix trees like this if we represent them in a computer so that's if you want to analyze space and time you should think of this but for Designing algorithms we'll think of the representation on the right uh just because that's the same information just stored differently and much more human friendly

0:48 a little uh nitpick or extra little thing that sometimes is important and is is not a problem we assume that every internal node has a quick way to jump to one of the leaves and just as a tiebreaker we assume that every every internal node in here has a pointer to it it's left most leaf which could be silly here if it's just the child but you know it could be um in all of these examples it's just one Edge oh come on uh in principle the tree could be fairly big the sub tree of a certain internal nodes and it's not guaranteed that you can jump in one step to a child to Leaf in all cases

1:44 foreign I guess it also depends on how you order order the children well we'll just make this assumption to analyze algorithms uh make the the analysis a bit easier so when you have an internal node you can quickly find one of the leaves in its subtree

2:07 uh I don't think I'm using this a lot but sometimes just as a an abbreviation TI is the if suffix starting at position I now before we present you the solution maybe you can figure this out

2:36 if we have a suffix tree like like this one that's the same as on the previous slide what does that tell us about uh occurrences of this pattern A and A

2:51 I tease it the whole unit as saying we'll do text indexing we'll find patterns in the text quickly now I've spent a lot of time talking about tries and suffix trees without making the connection

3:17 um I'll show the big tree instead the pattern is a and a I don't really ex expect you to see it yet but I thought it's useful to First trigger you thinking about it before I give the solution away

5:00 okay more more words come in 27 should we do again the 35 okay awesome so many votes for many answers there's also many correct ones okay as always you resist the urge to change your answer much

6:25 I hopefully doesn't tell us nothing uh it occurs it tells us that p o curse in t I'll show you in more detail why and it also tells us something about where what indices and we can deduce from that how often let me just uh

6:46 um map that on the next slide I think at least we want to draw this picture so what's the connection between a collection of all suffixes and pattern matching or string matching uh the reason is is just if if the a pattern P occurs in the text T then it is a prefix of a suffix in t

7:14 that's just throwing some fancy words around so if that's our text T and we have our pattern occurring somewhere then there's a suffix of the text starting here that's some t i where p is a prefix occurs at the beginning all right great what does that help one thing I haven't emphasized about tries but uh you could have maybe figured that out yourself you can actually search for things in the in the dictionary that have a certain search as the prefix

8:00 let me do that here first so what happens if we just Traverse with a and a in our suffix tree start at the root a and a we end up here that's what happens uh what does that tell us it tells us that first of all we didn't fall out of the tree so we didn't get stuck in some way and following this green pointer or just looking at the subtree here we see there's two leaves so there's some way to continue from a and a to a longer string that's stored as one of the leaves in our case the leaves are not arbitrary strings but they are the suffixes of our text so there are two suffixes in the text that I can find by reading a and a and something else after that so both of these suffixes have a and a as a prefix which says at positions one and three there's an occurrence of a and a and that's all the occurrences that there are so in a way the suffix tree encapsulates or the the sub tree we reach by finding the pattern encapsulates everything we need to know about the matches in the text that's why suffix trees are so cool they have all that information tidally collected in one node

9:30 and then we just have to walk around this sub tree in a little more structured way that's what I have on this slide so we we try to Traverse with our pattern in the tree

9:36 Application 1: Text Indexing/String Matching

9:50 following the next Edge when we can like in our example A and A when went nicely through and then there's there's different cases what can happen so we had example a n a where colloquial I would say we traversed in the in the suffix tree and we ran out of pattern we reached the end of the pattern a and a brought us here and so if that's the case we find all the leaves in that subtree that's all the occurrences of that pattern now um there are also slightly different options if you have the say the pattern ba

10:40 you would start traversing this Edge and then you're you're stuck you run out of pattern in the middle of an edge I mean figuratively speaking it's a remember it's actually a compact try so you would you wouldn't really get stuck in the middle of an edge but um you could match a prefix of the edge label and then you run out of pattern turns out this is actually the same as if you were just going to the next uh next node below if you just complete reading the edge and ignore that you also get all the occurrences are in the subtree

11:25 a different case occurs if we fall out of the tree um say the pattern NB we start here let me go here and then B is not in the tree there's no child Edge to follow that means n b doesn't occur anywhere

11:53 so we can get stuck in two ways we can get stuck at an internal node like in this case then there's just no child Edge for this this um a variant of this where we foreign

12:16 Edge but then we fall out at this point right that's technically a slightly different case but the same conclusion if at at any point we can't Traverse with our letters because there's no child Edge starting with that letter or it doesn't match the remainder of the the label of the edge then we fall out and the pattern doesn't occur

12:42 technically there's the third case that we run out of tree we continue reading the pattern and we reach a leaf and can't continue now it turns out this is for our application

12:54 this can never happen as long as our pattern doesn't contain the end of word marker so normally we have a text and we assume we are looking for some actual string in the text not something involving this this dollar symbol and so if the pattern does not contain the dollar it can't ever finish reading the label because all the labels leading to an edge must stop with dollar that's the end of the text so we can never really reach a leaf

13:39 so if dollar not in p yeah if you include that case you can also handle it it's not not necessarily a problem but we don't normally have to worry about it

13:56 okay a slight nitpick how long does this take so it takes us order P time the length of the pattern to find that we're in one of those three cases but then what do we do with that if we're in case two where we have half matches we can find with this green pointer from before to the leftmost leaf in constant time we find one occurrence if the goal is to find all occurrences then we have to Output all occurrences so we we can't do that in just that time so if the problem is to find any occurrence we can do it in order p time if we want to find all occurrences we have to walk through the entire subtree and output all leaves that we reach and that can take more time if they're more currencies than the patterns long that's possible

15:00 okay we've discussed most of these already um some other examples let's come back to something similar to this opening question that was straight string matching in a way we already knew how to do that it's just now that we can build this suffix tree Once and keep it it's useful if you have to search many patterns but let's look at a different problem where the suffix tree is is um of much more yeah essential use uh that's a the longest repeated substring problem we have one long string and we're trying to find some substring that occurs at another place so we're trying to find a substring starting at position I of length l looking for the longest such so the longer the biggest l so that there's another Precision J where the same substring occurs okay

15:05 Longest repeated substring

16:04 the formal definition is just here to emphasize the two occurrences could be overlapping which maybe is not what you immediately would have expected that actually has use cases that we'll come back to so it's not just an esoteric puzzle if you want how can we do this we definitely don't want to check all substrings of the text and check if they occur uh that would be really slow now again suffix trees to the rescue if we have something shared some string that occurs twice uh picture

16:47 so if there was an occurrence of some something here and here I'll call this P but it really just is a substring of the of the text that occurs in two positions then there there are two suffixes of the text starting here and there that start with the same string p two suffixes of T starting with the same texts the same characters so this bit must have a joint path in the suffix tree because we're traversing uh the the suffixes letter by letter so example um in our in our well this is the running example for the for a long time so get used to Banana van uh we have a band and a n so there's two occurrences of just the letter A that's one one repeated string now if we look at a band a ban and a

17:54 n they have this shared common path that has label a and that's no coincidence it's always like that whenever you have an occurrence of something twice in the text there will be two suffixes that share this thing as their common prefix

18:16 and that means there must be some internal node that we reach from the root with label a or general label p so all we have to do to solve this problem to find the longest such repeated string is to go through all of our internal nodes and check if there are two leaves below them then the path from the root to that internal node is a repeated substring

18:53 to reformulate the question the longest repeated substring in a text is the same as the longest common prefix the longest prefix that's identical occurring in two suffixes okay and well you can you can narrow it down further um but it's it's two leaves how can we exploit this we first of all compute the What's called the string depth of all the nodes that's just the number of characters that I have to read from the root to reach that node in a compact tray you don't have to do that it's actually the number that's already in that note but let's do it here because we're storing the human friendly version we have to read one a to get here the root always has stringed up zero one character to get here three characters to get to this one a n is two another is three and another two for this one that's all all internal ones uh if you worry about how to do that again you don't really do it in the compact try you already have it otherwise you could do a traversal of the tree uh a recursive function that remembers the current depth and passes it down and then the second step for finding the longest repeated substring is to just pick any node that has maximal string

20:20 depth so we could for example take a and a that's one of these and then the path to that node from the root a and a is one of the maximal repeated substrings and a and a occurs uh in the suffix anaban and a nanoban so it occurs in two places and it's actually overlapping right if you if you look at band Nano there's Anna and Anna okay do I have to write this down

21:04 so the two occurrences are Anna and Anna they they reuse the a so the two are overlapping but that's all right that's that's allowed there's a second equally long repeated sub uh repeated string if you pick this one instead also has stringed up three that's ban and it tells you look at position six and zero ban ban right magic right uh no of course not magic is the definition of the suffix tree uh but the the tricky bit again only is finding the suffix tree Once you have the suffix tree this algorithm is is fairly simple to do Computing the string depth is not hard and finding the node that has largest string depth is also not hard

21:55 so we can do it in linear time after building the suffix tree we're almost almost there to solve this original problem the only thing that's missing is suffix trees so far are just for a single text and the other problem remember was the longest common substring you have several texts and you you ask what's the longest thing that occurs in all of them as a substring but that you somehow need to have a suffix tree for several strings it turns out that's actually not hard to do um there's a a simple way to to reuse the suffix tree as a black box and get this done and that's that that trick is known as the generalized suffix tree uh all you do for that is Define a text like this so you take all your individual texts T1 T2 and so on and you add different dollar signs after each so you you reserve a new marker to say that's the end of text one that's the end of text two and so on and then you build the suffix tree for this for this new text ignoring that it is composed of these individual texts and if you look at the resulting tree you will find that there's always some dollar J edges that lead to leaves just because they

22:00 Generalized suffix trees

23:25 occur in only one place so you can always find for every for every suffix of every text you find one leaf so in a way the the very same trick works it's just um a neat little little extra idea that that's needed for that

23:48 Clicker Question

23:51 um because we're running short on time I don't think I'll do the question but uh let's um let's just do it together I mean this this three strings what's the longest common substring because this last one is so short we can just brute force it in a way so BC occurs in all I can see that here but BCA also occurs in all three good so PCA should be it because pcaa doesn't occur okay uh yeah I think that question number was that useful but a wake up time you know and so on

24:29 Longest common substring ► With that new idea, we can find longest common substrings

24:34 so how do we do the longest common substrings with this uh let me show the example um maybe the algorithm we don't have time to discuss in detail that's the generalized suffix tree for these three strings that we've just seen in the in the example and so you see there's um all the suffixes of all the strings must be there so there must be a a from this third for example so you could follow a and a and then there's an edge with dollar three telling me Oh this is a suffix of the third text

24:39 Longest common substring - Example

25:13 um there are more more occurrences of a a in text 2 so you could also have a a b c a a a b c a that brings you to that one and so and so forth so the way to construct this is put all the text uh behind each other concatenate them and build the suffix tree for that

25:37 now how do we find a string that occurs in all three texts there's one extra extra trick in this tree that's these green numbers the green numbers just mean there is some Leaf below this note that has the appropriate dollar Index so the one two three here means I can find a one and a 2 and a 3 among my leaves whereas for this node the 1 2 means I only have a one and a two I don't find any dollar three below me

26:16 if we have that information we can find a deepest node in terms of the string depth same as before and I already put the string depth in in the the notes so this one this one looks like the deepest right uh has a three we look for the deepest node that has all green numbers

26:36 because that means the string I can read from the root to this node I can continue that and reach all three texts so there's a way to extend that string to a suffix for each of the texts which means it occurs in each of the texts and here that's BCA which we figured out before

27:01 all right so that was the that was the quick version I spelled it out in in detail as code it's basically describing in in several steps how to compute the green numbers how to compute the string depth and then find the deepest node in terms of string depth that has all numbers there's not much more going on there and the only tricky bit really is to construct the suffix tree again

27:05 Application 3: Longest common substring

27:37 all right cool so you've seen uh some immediate applications for string matching and some more Advanced applications where we really use the inner workings of the suffix tree to maximal extents