Video 6-9: §6.8 LCP arrays

0:00 Intro

0:05 in this next section I want to show how the LCP array that I'll Define brings back more flexibility from what the suffix tree could do to the suffix array world and those two together will basically be able to replace what we had done before in the suffix tree so that's maybe a little less obvious so to motivate that let's see what you remember from this long list of applications of suffix suffix trees

0:23 Clicker Question

0:40 and specifically the the one algorithmic problem I used to motivate back then to study suffix trees in the first place this longest repeated substring or longest common substring remember they are quite closely related the longest repeated substring is the cleanest technically so what did we use that especially our um yeah what all what are all the features that we used

1:31 I think I set it up it's there's really just one answer that's the the key thing so uh if you just want to know the length of the longest repeated substring you only really need one thing from the suffix tree

2:10 should have included an option I don't remember anything at all uh but uh in case of doubt maybe you just have to guess one for this one I think he'd already Click by the time this makes it through the network 25 yeah as I guess and you still can't see uh ah no it's coming

2:58 oh I can show you the right answer here as well so uh what I had in mind is the string depth of the internal nodes and just to remind you um if we are trying to find the the longest repeated substring of a given text of a string we can build the suffix tree compute the string depths of all the nodes and then the path to that node is this longest repeated string but the length of it is just the string depth so in this case we had this one at depth three right but there was another one no this one which is also at um

3:05 String depths of internal nodes

3:45 right how are we supposed to do this with the suffix array all we have is is this uh sequence of leaves so if we just have the suffix array seems not really possible it doesn't contain the relevant information we can do it by storing the relevant information on top of the suffix array and that will be the LCP array LCP stands for longest common prefix and it will be the longest common prefix of two neighboring leaves in the suffix tree or two neighboring entries in the suffix array uh so I want to point out here that we usually Define the LCP array other than our other arrays it starts at one because it talks about the difference between two and so there's there's some offset in one way um I have a bigger example in the next slide but maybe let me just illustrate this so if I if I take the suffix array of this string I should just follow the leaves left to right right that's the

5:02 that's what we get nine five seven three one six zero eight four two and between any two adjacent ones I can Define this this LCP array so it would really want to sit here with a number between every pair so something like this but of course we don't Define our arrays with an offset of 0.5 so store it as an array this is 0 1 2 3 and so on in the suffix array and for the LCP array we start with one so the longest common prefix is between R and R minus 1. um but we use the leaves in sorted order so it's uh

6:01 the entry at one if we do this here as a concrete example so LCP of one is the longest common prefix of two two suffixes namely the one starting at L of r L of R is one so that's the text starting at five and of L of R minus one that's zero so it's l of zero which is nine

6:34 okay so if I if I map that to the tree so I would look at this and this and I would ask what's the longest common prefix between you two guys and remember the longest common prefix is the is the string depth of the lowest common ancestor there was a thing with a box around it at the time last time I said rememberize this if you did then you may may recollect it now so in this case it should be zero they don't share any common prefix one starts well I guess T9 is just a dollar right so it will always get zero okay maybe one more less boring example between say five and three so this entry LCP of three

7:36 if I go up to this one I should have a string depth of two so LCP would be 2 in this case okay now if I have the LCP array the longest common prefix is actually trivial to find let me fill the array just so that we have this and it's relatively easy you just follow the traversal of the tree one and six is zero six and zero is three zero eight they go via the root so that's 0 8 4 now step one those this node at step two else finding the longest repeated the length of the longest repeated substring is just the maximum entry in the LCP array so 3 in this case

8:26 LCP array and internal nodes

8:32 there's more so I motivated it from this longest repeated substring but it did a lot more about the suffix tree is encoded by suffix array plus LCP and again mostly on an example but I think that makes it clear here's the suffix array here are the suffixes in sorted order what the LCP array is about is the longest common prefix of adjacent suffixes in sorted order and so you see here these share an A but then they differ on the next position these share a n then they differ and so on and so forth and where where there's nothing they don't share any common prefix as on the last slide just vertically now the LCP array should be thought of sitting between the entries of the suffix array and so the numbers here are just the lengths of these red strings

9:33 and now I can do something called LCP intervals which which is tracing uh pairs well tracing ranges where this common prefix starts again with a common prefix uh let me make it clear on an example the entire range is spanned by the Epsilon LCP interval everyone starts with the empty string so all the common all the suffix or all the suffixes start with the empty string as a degenerate case then there's a range of suffixes that start with an a namely these four and their longest common prefix between this and this this and this this and this they all start with an a so we have this range of length 3 here that covers from here to here all the strings they all start with an A and there is a similar range for things starting with a B and starting with an n now within the range of all the things that start with an a there's another range namely this one of all the things that start with a N and then something else all right and similar for the other things now if you remember the suffix tree for this example because I've shown you probably 500 times you may recognize this there is a one-to-one mapping between the internal nodes of the suffix tree

