Video 6-5: §6.4 Longest common extensions

0:00 Intro

0:03 in the next subsection I want to look at longest common extensions as one application of suffix trees and an additional building block that allows you to solve even more problems based on suffix trees I'll I'll tell you first what these longest common extensions are and then we'll look at one example where that allows you to do a more interesting algorithm than that without them

0:16 Longest Common Extensions

0:32 longest common extensions again have a text as input and then at query time so uh as always for data structure problems I give you the text up front you can do your magic on the text up front and take notes you can build a data structure from it and then later I'll ask you lce queries longest common extension queries which consists of two positions I and J in the text and you have to tell me how many characters can I read from these positions so that what I read is the same string how long can I extend uh the same string from these two positions that's an lce query so formally expressed here it's the maximal L so that uh TI up to t i plus L matches TJ up to TJ plus L and here I and J are given it's quite similar to longest repeated substring in a way but here we're given the two positions so you're asking what's the longest repetition at this particular point right it's a relatively easy thing to do if you don't care about the running time so maybe the trivial solution

1:57 as often is don't do anything at pre-processing time and always compute it from scratch at query time so I call this the store nothing solution probably defer deserves quotes and then how do you solve an lce query well you have two pointers and now you just compare character by character as long as they match

2:40 this is similar to what we did in the naive string matching algorithm so I don't want to spell out some pseudo code for that but it's clear that you walk along this longest common extension and the longest common extension could be long in the worst case imagine worst case stupid one again you would have a text that consists of all A's so no matter where you start you'll always run to the end and so the worst case time of an lce query is is linear and that's that's fairly slow it's uh not very interesting to use the lce query then because you could have just done that on from scratch what we'll find is with some pre-processing on the text you can get much faster all right now the end really here is the L the output which is sometimes useful to know if if you can guarantee that the longest common extensions aren't long then maybe this store nothing approach is good enough

3:48 if we it's just the chapter about suffix trees right so maybe not not a big shock that we can use suffix trees to do that a little smarter if we have the suffix tree of some of this text T the longest common extension between positions I and J say we do lce of one and three is finding the two leaves that correspond to that okay I picked a boring example anyways we can do another one uh

4:22 the longest common extension is is nothing else than the longest common prefix of the suffixes starting at these positions a complicated way to say something simple so here's the text positions I and J and I ask how much can I read at these positions so that this matches another way to say that is I look at the suffix starting at I and the suffix starting at J if I align those

4:56 starts at I goes up to n this starts at J goes up to n then I want these to match so it's the longest common prefix the longest Joint part that these two have in common

5:12 now remember we wrote t i t j for the suffix starting at that position so that's just a different name for the same thing and the longest common prefix of two suffixes that's the

5:31 if we go to these two we notice that they share a path for a while and then they diverge so the part that they share is exactly the path up to this node where the two split and this node is called the lowest common ancestor of the two leaves just in the genealogy tree meaning you walk up from the two until you're for the first time join paths and such a note always exists and it has some label from the root down there that's your longest common extension so in this case lce of 1 3 is the number three because lze asks for the length of that string we can do one more um just to show that sometimes these are boring I can ask for six and four so if I go to these two here's four here's six

6:30 they have nothing in common the longest common answer is to exists but it's the root and so in this case uh lce is zero okay okay I put this down in in short notation and put a box around it because that's something useful to memorize it sounds a bit cryptic but if you keep the picture in mind you can actually read it write it

6:58 so Long's common extension is nothing else than finding lowest common ancestors of leaves in the suffix tree and then you need your string depth which is something used before

7:12 Efficient LCA

7:16 now if we if we do this in the suffix tree we have only pushed the problem one step further we now have to find lowest common ancestors instead of just walking along the tree the string it's not so clear if that's any better

7:33 what we could do is we could walk from the leaves upwards step by step until we find a common path um that's that's possible but it's actually not slow not any faster in the worst case you can create suffix trees that are very deep and and still if you have two leaves that share essentially no common prefix you may have to walk up a linearly long path so that translation to the suffix tree didn't really help us in that case of course there's another trivial solution we could pre-compute everything for lce uh store all the combinations of I and J in a big table that's all right for query time you can just look it up then but the the space of pre-processing time are prohibitive so these two Simple Solutions won't get us any further and here's another black box that will only come back at the very end of this module for now you have to just take it as another magic trick you can pre-process the suffix tree in linear time so essentially again the time you need to read the string or read the tree so that we can find lowest common ancestors in constant time afterwards no matter which two leaves you pick in one step you can jump to the right node

8:55 these are literally copied from what I said about the suffix tree Construction and they build they build up on on a few Nifty tricks it wasn't so clear how to do it before people showed it but now it's something you can teach in a module like this it's not the the most ugly data structure and it's definitely useful in practice it's not hard to implement so this is this will be the topic of unit 9 which I labeled as outside of the exam because it's it's just a little too too much for an introductory course like this for some of you but I wanted to show it because I think many of you will enjoy it it's uh it's a lovely topic it's just a little technical at a few bits so I don't don't feel it's it's useful under the exam but I think it's good to show you a little beyond the textbook level so we'll come back to that that's a promise not a threat uh I will will crack this this Black Box open too but I have to ask for a little more patience in this case right uh for the moment let's close the box and just use this as a result we can find lowest common answers in constant

