Video 6-10: §6.9 LCP array construction & back to suffix trees

0:00 Naive LCP array construction

0:02 so in the next section i want to convince you that the lcp array is not only useful but also quite easy to compute let's first take a look at what we could do just naively how do we fill the lcp array and how long would that take by definition each entry in the lcp array is the longest common prefix of two suffixes so i could do just take the two suffixes and compare them character by character and count how long the characters are equal that's fine but in a contrived example like the text with all a's is the worst case for most of these things you always have to walk till the end and so this could take linear time for one check and quadratic time in total so that's not brilliant

0:58 the insight here is that if you ever see a big value in the lcp array you will be guaranteed to see other big values so there's in a way a charging scheme behind this if you if you have ever had to go a long way of comparing then there's way to make that knowledge pay off in the future that's an idea vaguely that at this level of abstraction we've used it before amortization uh but let me illustrate in an example why why this is promising and so here the text is this i don't know if you know this famous english it's a valid english sentence just because english is so great in ambiguity the full version is buffalo buffalo buffalo buffalo buffalo buffalo buffalo buffalo proper english sentence you can look it up i went for the slightly shorter version here just to make the point suppose you try to find the um so you've you've constructed some of the suffixes in sorted order that's the first suffix that's the next in sorted order in lexicographic order than this one and so these two you would now like to know the longest common prefix so all right there you go they are pretty much identical up to the dollar so that would have been an lcp value

2:21 that you would have to pay for a lot because you need to compare all those characters but if we have these two really similar strings that start with the long common if i throw away the first character the rest of the the remaining 18 characters are still the same so somewhere in the suffix array i have these suffixes where the first character is missing and the rest is the same and they still have this long longest common prefix it's just one shorter okay now it's unclear where those are and it's unclear where to put this value 18 and even worse um it's not clear if there is ever a value at 18 exactly the problem is that if you chop off the first character you don't no longer know if these two suffixes are adjacent there could be others that are between them and you only have lcp values for two adjacent suffixes

3:33 but the same idea can still be made to work and that's the algorithm i want to present you now it kind of uses this idea but in a slightly smarter way by turning things on the head if you want

3:36 Kasai's algorithm explained

3:53 the key idea of of this algorithm is to compute the lcp values not in the order of the suffix array like lcp1 lcp2 lcp3 and so on but computing them in text order so what this means is shown in in this picture again text order is on the left and so the first thing you want to do is compute the lcp value for the first suffix this lcp value where this the longest text participates in and then

4:34 we we can drop the first character this might not be directly what we need but we can make sure that we don't throw away knowledge so i think this is clearest in the example

4:50 so we go through the suffixes in text order so we start with the one that starts at position zero we use the the uh write array the rank array to see that this occurs at position six in the sorted list okay so that tells us which lcp value we're actually trying to compute first because it must be the one between the suffix here and its predecessor in sorted order and so that happens to be the suffix starting at six and then the algorithm naively compares so we started the first character these match so they are shared longest common prefix continues continues we found those three uh then the next one differs so the longest common prefix between those two is three so far nothing smart happened right we just compared naively and we can fill the first entry in the lcp array namely the one that corresponds to the longest suffix okay

5:58 now what happens if we remove the first character from both of these suffixes well of course the longest common prefix is one shorter but there is another thing that happens if i remove the first character i get to the one smaller suffix of the text so instead of the entire text i'm now looking at this one i didn't want to strike this out uh this one so that's the next one to look at and we remember that we've matched two characters in in the previous comparison after we deleted the first one okay so same game again we start from scratch we have this one it the rank array says it occurs at position 4 in the sorted list so that's where we go and so the next lcp array entry will be the one at position four and we compare this string with its predecessor in the sorted list now notice that this this uh band with a with b deleted is not the predecessor it's one that comes before it that's one of the cases that i want you before there could be other suffixes that now lie between those two

7:21 but we still know that this one and this one they shared a common prefix of two and so if this new string is between them in sorted order it also has to start with a n otherwise it couldn't be at this position so in fact all the strings between this one the shortened predecessor from before and the shortened uh suffix we're looking at all of those in this range must start with a n so we inherited this longest common prefix of a and we don't have to check it again that's why it's shown green we know that two first characters must be equal and we just compare with the ones afterwards in this case the a matches but then we have a mismatch so we have another entry of three okay can you see how this goes let's do one more if we chop off um another character then we're at this position the rank array that occurs in position 9 in the sorted list so that's where we go we try to find their longest common prefix and we know from before we don't have to check the first two characters because they must be the same if this and this agreed on the first two on the first three after leading the first one these still agree on the first

8:47 two and so really what's happening is just we take the previous lcp value we wrote and subtract one you don't really have to check which suffixes are involved etc that was just for explanation the algorithm just says okay i know three was the last value so two are definitely the same i don't have to check and then you keep reading this time we have a mismatch here so we leave it at that

