Video 6-5: §6.4 Longest common extensions

0:00 <Untitled Chapter 1>

0:01 in this section we'll look at longest common extensions a data structure problem that at first sight doesn't really tie into suffix trees much but we'll see right after that suffix trees are the key to solving this problem efficiently so let's um let's have a look at this at the definition what this problem is about and i'll point out that again as we've just seen in generalized suffix trees in the previous section where we try to find the longest common substring of a set of texts suffix trees are good for identifying longest common prefixes of suffixes

0:16 Longest Common Extensions

0:40 so the longest common extension problem nothing to do with suffix trees for starters we're just given a text and you can look at the text you can pre-process the text and afterwards i'll ask you queries of the form here's two positions i and j maybe a picture again here's your text i can ask for position i and j what is the longest uh the longest was the largest amount of characters you can read from both positions to the right and you see the same substring so you read to the right there's a certain part that occurs at both positions

1:26 and so in form in formulas that's what's written down here the longest common extension is the length of this green part so it's the biggest l so that if you read the substring starting at i respectively at j you get the same string and this maximum here just means we want to capture the longest such l which means the next character differs necessarily

1:52 again it's useful that we terminate our text with this dollar symbol so we never run out of out of bounds in in this definition so it's always well defined

2:06 now we will see in a second uh how we can how we can implement this data structure will be so this is if you like this again i shouldn't say data structure this is an abstract data type it's just telling you what the operations are so

2:27 maybe fix the slides here remember from unit 2 back then a data structure tells you specifically how to do things whereas this is really just telling you what to do so it's an abstract data type in that sense and we'll see different implementations of this abstract data type on the next slide a key idea is that the suffix tree somehow seems well suited to support this

2:54 simply because longest common extensions are just a re naming of a concept we've used before so let's unwrap this a little bit if we want the longest common extension of two positions i and j we can also look at the suffixes that started those positions and look at their longest common prefix so that's just a different name i'm introducing this his abbreviation lcp already here because it will it will pop up later again and will be another big another big player in a sense so these two things are the same things they're just named differently but they're really by definition the same and also if you have two suffixes then in the suffix tree there's two leafs that correspond to these starting indices i and j and now something that might not be completely obvious at first sight is if you find the lowest common ancestor that tells you what the longest common prefix is so let's do an example in our tree here

4:13 if we want the longest common prefix of t5 and t1 we find the leaves for five and one and now lowest common ancestor just means you walk up the tree to the root from both and these paths at some point join for the first time so that's this node in this case that's the lca of leaf 5 and 1.

4:46 and so where what the rest of the statement says if you look at the string depth the length of the path from the root to this lowest common ancestor that's the same as the longest common prefix why well these are two suffixes in a suffix tree so if you read the path from the root to the leaf you get the suffix back and they share this first part so whatever you read on this shared path down to the lowest common ancestor has to be the same and also at the next position they differ otherwise they would continue on the same path okay so at first sight this looks a little magic and maybe confusing all these acronyms with ls if you unwrap it on an example it's really nothing nothing deep it's just an observation taken from how suffix trees are defined

5:39 okay so here's that statement in short again and i put a box around it because we'll revisit this uh a few units down the road but i think i have a copy of the slide in the deck there so that's just for you to summarize um i guess more more useful is to remember the picture and the example on the picture and then you can reconstruct the equation form from there

6:14 Efficient LCA

6:19 we've seen how we can use suffix trees to find these longest common extensions using the fact that the lowest common ancestor gives you those but that's not the same as having an implementation for this lce problem if we have the suffix tree what we could do is just walk up uh from the two leaves until they meet for the first time but that could take a long time if these are long suffixes and they don't share a lot of a lot of characters at the beginning you might have to walk up the tree a long while we could also just pre-compute everything it's kind of boring also takes lots of space we don't like that and it takes if you need that much space it also takes that much time to fill the table in pre-processing so that's not great either we could also this the trivial solution that i didn't even dare to list

7:25 that's an e we could do no pre-processing at all and just when someone tells you find me the longest common extension of inj you start walking from inj until they differ you could do that but that's slow at query time so

