Video 8-5: §8.4 Longest common extensions

0:01 in the next subsection we'll see a few more applications of suffix trees in a way we've just done the warm-up so far the the real um Power of suffix trees uh comes with this additional trick that they make possible uh and that enables a few more applications where again if you see them first it looks like this can't be possible uh in that short in that linear time um uh but this this makes it possible these longest common extensions I'll explain what that is uh in a second so we've already made use of that implicitly without me telling you and without you noticing probably um but you can uh you can formalize the following the following problem on a string the longest common extension problem uh you're given a string now the the deal is that you get this string up front as as in string indexing so you can do pre-processing on this on this text and then later I'll ask you lce queries longest common extension queries which means I'll give you two positions in that text one here one there and you have to tell me how many characters can I read from there to the right that match so how far can I read the same same characters here uh that are

1:28 equal and all I all I want to know is how many characters so not the actual text that's the formal definition here the LC query for I and J is the largest l so that if I read from I and from J for L characters I get the same string and because it's the largest L it means if you take one more character there's a mismatch so the next one would be a different character at the two

2:01 places and you see how this is connected to um uh what we've done before in terms of the longest common prefix of of suffixes indeed it's the very same thing if I if I ask for the longest common extension at two positions I could also say I I ask for the suffixes starting at these two positions and how many characters they have in common so that's that's really just um a different name for the same thing so let me draw my f favorite picture again I can take this this TI and I can take TJ which starts here and align it below uh TI and TJ and then I can ask how many characters here are equal before I get a

2:54 mismatch so these two things are the same just a different name um and uh We've also already seen in the second equation which relates this to the suffix tree namely the longest common prefix of any two um any two suffixes so any two suffixes corresponds to some leaves in the suffix tree and then I can find the lowest common ancestor of those two in the tree and that will give me the string with that node will give me the longest common prefix of those sub fixes so if I take the long lowest common ancestor of those two it's a boring example because they have the root as the first thing where they join paths if you move upwards so their longest common prefix is empty they they differ on the first first character and because this is banana ban the entire thing and this is naban the first character is different we've had the other example before with five and seven where the lowest common ancestor was this node so uh they had a a long longest common prefix of length one okay so you already know what I'm what I'm telling you here uh it's just throwing in another piece of vocabulary in the in the mix uh which is sometimes a bit more bit bit more intuitive because it

4:21 doesn't talk about suffixes um this observation I mean you can you can express this as this for equation I circled it because that's kind of a good one to to memorize just so uh you can quickly recover that fact even if you uh don't remember you would always have to draw an an example and and ReDiscover it otherwise you can also memorize it uh that's why I Circle it again but it's the same

4:55 thing so we defined a problem okay the problem being I give you the text and later I'll ask you lots of these lce queries and you're supposed to tell me very fast how many characters these two these two places share um how can we solve that problem there's different more or less smart Solutions if I have the suffix tree already I could I could use this last part and find the lowest common ancestors so I could walk up from both nodes and keep checking if I um if I found the same node that's one option um unfortunately that's quite slow at least in the worst case um if you imagine you're like in this like for these two leaves you're far away in the tree and you have to essentially walk all the way up to the

5:46 root another option would be you pre-compute all those lowest common ancestors in one big table um but because you have n leaves it would be for every pair of leaves an entry so that's quadratic space and even just write that write that table to memory you need quadratic time so that's too slow on the pre-processing uh there's another um for

6:13 lce if you use the the other version of the problem there's of course another solution that doesn't do any pre-processing but instead at query time you're given these two positions and so you keep walking walking to the right from both until there's a mismatch so

