Video 6-2: Suffix tree applications

0:04 Let's see a few examples of how we can use suffix trees for some string problems. Um just as a quick reminder uh what the suffix tree will really look like. I'll denote this by this calligraphic t because the normal t is the text. uh what's really stored is is this compact try but you will think about it in this way and the only difference is that we have to think about these extra comparisons with the characters we skipped that we have to do. Uh another kind of technical assumption that just makes some statements a bit easier is that every internal node has a pointer to the leftmost leaf below it. And uh in this case it's is always just the left child in this example, but that's because my example is too small. In general, it could be that some some node has a long path before um there's a leftmost uh a child a leftmost leaf. And then this pointer might jump over a long long branch.

1:21 I wonder if we always have the dollar edge though. Um well, this one shows that the answer is no. Right. It's just a a a property of the small example that here it looks like you always have from each internal node an edge to the dollar but uh not every prefix is a suffix. It's not in general true.

1:56 Okay. Uh these these pointers we'll just assume are there. It's easy to fill them uh in a linear time pre-processing over the tree. Uh where it's convenient to assume they're all they're already stored. Um okay, I try to get rid of most of these occurrences, but uh maybe for saving space, I sometimes still use ti for the suffix starting at I. See, that's the applications. The first one is finding a pattern in a text. Exactly. So the the very problem we've spent a lot of time thinking about last week and earlier today, we can also solve that in a suffix tree. And the running times are a little different. First of all, clearly a pattern occurs in a text if it is the prefix of some suffix. Why is that? Well, if there's an occurrence here, I can start the text here and then the pattern is a prefix of that suffix of the text, which means in the suffix tree, I can search for my pattern starting at the root and then I'll eventually lead uh get to some point here where I've read all the pattern if it occurs and I can try to find from there the starting point of this match.

3:23 That's the idea. Um in more structured terms what you do um depends on uh how the tree and the patterns uh the pattern continues. You start at the root and uh there's different options of what can happen. Uh one option is that we get stuck uh and cannot continue reading with the character that is in the pattern. So for example, uh this first string here, if you read a n and then another n, there's no outgoing edge for n. So here I'm I'm falling out of the tree. That means I couldn't find any any occurrence because there's not even there's already a prefix of the pattern that doesn't occur anywhere in the text. Then uh P doesn't occur. There's a subtle version of this which is if you're inside an edge and you fall out of the tree. That happens with this uh with the second example. Uh here you would say BA is fine but then this N I'm falling out of the tree.

4:32 Now remember this is different for the algorithm because it wouldn't actually see the A and N. It would only find out after get getting to some leaf and checking the characters. But you can still check it. Um that's one of the cases if we fall outside of uh the tree inside an edge conceptually this is one of those places where we might use the pointers I introduced earlier. You might at this point jump to the leftmost leaf read the characters from the suffix and you could immediately check here whether the characters match or not. It's one way to do it. Um, another option of what can happen is that we run out of pattern. So, we've read the entire pattern, but we're not at a leaf yet. Uh, that could be this one. So, you start here. You read A and A. Now, we're stuck at some internal note. And that's a case where the pattern occurs, namely in all the leaves that are below this point. In particular, if you want to find a first match or well one match, we can again follow this um dotted point this this uh pointer to a left close leaf. Then that position three is the starting index of an occurrence of that pattern.

5:59 So again I can find this one in constant time. Um at this point I might have to check if I skipped over characters if they actually match. I only have to do this once, though. Either they match for all of the leaves here or they don't match for for any because they're all the same in the leaves here.

6:26 Uh there's hypothetically um another option that we run out of tree. Uh this can't really happen with a dollar, but in principle it uh it's another option if you think about the case distinction. It could also happen that you reach a leaf and the pattern keeps going. Um because we assumed that the dollar doesn't occur in the patterns. Well, uh I'm telling you now, it's not on the slide. Uh then this doesn't happen. [snorts] Yeah, I think the the subtle case is is what's mentioned here. You could um um in this case you have this lovely condition. If you just compare the first character, you would follow down this edge because the B matches. Then you skip two characters and you would take the A and go down here. And then uh you're skipping over a whole bunch of things. um and you would essentially run out of out of pattern because you don't continue with the characters in the edge. Now in an implementation you would find out by checking the characters.

7:43 Now the cool thing is finding the first a uh some match um first here doesn't mean leftmost in the text. there's no guarantee of that sort or returning there's no match that is linear in the length of the pattern if the alphabet is constant because we can just go down the tree character by character if you want all the occurrences that's also possible by walking through the tree and reporting all the leaves as a last thing let's have a look at this uh at this problem we started with in a slight variation This is not exactly the longest common substring but rather the longest repeated substring which means given a single text what's the longest string that we can find twice in the text where it occurs at two positions uh starting at i and at j where these are not the same indeed this is something you could uh use for compression But we haven't covered this. Sorry for the reference. Um, if you don't use suffix trees, it sounds like you have to check all substrings.

9:05 You could say, um, I'm checking all possible substrings. Do they occur more than once? But there's a lot of substrings. It's a quadratic number of substrings in a text. So, that's not going to work. Even if you were to use the suffix tree to check if they occur more than once. That by the way is easy, right? Checking if something occurs more than once is finding it in the suffix tree and looking if there's more than one leaf below it. Uh but there's a lot of substrings. So how do you know which ones to check? Uh this is again something where the suffix tree can provide us the answer.

9:45 Every internal node by definition is labeled with the path from the root to that node is labeled with a string that occurs twice at least because there's at least two leaves below it otherwise it wouldn't be there. It can only be a node if it's more than two children that's split here. So every internal node is precisely a string following from the root to here that occurs at least once at least twice. It could occur many times like uh the a here. And the cool thing is this is an if and only if if any string occurs twice in the text. The suffixes starting at that occurrence share a common path and then split. And so they share a common path and then split means there's an internal node. So precisely checking all the internal nodes or the strings that lead there will find the strings the substrings that occur more than once. And indeed if we're just looking for the longest we don't even have to report all of them just the longest. How do we do that? That's the length of the string from the root. And this happens to be stored in the try. Anyways, this is precisely the numbers that the compact try has to store. Anyways, it's otherwise known um I'll uh skip that in the interest of time. It's otherwise known as the string depth of a node. Uh usually we think of depth in a tree as the number of edges you have to go down. But here the edges somehow have different weights, right?

11:22 Sometimes I'm doing three character jumps or whatever number. Uh and other times it's just a single character. So indeed this node and this node are both deepest in the tree even though this needs three edges and this is a single one.

11:40 And the two strings that are labeled here on the path, Ana and Ban, are the two longest uh repeated substrings in this in this banana band. And you see that there's a quirk with this definition over this data structure in that ANA occurs twice, but is an overlapping occurrence. The suffix tree is happy with that. And if you want to not have that kind of recurrence, it's actually a bit harder. But you can of course find it out by taking the difference between the the leaves. Ban for example here is is a non-over overlapping occurrence.

12:20 So finding these longest repeated substrings you can essentially work out from the suffix tree. Once you have that the string depths of all the nodes you could compute them in a traversal or you could observe that the compact try has to store these numbers anyways. So they're already there and then you just find in another traversal find a node with the largest number. That's easy too. So in in linear time you can solve this longest repeated substring problem.

12:51 And that's very close to this original motivation problem. But let's uh let's start there again uh next time.