Video 8-3: §8.3 Applications of suffix trees: string matching

0:02 in the next section I want to show you some applications of suffix trees I'll show you more applications in the section after this so I split it up a bit uh this one's showing the direct versions where we just used the suffix Tree in isolation um I just want to show you how many things they make easy recall we store suffix tree like this the notion the the the standard way to store a compact try but for the algorithms we'll think about them as this where we have the full labels and when it's convenient I'll replace the indices and the leaves with the full

0:49 string to um keep notation short I'll I'll sometimes write TI to mean the suffix starting at position I or at index I okay so that keep keep that in mind um if it occurs on the slides and that always includes the dollar symbol so we usually say t0n for the input but now I'll I'll usually have t0 n with so this is a round bracket and this square bracket right this position at index n includes the dollar

1:25 symbol okay very interactive um let's see if we have if we have time to do those um the first thing we'll do is is try to find uh patterns with the suffix

1:49 tree and uh if you have this small example maybe I'll go back in a second uh to show it in bigger what can you tell about occurrences of this pattern A and A uh what does the tree tree tell you and it's the same same tree so here it is in slightly

3:51 let's try to get to the 60 again I don't think it's uh it's useful to rush that ah now it jumped to 60 perfect timing so uh I'll I'll leave it for you to check um there's a a bunch of things I'll I'll just want to show you on on the example here

5:22 so uh let's let's do it here so if you um if you have this this pattern a and a any anything in the try should search from the root downwards so we start at the root and we find a n a so here we have the the pattern red so after traversing with a and a we're stuck at this internal node fine so what what does that mean it means um there's a whole subtree namely whatever comes below this this node where everything in that sub sub tree any Leaf in that sub tree has a path from the root downwards that starts with a and a right otherwise it wouldn't be in that subtree and that means all the suffixes that have leaves in that subtree they start with a Ana and if a suffix starts with AA that means that's an occurrence of a Ana in the text and specifically the indices of these two leaves are exactly the positions where AA occurs in the text and if you check there's a Ana here and there is an overlapping occurrence a and a here and that works out to starting index one and three uh remember we start at zero uh that's why you can conclude this by the fact that you didn't fall out of

6:54 the tree you could Traverse with a Anda down the tree and nothing was ever uh blocked you always could follow an edge um and the rest follows from studying the sub tree that you find

7:12 there so let's do this a bit more uh systematically if we look at our um string matching problem from unit four in the formal sense we have a pattern and we we ask whether it occurs in the text and the pattern occurs in the text if and only if the pattern is a prefix of some sub of T and actually we can make this stronger the pattern occurs at a specific position if it's a prefix of the suffix starting at that position and because the suffix tree at least implicitly stores all the suffixes of the text we can make use of that correspondence and that's what we've seen in the example already uh formulating that as a as a proper algorithm would give you something like this which try to follow down from the route following a path reading the pattern and then several things can happen um so we we follow down until we can no longer do this and we can no longer do this for one of three reasons we either get stuck so um there's a a place where we would like to uh continue reading the next character but there's no Edge that um that allows to do that uh that would be the case if we search um NN for for

8:40 example so we start reading we find one n but then here there's no no Edge for n so we fall out of the tree or we're stuck in that node and that means the pattern NN does not occur in this text and that's true banana band doesn't have double n the other option is uh we reread and we run out of pattern that's what happened in the example with

9:08 Anna so we went down here and so the pattern was finished when we read but we could have gone on in the tree that's the case where we have occurrences as I discussed in detail just uh before and the third case is we run out of trees so we keep reading the pattern and we reach a leave that actually can't happen the way um I draw the tree here because the pattern shouldn't contain the end of string symbol and uh before reaching a leaf there will always be a dollar symbol but remember that we actually store this tree as a compact try so you might actually have that case because you jumped over a dollar symbol uh and in that case you would have to uh do the comparison with the with the leaf but you will always find that uh you're in actually in one of the two other cases if you look

10:07 closely so what this means is if we're given the suffix tree of a text we can find the occurrences of a pattern so find um whether it occurs or return no match in time linear in the

10:21 pattern and that depend not at all in the length of the text the text could be the entire web or the entire Wikipedia the search time only depends on the length of the your of your search query that's the the big uh the big benefit here now there's one subtlety that I gloss over so far we don't usually want in string matching just to know yes there is An Occurrence so you search Wikipedia for some some article suffix tree and it says yep I know something about suffix tree uh that's not what you want you want to see the article where you want to know where it occurs the the search string and for that there's something else that we do in our suffix trees namely we assume that every internal node has a pointer to the leftmost leaf in its sub tree so um in this case here every internal node has a

11:26 pointer that points to one of those leaves and allows you to jump to one leaf in constant time that's just one more extra pointer it uh it increases the space by a constant Factor but it's still linear in the in the length of the

11:48 text and so uh when we come back to this case here when we're here when we read a n a there's a pointer that we can follow in constant time to find the first m or some some match we have to be careful if we put it what what does leftmost mean I took it as meaning the leftmost in the drawing of the tree uh you could also try to make make it point to the one with the smallest uh index but at least in constant time you can find a match and uh in in more time you can find all the matches but that needs potentially as much time as there are matches so um

12:59 in if you want to find a single match you can do it in time length of the pattern by following this one dash green pointer I know in this example it's a bit silly it's just one hop down anyways but it could have been a huge tree you can find all of the all of the occurrences by exhaustively exploring the entire subtree that actually has time linear in the number of occurrences so it's usually also not not not

13:30 slow and so we can solve our string matching problem now much much faster than anything we've seen in unit 4 the only thing is that we have to spend linear time pre-processing on the text before we can get