11:09 and these intervals in in this longest common prefix space so the root corresponds to the all embracing interval everything starts with nothing there's a node here that corresponds to this interval with A's containing everything in its subtree that starts with an A and so on and so forth the connection to just the LCP array is a bit more subtle but uh in the numbers you can see any contiguous range that has at least a one so in this range the LCP values are always at least one they never drop below one in the entire range they never drop below zero well by definition in this range they never drop below 2. so the ranges are defined by ranges where the value doesn't go below a certain value in the LCP array and that corresponds one to one to the nodes of the suffix array suffix tree

12:30 we won't dig much deeper onto this uh I will leave it with this example and the intuition behind it but I hope that it's it's maybe enough for you to believe that with enough algorithmic Ingenuity if you just have the leaf array and this LCP array you can get the rest of this picture the information is all there it's maybe not quite the most convenient form definitely not for humans but it's all there so these two are enough to reconstruct the suffix tree and in fact they're enough to simulate everything you can do on the suffix street directly on these arrays

13:12 the last bit I want to talk about is how to compute this LCP array because that's another uh another really cute algorithm and has one more a nice application of amortized analysis

13:32 I want to point out I will have a tutorial question where you you're asked to do this reconstruction and so maybe you can can gain a bit more insight into that just from doing it on another example the the key thing about the LCP ranges is its contiguous range is where the the LCP value doesn't drop below a certain threshold

13:58 and so the string depth of the node is that threshold in the last section of this unit I want to talk briefly about how to compute the LCP array again efficiently is our Focus so linear time is the goal

14:20 LCP array construction

14:23 let's first look at what you can do naively you could just compute each entry from scratch by it's a longest common prefix so you take your two starting indices of the suffixes and just compare how many characters are equal again uh as almost always some text with just all A's will have lots of lots of common prefixes so you always spend linear time in the in the worst case and quadratic overall so that's not good enough however it might be good enough if your text has almost no self-similarity

15:02 the insight to get faster than that is if we see one large LCP value where we had to spend a lot of time comparing we will always see more large values that use the same common prefix so we can somehow reuse that that work before uh before defining this more more concretely let me show you one of my favorite English examples uh sent the valid grammatical sentence buffalo buffalo buffalo buffalo you can go much longer than this uh 789 buffaloes in a row I think you can still parse that as a proper sentence with contact classes and so on the trick is there is a City Buffalo there's the animal buffalo there's the verb to Buffalo someone is to bully someone so you can in this case construct a sentence out of a single word I chose it because it has lots of self-repetition and self-similarity if you start doing uh if you start by Computing the suffixes of this text in sorted order and start Computing some LCP values you can find really long LCP longest common prefixes and large LCP values because the the text has a lot of overlap

16:19 now if you if you have these two suffixes there will be two other suffixes where these first characters are deleted and these are written here so they will also have a really long longest common prefix because they share all but the first of these 19 characters and you already know that so you don't want to start from scratch comparing for this next one uh the tricky bit is it's not so clear where are these shorter suffixes and where is the LCP value that you are trying to infer from this and in a way it gets worse than that it's not even clear if there is any LCP value for this uh because these two shorter suffixes might not be adjacent in the sorted order once you chop the first paragraph there might be other things in between and then there is no single LCP value corresponding to those those two suffixes but still it's still somewhat true right even if there's things in between they will also share this longest common prefix

17:29 so uh that's that's the the key idea behind exploiting it uh to turn that into an algorithm um the the smart way to do it that uh kasaida came up with is to just compute the LCP values in a convenient order and then all the complication goes away it's another I love this one because it's so simple to present but each time if you don't have an example prepared you probably forget how it worked and you uh have to reinvent it so we'll try to compute the LCP values in text order um that's why I have our favorite picture here again in text order means I'm trying to compare trying to compute the LCP values corresponding to the suffixes top down on the left but I will jump around in the actual LCP array on the right while I'm doing that

17:32 Kasai's algorithm - Example

18:27 and so in this case when you drop the first character you may not have adjacent suffixes but you can still use the information you learned from the previous face let's let's see the example we first look at the entire text that's the first suffix in text order I'm starting at index 0. I use my R array to map that to the right hand side so I know I'm at position 6 in here so I'm I'm looking at the LCP the longest common prefix between that suffix and whatever is just before it in sorted order this is the relevant LCP entry that I'm looking at and this one I compute naively by comparing characters so I find B matches a matches n matches then there's a mismatch so the longest common prefix is three so far so good nothing smart happened

19:31 and I remember though that while I will lose the first character this a n I will keep that in mind if I go to the next suffix in text order it will start with a N it has to because I know the previous one started with pan