7:52 or more precise you could say l where l is the length of this the shared prefix so if you don't expect long shared prefixes maybe this is not not such a crappy solution but in general it's not really interesting and also it doesn't it doesn't use suffix trees so we can't be content with that

8:15 now for the time being i'll just throw in another magic black box and tell you it is possible to do this to solve this um well to compute lcas in this case i've rephrased it in terms of the suffix tree you can take a you can take a suffix tree and pre-process it spend linear time in space and afterwards you can find for any two leaves their lowest common ancestor in constant time you jump there in worst case no walking nothing okay uh i just copied these bullet points from the suffix tree it's the same statement it is a little tricky to understand how this works but again it is uh we'll completely unwrap this towards the end and it was a breakthrough when this first was was observed but if you follow the steps in the right way each each little step is quite elementary and easy to follow it's just combining them all together in the right way took people quite a while

9:21 and this will be part of of the um the most practical and uh useful implementation of suffix trees so uh it will okay this will not make sense to you at this point it is useful in practice let me just promise this at this stage so for now we'll just treat this as a black box if i give you a text you can call a magic function and that in linear time produces you some some data structure that in constant time can answer these lca queries lce queries on the string okay so here's the statement for lce here's the statement for lca remember the two in suffix trees are essentially the same i put the the material puppets here because we're we're starting to use a black box inside a black box so that's the point where you should get a little uncomfortable if someone promises you that this is practical but you haven't seen the black box that's now used inside another black box but i'll i'll get you there eventually and we'll unwrap the first box soon all right i hope you kind of appreciate that this is a cool result and if you just mess around with simple ideas it seems you can't get this linear pre-processing time and constant query time for lce

10:50 same pattern as before before we further bother to construct these things let's see what we can do with this new toy and there's there's a lot of different things but i picked out a few easy to digest examples that are still somewhat cute i think the first is let's depart from the unit 4 definition of string matching and instead find inexact matches of a pattern in another way to put it you're trying to find something in a book but you type slightly mistyped the word you're searching maybe you want to allow one or two typos and still find the occurrences

11:35 so formally we're still given a text and still given a pattern but there's an additional input parameter a number k and i think usually of k being really small like one or two or three that's the number of typos you tolerate uh and what does tolerate here formally mean in the simplest version that we'll look at we want to find occurrences in the text so substrings of the text that differ in at most k characters from the pattern and differ here just means you can replace up to k characters no deletions or insertions so if you if you type in a haste and google for something you often omit a character or mistakenly type another one that doesn't belong there you can handle these things too but we'll keep things simple for now so just mismatches all right that's something you might have seen elsewhere it's called the hamming distance between two strings just the number of positions where they differ and again another thing that will pop up later so i'll throw in this this name already of course there's the possibility that the text does not occur any position that is within hamming distance k of the pattern so then you just return no match so it's something like searching with typos in a very simple form

13:04 let's take a a quick look at what you can do without any fancy things if you think back to beginning of unit 4 our brute force algorithm for string matching remember it just tested one text position after each other after the other and for each text position it tried to match the pattern at this point now we can adapt this to that

13:31 scenario where we don't find exact matches if we align the pattern at certain at a certain position with the text we can just ask how many characters are equal and if there's a mismatch then we count

13:52 and whenever we found a position where there's fewer than k mismatches we report this as as a match okay i didn't prepare code for this but i think it's it's conceptually quite simple to do you could literally take the the code from unit 4 and just include a counter instead of skipping out of the loop right away so what we're comparing with is this baseline of of the brute force string matching if m is really small that might be good enough but if m is is not so tiny this is relatively costly and remember for

14:51 this time order n plus m and we were even able to figure out some parallel ways and all these things so this is much worse it seems now how does this fit into the section on longest common extensions well let's look at this string where we have the text and the pattern again we applied the same idea as for the generalized suffix trees just take the strings put them concatenate them and throw in some some dollar symbols that served us well before let's just try the same again and pre-process this string for the longest common extension queries so we can we can do this by building the generalized suffix tree computing the string depth and then pre-processing that tree for lcas but that's unwrapping the first layer of the black box you might ignore that part if you want so we'll we'll try to use lces in in this one and before we do that let's see if you paid attention and also wake you up again just a quick one

