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

0:00 LCP array construction

0:03 i've explained you now what the lcp array is and why it seems like the right definition to augment the suffix array to get the same functionality as the suffix tree what i haven't told you so far is how to compute the lcp array as always first think about the the naive and simple way to do it its longest common prefixes so you can always compute this by step by step each pair individually but just looking at the two suffixes and comparing them left to right how many characters match but obviously that could be um i can go for a long while if they share a lot of suffix if they share a long comment prefix so the overall time could be quadratic and that's out of the question that's way too slow for anything interesting

0:56 but the the key insight how to do it faster is is this one suppose we do see a very large lcp value and that's one that is costly if all the lcp values are small then the if method would work fine it only runs into problems if there are many long shared prefixes so the post there is a costly lcp value that means we can also find another one and let me show that on this example a valid example of an english sentence you can actually add three more buffalos so it's buffalo buffalo buffalo buffalo a nice coincidence that buffalo is a noun and a verb at the same time and well you can read about this you can go up to seven buffaloes but that's uh not my point for today it's just a nice example with a lot of repetition if you look at the the suffix array of this text i know i shown the the first few suffixes here um then you see that they have a lot of things in common for example the the second and third or well at position two and three they share this long aloe buffalo buffalo okay if we chop off the first character of those two suffixes we get another suffix obviously it's not

2:22 so clear where in the sorted list it is but it's clearly the suffix that starts one character later so if we have the suffix array in the inverse suffix array we can find where they are and uh just by definition if these two share this sub uh this uh long common prefix if i take off the first character on both they still share the same common prefix except for the first character that's gone so if the lcp entry here was 19 i'm now sharing a prefix of length 18 and i don't have to spend a single comparison to know that it's by definition it has to be like that there's only one issue here it's it's not so clear which lcp value that is and things get worse it's not even clear if these two suffixes are adjacent in the sorted order right it's you're taking a character away so that mean it might mean there's more suffixes between those uh in general that can happen and if that happens there is no lcp array entry where we would get the value of 18. so it seems like this is this is a good idea because it allows us to save effort we can if we once had to find this long common prefix we would like to

3:48 exploit that fact for other values and amortize the cost but it doesn't seem to work quite exactly by doing that but there is a way to do it and that's uh casaidal's algorithm so they found a very very nice simple algorithm to do this and i want to illustrate it just on an example the key idea is we don't compute the lcp values in the order of the array starting with lcp of z of 1 then lcp of 2 etc that that seems not easy to do efficiently instead we compute the lcp values in text order so we start with the longest suffix and then work our way through the string i'll show you the example and we use the observation from from the buffalo example if we take if we have a long shared prefix and we take the first character off that shared prefix will not vanish we don't know if they're if the resulting suffixes are still adjacent but even if they're not they might be further apart but then there is another lcp value between those and that value must be at least as big as the previous one minus one i think this will become much clearer in the example so let's just get cracking with that we start with

4:11 Kasai's algorithm - Example

5:12 the first suffix in the text order that's the entire text so we start with i equals 0 here's the entire text now the first thing we do is we find the corresponding lcp value and for that we have to move to the right so we look into the rank array and we find the same string at position 6 in the sorted list remember the lcp values they sit between the adjacent suffixes in the sorted order so the lcp value for six is actually talking about this suffix and the one that precedes it in sorted order and that happens to be ban in this case and we we know which suffix that is because we can go to rank six minus one and then use the suffix array to know where the starting point for that suffix is but the uh what we do in this example here you you just directly see this so just uh imagine you've written down the sorted list by uh explicitly what we do now is find longest common prefix of these two suffixes and we do that in the naive way so we just compare we find this is it they share this long this common prefix of three characters so the lcp entry for this is three that was just the naive way to find this

6:42 common prefix now we want to take that knowledge and learn as much from it as possible for other lcp values and remember uh the idea was to chop off the first character so what we do is uh if we chop off the first character we know there's still this n that is uh matched and kassai's algorithm now says okay you just go to the next suffix in text order that corresponds to chopping off one the first character you find

7:18 that chara you find where that is in the sorted list using the rank array so you go to the right and you find this is this is the corresponding suffix that has the first character omitted and there is one preceding it now notice that this one maps to this if you take off the first character and this one maps to this if we take the first character off so this is an example where the two are not adjacent in sorted order there is something in between but we can still make use of our knowledge about this common prefix because we know a n must be shared it was actually shared between all these between this and this but because they are in sorted order it must be also shared by everything in between potentially more like in this example we can see here that we can extend this shared prefix by another character that was not implied by the previous the previous lcp value we only knew that a n doesn't have to be compared again they have to be the same we don't have to check them again but we potentially have to extend that match and that's what we did here so we spent one extra comparison and found another lcp array entry of

8:40 3. okay that's how this algorithm works let's see how it continues what we've learned from this for the next example is there's a shared common prefix of n a we go to the next entry in in text order find where it is in the sorted order we've learned from before that n a is shared but we have to compare the next characters in this case they don't match so the lcp array is the entry is two because they just share this this inherited common prefix

9:21 we remember that there was one shared if we take the first character off now if we find the next the next suffix in text order in the sorted list we know that they have this a in common because these are well again um this is this one becomes this suffix if i take the first character off the nair ban actually becomes the a band so there's more they share but this definitely also has an a in the first position that's what we know there's another character that we can match this we find by just naive comparisons and that's it then they then they differ so the lcp entry at this position is a 2. so you see how this goes we compute the lcp values in text order but what that means for the lcp array is that they were filled in some seemingly random order the important point will be that we can make use of previous comparisons to avoid spending more on the next step let's briefly finish this off the next in text order is is this one we find it here we actually know that the n has to match from previous from the last entry but then that's it so we have an entry one in the lcp array for the next one we find it here because