19:56 but which ltp array entry am I binding now I look at the rank array and that brings me to this position so I know I'm looking at this suffix and whatever it comes before it in alphabetic order and I already know it has to start with a N Y again because uh it I previously compared with this one and this one without the B started with a n find this here now it's not the the one that I actually compare it with but all of these strings have a n as their longest common prefix and so in this case it happens what the previous slide said there was another suffix that smuggled between the two but if it ever happens like that the longest common prefix has at least this a n so what we do in this case is we inherit the two but then we start comparing the next character because there could be a longer match as in this case but then there's a mismatch so again the LCP entry we find is three

21:04 and we keep in mind that we found n a we keep in mind that we found two apart from the first character that matched and then we continue like this we go to the next position in the text find where are we in the right hand picture down here rank nine so we're looking at this and this and we already know without thinking they have to have at least two in common in this case these are exactly the two suffixes so we kind of know that they already have just these two and no third but we forget that we just do another comparison and compare B and N again and find they're still not equal but this little uh rediscovery is cheap because it's a single comparison so we find another LCP entry and we remember there was one overlap still after removing the first character so when we go to the next position in the text which we find over here then we can inherit one character that matches and we find one more

22:14 all right I think now you get to see the pattern we go to the next position in the text find where that is on the right hand side we inherit one match and that's actually the only match there is it's again a case where we have exactly the two suffixes without the first character so we have a new LCP entry and this time we we don't remember anything anymore and then the remaining ones this one has lcp0 they don't have anything in common these two would have done not anything in common uh these two have one thing in common so we have a one and this is the zero and that's it

23:03 so you see how things uh maybe we can already see you always just spend constant time in each iteration you inherit a variable number of matches and then you may spend time in one iteration but then many other iterations become cheaper

23:20 Kasai's algorithm - Code

23:22 if you write that up in code it looks like this um I don't think there's any anything uh worth pointing out so we remember in in L what's the length of the prefix that we already know about initially nothing then we go through all the positions in the text we find our way on the right that's the mapping to the right

23:55 we find what is the other suffix that we compare with which is the one just to buff it in sorted order but we have to find it in this in this way

24:05 then we compare the characters that are equal but we leave out the first L comparison the first L characters in both strings we store what we found and we set L to be one smaller or zero and then we continue

24:25 if you Analyze This in terms of the number of character comparisons counting how often we compare two characters the way to go in this case is to count separately how often you find a comparison where the outcome was equal and how often you find an outcome where it was not equal because then the not equals always terminate the loop we'd only do the character comparison at this point that's the only place so that's the only cost that we are interested in how often do you iterate this Loop over all the iterations of the Outer Loop every unequal outcome jumps out of the while loop and so we have at most one of these for each iteration of the for Loop at most n whenever we have an equal outcome we increment l so far that's all we can say but L can be at most n because it's a length of the common prefix and it's only decremented by one once for each of the outer iterations so we can decrement it at most n times so overall it can only be incremented two n times in the worst case and probably less

25:42 so for both of the outcomes we have a Bound in terms of n so the overall cost is linear if we have the suffix array and the LCP array both of which we can construct in linear time as you've seen just today uh we can actually reconstruct the suffix tree from that if we wanted using this construction with the LCP intervals but the the key message should rather be you don't want to do that you don't want to compute these two arrays to compute then the suffix tree from that and spend all that space the modern version is use these two arrays and maybe a few extra tricks so probably you want l r and LCP so three arrays to be fair and use those to replace suffix arrays entirely suffix trees entirely

26:43 so that's what people now call enhanced suffix arrays they're a little trickier to build algorithms for so usually what people do is design an algorithm as if you had the suffix tree and then simulate access to the suffix tree based on the suffix arrays enhanced suffix arrays it turns out you can actually do everything that suffix trees can with these arrays and they use much less space and it's much simpler to construct them for the mainly the reason because you can split it up into building first the suffix array and then the LCP array and then stuff on top whereas the suffix tree seems to be uh you have to solve everything to to get everything at the same time

27:32 no summary um so let me do that verbally that's the end of the string matching chapter um I I like this as one of the one I like this best among most of the the modules because it brings us very close to recent developments uh there are a few quite deep Parts but we've cracked one of the black boxes open that we started with we know how to construct a soft extreme linear time now at least the theoretical ideas behind it and actually we found something better the suffix race can do all so in practice you would not really want to compute the tree in the first place and so you could use that to build a small relatively small data structure for a huge text and very quickly find occurrences I I didn't say the one one thing that this for example contains is finding the occurrences of a pattern in the text you can get rid of this login factor using tricks on the LCP array that we didn't get into but it's it's one of the things that is possible and and all the other fancy applications of suffix trees you can also do uh but that's beyond the scope for for this um I hope you enjoyed some of the constructions

28:51 and um so that's uh that's all I want to say about text indexing