9:16 now let's do another one so they become faster and faster now that happens to be at position 3 here so we have to compare those two and find the longest common prefix we know by the last value that we wrote that at least the a matches now in this case we can continue it by one more so we indeed have a two again but that's it so then we go to the next position in the text this one we find it in the sorted list at rank eight we know they have at least one character in common and if we compare one more we find out that's the only one so we write a one okay

10:01 and that's how it goes uh for this one we know from before we know nothing it's only one minus one is zero so we have to start comparing we find there's actually nothing in between so that's that remains a zero

10:16 next character we find where it is in the sorted list uh we know nothing and we compare and there is nothing so it's another zero let me go to this guy uh here again we know nothing but we find um overlap of one so we write that there and well two more and so well the last one we actually don't have to do anything because uh the um the one that has uh rank zero is the first in this list and so there's no predecessor and that always happens to be the the suffix with just the dollar sign so we just we can just stop at one one early okay that's kazai's algorithm for computing these lcp values

11:01 Implementation details

11:09 because we've done the example in great detail i don't want to go through the code in detail that's exactly spelling out the the same idea i don't think it reads well in the code the example is much clearer there's just the one thing i want to point out you keep track in l of the length of the longest common prefix so l is this value that we wrote at the end in the current lcp array entry and then we subtract one but never go below zero so that in the next iteration when you start comparing you start comparing at l and not with the first characters that's exactly what we did in the in the example skipping the green parts

11:58 Complexity analysis

11:59 let's briefly think about why this algorithm is linear time though and what we'll look at is the number of character comparisons because that's the dominant operation in finding the the common prefixes and the trick for the analysis is to separately count those that come out as equal and those that come out as non-equal it's just easier to count them separately

12:26 every character comparison that comes out as not equal must be the end of a common prefix so that's where we detect no they don't share any more characters and this can happen only once for every lcp array entry because we stop after that that's something that's obvious in the code you ask are they still equal and if not then you continue with the next iteration so we have at most n of those at most as many as lcp array entries the interesting ones are the ones that come out as equal because they might be frequent you might have to compare many long prefixes but whenever you do have um one of these characters comparisons that come out as equal you increment l that's obvious again in the code um at this point you increment l

13:21 but l can be at most n because it's the length of the of the string and we decrement it at only one position and we do that only once for each outer loop iteration so it's never more it's never decremented more than n times so the most equal the most known the largest number of equal comparisons you could ever have is 2n because it could go up to n and then be reduced down but that's that's it

13:52 okay and that leads us to linear linear time overall the argument here is is quite similar to what we've had with the kmp algorithm in in unit 4 and and for other methods it's oftentimes a similar kind of argument you have some some potential that is built up slowly and you just can pay much in one iteration but it has to be then followed by many cheap ones

14:25 Enhanced suffix arrays

14:26 that's the end of the suffix array construction and to finally bring this long unit to a close i want to point out that we have solved this first big magic black box that we started with at the beginning because we can now finally compute suffix trees and in linear time and you've seen all the details for that we can compute the suffix array for t it took us the better half of today and a bit of build up before to go through the algorithm but the dc3 algorithm shows you how to do this in linear time we've seen kasai's algorithm for the lcp array just now still linear time and from those two you can actually figure out the suffix tree using this idea of lcp intervals i haven't shown you the details you will practice it on an example in the tutorials and it will essentially close the loop in in unit 9 with the concept of the cartesian trees so maybe if if we have enough time i'll point it out there in more detail if not then take the take my word for step three uh you can relatively easily piece together the two arrays and build the suffix tree if you want to

15:45 it's a legitimate question though if you ever have to build the suffix tree as opposed to staying with the two arrays that's my my last point for this one these two things together the suffix array and the lcp array and sometimes a few extra data structures to help work efficiently with them that's called the enhanced suffix array and in a way that's the modern version of suffix trees the only downside i see is that it is more complicated to reason about because it's just these lists of numbers and you always have to keep in mind what is l and r and all these things but you can support the same operations as in suffix trees and there's even um an automatic way if you came up with an algorithm for suffix trees you can translate it to one that works on the arrays in a in a schematic fashion it uses much less space compared to the tree especially if you do it in the easy way and we have a arguably simpler linear time construction at least one that i dare to present to you uh in in a lecture whereas the suffix tree ones are are questionable they are even more intricate

17:01 Applications and compression

17:05 so we've seen all the details of text indexing building the uh enhanced suffix array of a text and then you can do all sorts of cool searches and analysis on the text and that's the basis for many things

17:22 one pointer for for current directions is to reduce the space even further so you can do all that we've seen if you also try to zip the text so you try to compress the text but at the same time keep all the functionality we've seen and that kind of all builds on these ideas so that's still worked on a lot and is what you need to do if you have genomic databases where you don't have just the genome of one person but a thousand people or even more then you need to compress otherwise you just don't have the space to store that and that leads into the next unit where we look at compression without combining it with this unit but we'll do the basics for that part as well