10:43 the previous entry was only the first character once we take that off there's nothing left so we know nothing about those two and if we compare them we find that there is indeed nothing that they share so the entry is zero and as the strings get shorter this is a typical phenomenon if we find this one here they again share nothing um and we we again don't know any common prefix for the next round finding this one here we find it at least shares one uh character at the beginning

11:24 that's by naive comparison and the last one is again a zero because these don't share anything and uh notice that we never have to look at the last suffix because that's only the dollar sign and we know the dollar sign is not shared with anything and also it's the the first entry in the list so there wouldn't be anything that precedes it to compare with that's kassai's algorithm by example here is the same thing written in code i probably don't want to spend too much time on this but just how does it work l stores the current length of the common prefix that we found initially that's zero then we start with the first position in the text we find so we start

11:49 Kasai's algorithm - Code

12:33 we now look at the suffix starting at position i we find its rank in the sorted list that's moving from the left to the right that's r so what we will do is we compute the entry lcp of r and uh we'll note that this r can never be zero that would mean we've reached the uh the end of the text just the the dollar and uh we stop here at n minus one we never let it reach the last because there's no lcp entry for that to compute anyways now this uh i minus one maybe a bit weird of a notation but that just is the starting index of the suffix that precedes this thing on the right so uh if if this would have been my r then i minus one would be zero because the suffix that precedes it in sorted order l of r minus one is zero that's the starting index here for banana ban uh that's exactly that

13:42 and then here we do the actual character comparisons and notice that so we start we compare the suffix ti and the suffix ti minus one but we start comparing at the elf position of those suffixes because we already inherited a potentially a shared common prefix of length l initially that's zero but when the algorithm keeps going l can have a larger value in in the time that's that was the the green characters in my example so as long as we find matching characters we increment l as soon as this terminates l is the actual length of the shared prefix of these two so we store that in the appropriate position and then for preparing the next round we subtract one from l but we never go below zero that is taking the first character off the share prefix and then continue so in code this is really really short and concise to understand why this is correct why this computes correctly the lcp arrays i think the example is much more insightful but the code is useful to have to implement it and to analyze it that's what we still have to do um

15:04 the overall running time is linear as i as i sketched but i want to give you a very nice little intuitive argument why that is the case what we'll count is the number of character comparisons as most of the time in the string chapter and the key insight here is these character comparisons they only happen at this at this single position right so this is counting how often we have to iterate this inner loop and the key inside is we have to separately count those that come out equal and those that come out unequal then we can easily bound their total number whenever one of these is unequal that means we leave the internal the inner loop and we only do that once for each iteration of the outer loop right for every i we enter this loop repeat that a couple of times but then eventually we leave it when the characters are unequal so we do that exactly as many times as the outer loop is is run so it's at most n comparisons from from there

16:17 so these are these are fine these are linear in number the equal comparisons are a little more concerning because for each individual iteration we could spend a long time running our circles in this inner loop but we can again do a potential style argument this l value always increases by 1 in the loop but it's only decremented n times in total because it's only decremented here and that's only run once per iteration so only n times in total and uh we also know that l can never be bigger than n because that would be the entire length of the string so you can only walk up with l a certain number of times you can never walk down more than n times and it stays below n that works out to at most two n increments

17:19 in in the word in the worst case so both operations are overall limited by uh a constant times n so kassai's algorithm runs in linear time even though it's based on the naive version of just comparing the characters from left to right but by exploiting the fact that a long shared prefix of of two suffixes implies another shared prefix of two other suffixes we can get the overall running time to linear

18:01 okay with that we can go back to suffix trees so we found a way to construct suffix rays we found a way to construct lcp arrays and these two things actually encode all the information in the suffix tree that's what i've shown in this picture before so a way to get a reasonable practical algorithm for suffix trees is to compute the suffix array compute the lcp array and then construct the tree from those two you will actually look at this construction on an example in the tutorials so i don't want to talk about this in detail in class but once you have these two things and observe this connection it's actually not too hard to really construct the suffix tree if you wanted and that is finally looking into this magic box remember initially before easter when we started this this uh text in the indexing chapter i told you there is this magic data structure the suffix tree famous people conjectured that it doesn't exist because it it solved problems that they thought are not solvable in linear time and yet it does exist and it's constructable in linear time but it's complicated and i don't tell you how yet but here you actually learned how you actually you've actually seen um how to do this

18:03 Back to suffix trees

19:32 in most of the details and i think that's a that's a good a good starting a stopping point for this unit concluding this this section and actually the entire unit a little bit earlier than i thought the enhanced suffix array that usually means the suffix array plus x where access the lcp array sometimes plus additional things again i'll refer you to the tutorials for one example what this other axe could be but usually based on the suffix array and the lcp array you get a simple data structure that's that's easy to handle in code and that can support the same algorithm as suffix trees without using complicated ways to represent the tree efficiently so these are really the modern version of suffix trees unfortunately not as widely spread in textbooks yet but i think this is just because the suffix arrays and all these algorithms they're all from this millennium they're all past 2000 this is fairly recent stuff giving given that this is such a fundamental problem it just took people uh time to to figure out these connections so in in their raw form it can be a bit harder to reason about these enhanced suffix arrays as opposed to the trees but the way that people use these is you think of an algorithm to solve a problem

19:41 Conclusion

21:06 on suffix trees and then you find a way to simulate what you need in the tree based on the arrays and usually that works out fine i haven't seen an example where it didn't eventually where someone didn't even well not eventually someone invented a way to implement it based on on the arrays it uses much less less space both are linear so this is an example where the theta notation is a bit misleading both have theta of and space in theory but the constant factors do matter here and you've actually seen a linear time construction for the