6:41 um you just compute lce naively at each quy time uh that is fast for the pre-processing because you do nothing but at query time you essentially have cost as much as the answer is so if L is your answer you would have cost of L but in the worst case um that indeed is again uh linear so it kind of gets you in the same same ballpark as here so both both seems uh it's not so great um now without a further trick you don't really get further but there are there is a another trick you can you can play um there's a way to compute for any Leaf any two leaves in the suffix tree their lowest common ancestor in constant time after spending some pre-processing but not this super slow quadratic time again linear time is enough so in a way you can compute the suffix Tree in linear time and you can do this pre-processing for lowest common ancestors also in linear time and then you can jump from any two leaves in one step in constant time at least to the lowest common answer Anor and if you do that you can use the translation that LCA was the same as LCP was the same as lce uh to compute lowest uh longest

8:13 common extensions in constant time that's this box down here so for the rest of this section we'll we'll use this as a black box now uh this black box will also crack open that will be the Christmas lecture so I I wanted to show you what is what is inside that blackbox uh but I felt it's pushing a bit too far for exam material so that will be kind of just for your enjoyment um but that's Unit

8:51 Nine so uh for now that's also a promise it'll be the last black box I think that that I'll throw at you for the moment let's just take it as as as given and see what we can do with this and the first application that uses this is uh something where we um where we want to find approximate matches so far whenever we talked about spring matching we were one we were interested in finding exact occurrences of the pattern in the text uh and um there's many applications where it's desirable to allow little typos and so on or a bit of noise and the simplest version of that problem is is the K mismatch matching problem so similar to string matching you're given a text and a pattern but you're also given a bound on how many characters you're allowed to mess up and still call it a match so formally we say A match is uh some position of the text of the same length as the pattern where the Hamming distance between that portion of the text and the pattern is at most k so at most K characters are in mismatch uh you've you've heard about Hamming distance when we talked about Hamming codes uh in in unit six in detail so here uh it's just a reference

10:13 back to that um but really it's it's K match K characters don't match okay first what are the Simple Solutions you can take our good old brute force method for string matching and adapted to this uh the reason is the brute force method to took every possible position in the text and said let's let's see if I start here can I find the pattern there and I have this inner loop that just Compares all the characters now in this inner loop instead of comparing the characters and stopping as soon as you find any mismatch you can keep going and count the number of mismatches in the same time so the same time as BR Force um string matching you can also do this problem and determine all the matches where there's at most K

11:09 mismatches uh but if if both your texts and the pattern are fairly long um that's not so great um and we can do better so we do a pre-processing on uh something like the uh EXT like the generalized suffix tree again we take the text append some end of word marker and then the pattern and a fresh end of word marker and we use this um this lce data structure that I've uh just told you about as a blackbox so we can find longest common extensions in this in this string in constant time and that in particular means if I have my text and then the pattern afterwards I can pick a position in the text and I can pick a position in the pattern and in constant time it tells me how many many characters are aligned or how many characters are the same here okay that's what we'll use um and for that essentially what you need is the generalized suffix tree and all the string deps and the constant time lowest common ancestor LCA data structure uh but we'll we'll just work with lce for now so any two positions you're given you can find in constant time how many characters are the same

12:34 and with that you can um so you can use this this simple algorithm that got called the kangaroo algorithm because it always does jumps um so how does it work you have your you have your text and your pattern it has aspects of this of the naive string matching algorithm The Brute Force algorithm in that it goes through all positions in the text where the pattern could occur so all guesses so then we have a portion of the text but now we're trying to speed up the matching to see whether or not there's a at most K mismatches so we count the number of mismatches we have a position in the text and in the pattern and as long as we haven't exceeded our budget of mismatches we compute how many characters from this position in the text and the pattern match in one go so starting from here let me make the pattern a bit longer so that my kangaroo has more room to