10:12 time after spending some pre-processing on the suffix tree and it builds on the suffix tree so that will be hidden inside in a way we've already nested two of these black boxes one in the other

10:31 but that's the part for for the moment so given a string you can look at it in linear time and afterwards you can say for any two positions how far can I jump where the characters match

10:50 now if you see this for the first time uh the definition might be a bit overwhelming and slightly weird there's a very not a straightforward application of this where I hope this this makes it clear that this can be a useful primitive and this is for the first time a problem where we look for inapproximate matches so we're back to string matching not necessarily offline although we'll treat it as such you're given a long text and you're a shorter pattern but could still be a few thousand characters and you're trying to find a position where this occurs in the text almost without any mismatches to make this more precise what we mean by that we fix a parameter K that's the number of Errors you allow and then we look at a match where the Hamming distance between the positions in the text and the pattern is below k so I have to tell you what the Hamming distance is and it's just the number of mismatches between two strings so if you have two strings of the same length

12:02 you have maybe many characters that are the same uh and then maybe a few positions where they're not the same so if you have three positions where the characters are not the same distance would be three we just count how many mismatches there are and there's no ambiguity because we assume it's only applicable if the strings have the same length so there's no uh no leeway in choosing what to align to what foreign all right if you take the definition as such you can easily adapt our brood for string matching algorithm back from unit 4. to count the number of mismatches Remember at the time we said okay every position in the text is a guess let's try to find how many characters can I align between the text and the pattern and as soon as I had one mismatch I said ah no match next I'll try the next guest instead I can replace this inner loop with one that just counts how often I have a mismatch and when the number at the end comes out smaller than K I return here's an approximate match with so many mismatches and otherwise I continue so the the time we're comparing this against is this Brute Force string matching time n times m may or may not be good enough but if M

13:29 can be fairly large it might not be good enough and we can definitely do better using our new fancy toy the longest common extension similar to what we did with generalized suffix trees you can apply the same trick for the longest common extensions if you look at a text that consists of well T and P with some markers in between we can build the lce data structure on this text and then if we ask a question what's the longest common extension between this position in t in this position in in p I can get the answer of how much I jump uh and at these positions even though I'm looking at two different strings if you make them part of one big string it's actually just the special case of this longest common extension so I mean to not have a slide where I didn't scribble something on let's put our construction here so that's the text in the pattern and if I if I happen to ask a query where I is here and J is there I can find longest common extensions between the two strings but I'm really just using two positions in a long string that's constructed in that way so all the black boxes from the previous slides can be used

15:02 okay I slightly looked into the box remember that we're building this on a suffix tree but we can use the generalized suffix tree and then lowest common ancestors work in this generalized tree just as if it was a normal one still with me so how would we want to use this to speed up the K mismatch matching problem

15:29 well intuitive idea let's use The Brute Force algorithm but whenever we have something to check we first jump over all equal characters maybe that brings us a lot of positions to the right and we don't have to check oh matters matches matches matches uh meticulously all the time instead we just jump that's pretty much what we'll do

15:51 Clicker Question

15:54 um and that will be called the kangaroo algorithm let's do this to make sure your your with me here not that this is a hard one well either way so Hamming distance is the number of characters that do not match if you just write the two strings on top of each other uh so uh I did that here and okay apart from the handwriting e is the same a is the same R is the same but uh the other two are not

17:57 if the strings are not the same length Hamming distance is not defined doesn't make sense in that case uh there are other other metrics the edit distance is a is a well-known one where you um you say I can take one string and now I can edit it into the other string by replacing a character inserting a character or deleting a character and you say what's the minimal number of such operations that takes me from one to another string that's more General but it's a little trickier to do string matching with that all right let me show the attendance code again for those who came late and we can move on with this one so Hamming distance is two in this case because two characters are not the same goody

18:52 Kangaroo Algorithm for approximate matching

18:56 the algorithm that exploits the lce data structure is called the kangaroo algorithm because of these jumps we always make and it works like this we have one Loop over the positions in the text similar to The Brute Force string matching algorithm then we have a variable that counts how many mismatches we have seen so far and we have a position in the text and in the pattern but now instead of doing single comparisons we first jump over all the equal characters between the current position in the text and the pattern

19:38 if we're currently at position I in the text we imagine we put the pattern below this and then there's a certain number say of characters that are equal and so the first step brings us right behind this so we jump from I to this new position I plus l now if we have jumped L positions from the lce data structure it means we could not jump L plus one positions otherwise it would have done it so without doing another comparison we actually know there's always this mismatch here between the next characters it has to be like that otherwise we would have jumped further so we don't actually have to do this comparison but we know there's a mismatch and we can advance where we are in T and in p by both L plus one