16:38 you know what to do it's a simple exercise it's mainly testing if you remember the definition the number of emoji has skyrocketed compared to last year it's definitely times are changing there's more smiles in the world again it's good to see all right uh i'll i'll just show the results uh you can still put your vote in but most people uh came down to two or something close thanks guys yep i guess i provoked that one so why is it two uh well you count okay let me do this on the slides [Music]

17:42 you keep going you can see it on your phones so if you if you write the two words below each other heart beard then there's uh three matches in the middle but mismatches here so hamming distance two all right

18:11 Clicker Question

18:16 Application 5: Approximate matching

18:18 how can we make use of this before i show you the code so we have this this magic toy that tells us in this string or any two positions how far they continue the same way in the text how can we make use of that

18:41 if we have a position in the text and we have aligned the pattern we can take this i position i and this position j in the text initially zero and we can map this to this this weird text here where we have t first then one dollar then the pattern

19:05 and well the position i the text is still at position i and this position j is at i plus one plus j in this big text so we can put an lcd query for these two positions and we'll tell you in constant time how much you can jump from these two positions and also where the first mismatch is because it has to come right after

19:33 so instead of walking over the green part and having to check all these characters we can just jump over them then we have one one character the red one where there is a mismatch so we will have to deal with that but then we move over it and jump again and the trick is we only have to do this k times because after k red mismatches we know it's not a match position

20:00 Kangaroo Algorithm for approximate matching

20:01 and because of this jumping people have called this the kangaroo algorithm so this just is code spelling out the idea i just explained we built the lce data structure for this combined text again using the black box inside the black box and so we'll come back to that eventually and then we follow the brute force algorithm but we do jumps so we test each position in the text

20:29 another time i picture reach position in the text where we could align the pattern we count how many mismatches we've already used up and we keep track of the position inside the pattern and as long as we have budget for more mismatches and we haven't reached the end of the pattern we do another jump and the jump is given by this so you'll have to uh decode the formula for the two positions but i hope i didn't make it didn't make a mistake so you jump over the matching part

21:13 and then there's one mismatch position that you count and then after that you jump again and well you always increment these by one to jump over the mismatch character if after this loop you found the end of the pattern that means you didn't run out of mismatched budget before you reach the end so then you have found a match with up to k mistakes then you return this one okay it's a quite simple algorithm apart from this from this line uh how good is this the pre-processing will be linear in the in the size of this text that we generate and that's the text plus the pattern so that's length n plus m and the preprocessing will be linear in that length uh that's the part you haven't seen and then the matching part is this loop this outer loop runs n times and minus m but don't get too catholic about it and this inner loop runs at most k times so we gone down we've gone down from n times m to n times k so this is useful if k is is much much smaller than n

22:31 informally written as as much less than m uh not very useful but shorter than writing it out so it depends how useful this is uh unfortunately people have proven that you can't do much much better it just seems that these these problems where you try to find inexact matches they're substantially harder than the exact matches and there are lower bounds that you cannot get around easily people improve this to more complicated runtimes with much more complicated algorithms um this is like just for your for your curiosity this is not the end of the story um but it uh yeah in this in this model this is not so easy ways to improve this further

23:26 but you should think of k as being relatively small anyways if you allow many mismatches you'll find lots of spurious matches in your text so the useful realm is when k is a small constant and then this is a really fast algorithm and a huge improvement over the n times m

23:47 as the last application for now [Music] it's a slight twist on essentially the same problem we now uh allow a wildcard character in our pattern so so instead of saying i have a fixed pattern and i want to find inexact matches i'm now saying i tell you exactly which positions in my pattern i don't care what character is there

24:11 so this is a wild card in the sense that it can be replaced by any single character it's not a unix shell style wild card where it can be an arbitrary long string so an example here the pattern is is unit and then star which could be replaced by unit 5 but it couldn't be replaced by unit 10. it's just a single character