13:43 jump so we start at this position and now we ask how far can we jump where what I jump over is characters that are equal and that's the longest common extension of these two positions it's the longest piece I can read from there to the right where all the characters are are equal necessarily one place after that will be a mismatch otherwise we would have jumped further so after finding jumping over these L characters I go one more ahead so I I move forward by L plus one so I'm now standing right behind this mismatch and I count I've made one mistake so far then I jump again using another lce until I find another mismatch and then um I'm standing right behind that uh by doing this I can do at most K steps and no matter how long the pattern is After Time proportional to K I know whether I found the end of the pattern so I I could match the entire pattern with the most K errors or not because uh I'm still in the middle of the pattern I ran out of mismatch budget so the algorithm is fairly simple the only uh tricky bit is in the implementation of lce the black box for

15:21 Christmas so the overall time instead of uh the brute force method was n * m we now brought this down to n * K and K is a parameter that you give uh as a as a user and usually K will be small I mean if you're if you're trying to find a match because uh someone is is searching something and they might make some typos but if they've typed 20 characters wrong then this uh probably not a useful match anymore but probably K is is two or three or so so this is essentially close to to linear again uh whereas this if the pattern is long might be substantially bigger and we need this pre-processing but that's n plus M that's essentially again theine near time so for small K this is a substantial Improvement um and it's also a practical algorithm now again uh I often have these kind of extra sections state-ofthe-art maybe I should at some point generally say whenever it says state-ofthe-art you can ignore it um that doesn't sound like a very very helpful statement but you don't need to know it for the exam uh people pushed this further so just in case you were wondering if that's best possible it's not you can uh play further algorithmic tricks but I don't want to

16:40 get into those all right so that's um that's an application that doesn't even use suffix trees explicitly they're only occurring inside this lce query hidden from you in that sense um the algorithm around it is fair really simple but it gets the running time down

17:06 substantially and uh a last application is related to that if you're trying to find patterns and you have a don't care character so wild card in this case it's not it's not like the star in the Unix shell where it can stand for an arbitrarily long string it's a single character but you don't care which one uh you can do essentially the same as this kangaro algorithm slight Twist on that solves that version of the problem and um if you're still still curious about more I brought this book here as well that's on the slides uh it's kind of the the suffix Tree Bible there's a lot of more applications of suffix trees where if you try to solve it from first principles without using existing data structures it seems it's a very it's very hard to solve efficiently and with um with suffix trees potentially using this trick for lowest common ancestors uh it's a relatively simple task to solve them so the the suffix Tree in that sense really is this this threshold invention that made a lot of other things very simple conceptually um and and has lots of applications uh whenever you whenever you have these kind of strings and the book focuses on on biological sequences

18:39 so to wrap up suffix trees um are great from a theoretical perspective they're linear time and space you can construct them in time proportional to the length of the text they use up space proportional to the length of the text and made all these uh problem solvable as I just said uh from a practical perspective there's still a few things that are um that are kind of leaving wishes open uh the original algorithms for constructing suffix trees while there were linear time um in in theory there were still relatively slow uh and also complicated to implement and to explain uh and the suffix tree itself because it it's this tree with potentially many children and so on it's a little less obvious how to represent it space efficiently think about it that way we always assume in this section that the alphabet is finite and not not crazy big but it might be all asky characters at least 26 or maybe uh well all all Latin characters or all asy characters 128 or 226 so it's in the dozens or hundreds now you have two options how to represent a node you can represent a node uh with an array of child

20:14 pointers so it could be something like this then every node needs space Sigma if Sigma is constant that's linear space but still it's a a factor of a dozen or 100 overhead uh the other option would be

20:32 some other data structure within each little node that tells you what uh what child pointers exist so you could have for example a little binary search tree over the labels and then uh it's it's a little dictionary in each note that maps from The Edge label to the child to the child pointer but then you have a a log Sigma space overhead for each traversal because that's the binary search tree so here you have a sigma space

21:15 overhead here you have a a log Sigma time overhead H it's just not clear I mean both is may be fine but uh if Sigma is not tiny it's both both are not negligible and even this version still has a lot of pointers so it's uh it's in a way as great as is from a theoretical perspective but if you implement it it's still not as good as it as one would hope