20:40 and so we're looking at the next position and from there again we do a jump how many characters are equal well who knows but maybe a lot and we jump from here to that position and then again have one more mismatch now at some point we run out of pattern at this with this procedure or we run out of mismatch budget if the mismatches go above k then we stop because then we needed too many mismatches for this to count as a match and if we run out of pattern then we return a match at this point and we could have returned the number of mismatches at this but the formulation of the problem asked only for the index easy to change

21:31 how well does this work the pre-processing N plus M that comes from the lce data structure that's linear in the length of the string but we have to take the text and the pattern and the matching part the algorithm above it that is now instead of n times M where M could be in the thousands it's m n times k where you tell the algorithm how many mismatches you still count as okay it's probably a few right if you start getting into several dozen mismatches it's probably no longer recognizable as a match so the assumption is that K is substantially smaller than M otherwise the thing is not very interesting so we get some decent speed up at least in in many situations when when K is not too small not too big all right the algorithm above is is not that hard it uses this nice black box to do these jumps and without that it wouldn't work

22:34 again just for your curiosity people have thought about this problem much more deeply and you can get much faster with more complicated algorithms where you can essentially divide by m so you can do something almost like the good cases of boy or more where I remember if if we were lucky we didn't have to compare all the characters a few characters per guess could have been enough to decide there's not a match and so you can jump further something similar can be done here but not quite as efficient and what I mentioned before edit distance as a generalization when you allow insertions and deletions which is a bit more realistic if if this is searching with typos uh that's possible but it's a bit more tricky so beyond the scope for today

23:28 Matching with wildcards

23:32 as a last application very briefly not too uh not too interesting but can be useful not not interesting from the theoretical side but can be useful we can allow in our pattern to have wild card characters so a don't care character so it's not the Unix shell star where which matches uh any string it's the star in the sense of I don't know a dot in a regular expression this is some where would we use a star there was some you guys remember

24:11 but I mean the definition of star here is any character but a single one yeah so okay that's true okay too much it's also using SQL uh material or any character yeah that's that's my point so it's often used so a python import Star from and so on and SQL but there the star can be any number of characters what I mean here is a single character I just don't care which one I didn't want to use the dot because that's hard to see um so a single character is the important part and so then uh it's pretty much the same as asking for matches with string matching with up to K mismatches where just uh the Wild Card always counts as as a mismatch in that sense so you can you can adapt the algorithm from before to this

25:21 that was the application number six and for now the last one and I want to discuss but just to drive that point home there's a whole range more that for example Dan Grassfield collected in his book in his book which is uh it's a bit of the the suffix Tree Bible if you want as all sorts of things that you may may or not want to know may or may not want to know about suffix trees

25:53 any questions on the suffix tree applications I want to segue into the next part a bit by discussing zooming out a bit from what we've seen discussing what suffix trees are good for I I mean I showed this longest common EXT longest common substring problem several times where I was conjectured not to be possible put him why did you take so long to advance oh why did it take so long to invent suffix trees

26:03 Suffix trees - Discussion

26:41 I think the answer to that is read the old papers about the Suffolk Street Construction uh the lit so the definition of suffix trees is not so hard to come up with but to construct them in linear time is a little tricky and I mean it could have been possible in principle that you could Define this nice data structure it's just not possible to compute it quickly and so it's no use I think that's the that's the reason now in hindsight it's always hard to say uh what was the trickiest bit I'll show you a construction which is the modern word way to do it which is much much cleaner uh so maybe after that you can ask the question again or ask yourself the question again

27:27 so it took a while to get them but then once they're here they're linear time linear space and allowed all sorts of problems to be solved in optimal time but they have some downsides uh some parts that we didn't talk about is how to represent them in detail in memory

27:47 I I didn't show this yet but you will see that there's some overhead to uh doing it with the suffix tree uh gets a bit complicated the last part is something I want to discuss a bit how do you store a try well it's it's a tree so we need some way to represent nodes and then it has children so one obvious way would be every node has an array of child pointers for all the possible alphabet symbols that's all right if you have a handful of alphabet symbols if you have many more think again of the Unicode character set 150 000 or something you don't want every node to have a hundred fifty thousand pointers almost all of which will be null or empty that's not really efficient so another option would be give each little node a small data structure that holds the child pointers for example it could be just a linked list sorted in alphabetic order that's much more space efficient but now if you have one node that has gazillions of children could happen sometimes it's quite slow to navigate so this all what we discussed assumes that you can jump in constant time from a node to its child with a given character that's not possible anymore if you do

29:12 this linked list now you can you can go slightly more sophisticated and do a little binary search tree in each node or you can employ some hashing tricks you can try to work around your way uh around this fact that most notes will have very few children but some nodes may have a lot of children and we want fast navigation but it seems either way you either you at some point have to pay either in time or in space and often in both it's not it's not completely for free you can do a fairly recent fairly decent implementation but you still need a handful of pointers for each node at least and so this uh the number of pointers per note this this constant in the linear in the linear space can be much much bigger than the actual text um if the text barely fits in main memory as for a human genome say that's a bit of a problem