24:38 and if you if you think about that this is even a slightly easier problem than the one we've just solved so the kangaroo algorithm also works for this one

25:13 using lces in in that sense for this specific problem you can traverse the generalized pattern down the suffix tree if you have a character you just go down a path that's as before for exact matching and if you have a wild card you follow all the child links so this immediately explodes if you have many wild cards

25:40 but if you have few wild cards it's actually okay so you would follow sigma to the k paths in the tree when you have k wild cards so if you just have a few one or two or three that might be a fine so the sigma to the k comes from you traverse the path now there's a wild card which means you don't know what the next character is it can be anything so you have to follow all the possible child links and at most there's sigma because that's the size of our alphabet but then you have sigma paths to further go down so you have to go traverse with all those down and if there's another wild card each of them expands another times into sigma sub paths so this this won't work well if k is is reasonably big but for very small k this could be good and the benefit is that if you have built the suffix tree you can do this and uh search search the pattern

27:03 that's the number of paths we have to walk down each path is at most m characters long so that's how many notes you have to visit till you found all the potential positions and then as before there's the question do you want all matches then you would have to go to all the leaves below all those paths or you just want one then you jump to the left most

27:36 so in this case you can do this inexact matching without having a dependence on the text length that's the important part i want to point out sigma to the k depends only on the pattern the text can be as long as it wants as long as you want the sigma to the k times m doesn't depend on the text size so this algorithm is in the sense of unit four we do some preprocessing of the text but it is uh we still um do this on the fly so we're given the text the pattern then we do the matching whereas this solution is closer to the text indexing flavor you give the text pre-processing it once and then you get several patterns over time

28:21 you can think about whether this kind of solution can also work for the previous problem where we didn't know where the k mismatches are and the answer is yes but it gets even more expensive so if k is really really small you can still reasonably do it and yeah let me leave it with that um there was one thing i didn't point out um that was this one again this is we don't we don't dive into any details but if you're worried that this k mismatches is not very realistic i hinted at this earlier you if you type then for that application you often have insertions and deletions of characters there's a generalized notion called edit distance which is given two strings what's the minimal number of operations to go from one string to the other and the operations are replace a character delete a character insert a character and you can generalize these two algorithms for edit distance k as opposed to hamming distance k but they get a little more tricky and so i'll skip that here

29:31 Application 6: Matching with wildcards

29:34 and so yeah what i what i said about this part is also true for hamming distance but then it gets even hairier and slower but it seems that with these inexact matches that's to some degree inevitable

29:55 if you like this kind of stuff there's a book that has many more applications i mentioned this before that was the the book i quoted for this uh statement of don knuth this conjecture uh the bible on suffix trees if you want but there's a there's more modern sources as well linked on the website

30:15 Suffix trees - Discussion

30:20 so let me wrap up this part on suffix trees uh it's quite clear at least in hindsight that this was a threshold invention it allowed to do things that seemed impossible before even by experts and once it was there it made lots of things relatively easy it put research level problems into the realm of like exercises for a module like this

30:47 just to wrap up why is this great suffix trees use linear time and space to construct them and to keep them around and allow to solve all sorts of problems so they seem somewhat magic but then once people got used to this in theory they noticed they're not so great in practice as presented up to now they're quite fat if you want their linear time to construct but the algorithms that directly construct the suffix tree are quite involved and have quite some overhead

31:27 and once you have this tree you have to represent it somehow in memory and there's different options i mentioned this before you could for each node have all child links all sigma possible child links that uses sigma pointers for each node so

31:48 um n times sigma if we use an array of pointers and remember sigma it could be ascii then it's just 128 or 256 it could be unicode then it's 100k times the length of the text that's not so great uh you could bring it down a bit to something like n log sigma if we use dictionaries

32:37 we can't in constant time go from one note to its children because we have to use the dictionary lookup to get there so it seems there's no perfect solution and people played with this quite a while and there's some nice trade-offs but no one was perfectly happy