Video 6-9: §6.8 LCP arrays

0:00 Intro

0:02 in the next sub section i want to look at the lcp array and that will be a way to augment the suffix array with something that gives us more power it gives us more ways to work with the text that the suffix array is built from my motivating question was uh which feature from suffix trees did we actually use in some of the more advanced applications the of suffix trees and in particular the one of this longest repeated substring so remember long's repeated substring is you've given the text and you try to find two positions where when you start reading from there you see the same string and you would like to know what's the longest you can keep going and read the same text what's the longest string you find twice in the in the text um so let's switch to someone since you had time before to vote let me just show this right away and most of you got this it is the string depth of the internal nodes and the reason was again

1:14 here we have uh the famous suffix tree for our example that i bought you with for two weeks now if we compute the string depths of the notes so that's just the length of the of the string on the path from the root to that okay sorry you didn't see that

1:40 String Depth

1:44 and so here's um here's y again just as a reminder we annotate each node with the length of the string from the root that leads to this node that is the string depth of that internal node and then the longest repeated substring was one was the path labeled to a node that has the largest a lightest string depth so the largest string that was free in the example and we had anna and ben as two examples um [Music] here let's let's simplify the task a bit and not ask what is the repeated string but just how long it is and then literally just the string depth is the answer

2:29 and in this case it was easy then to find that but let's let's for now focus on just having the string depth of all these internal nodes the suffix array doesn't give us that the suffix array just gives us

2:45 maybe in gray so here's here's the suffix array it's a bit weird to draw this as an array but you know in a sense it is just that i need some artistic talent that i'm lacking so if you imagine to pull these down at the same level then they they form an array and that's the suffix array it just doesn't give you the blue numbers

3:18 so the idea is if it doesn't yet give us the blue numbers let's store the blue numbers on top uh but we have to find a way that we can link this together with the suffix array because we don't have the tree we don't have the shape

3:34 and the the topology of the tree anymore we wanted to get rid of that so what we'll do is the following we have this the leaves connected left to right in the suffix array um from each of these connecting lines we can make a detour through the lowest common ancestor of those two nodes of those two leaves okay some go all the way back up to the root you can have this several times for some of the notes

4:12 that's a big mess i guess um maybe instead of drawing it like this so that's the concept but let me just draw it as a single line so between these two

4:45 LCP array

4:49 we jump back to the root between these two the lowest common ancestor five and seven is this one then here we go to this here we go to this between those we go back to the root back to the root and this okay i think that's a little a little clearer

5:07 and so the lcp array as formally defined on the slides is just the string depth of the nodes that you point to here so it's 0 1 2 three zero this one's a three this one's a zero a one and a two okay in other ways and in other words the lcp array starts

5:43 is always between two suffixes so the indexing is a bit inconvenient it doesn't help to call it index 0.1 so instead we start at 1. and the r entry say r equals 1 would be this one means we take the longest common prefix of the suffixes that start at the position and the previous one and if you look at the suffixes here this one starts with is just the dollar and this one is a band dollar they don't share any common letters at the beginning they have a longest common prefix of length 0. that's why the lcp array entry here is 0. okay so same way as the suffix array is reading the leaves from left to right the lcp array is reading the string depth between adjacent leaves from left to right

6:46 and if you just want to find the maximal string depth that ever occurred in the suffix tree then you can just find the maximum in the lcp array that part's really easy

7:04 and let's let's look at this um a bit more um and that's a beautiful connection so i definitely want to show this um in some detail this is the suffix array for our famous example you may remember these numbers by heart now there they are these are the suffixes in sorted order what you see in red between the two adjacent suffixes is the longest common prefix so these two have just the letter a in common and then they differ at the second letter these two both start with anna but then they differ and so on and so forth and for some strings it's no common prefix okay

7:49 so that's why the lcp array for this example is 0 1 2 3 that's just the length of the red strings that's the same numbers that i've shown you before so zero one two three zero if you go back to that slide it's zero one two three zero although that zero looks like a six it's a zero

8:18 now um if you don't just look at adjacent suffixes but a whole range say from here to here all these four suffixes start with an a so in a sense there's a plateau where they all share an a as a common prefix at least in a they may share more if in this case you go further make the interval slightly smaller and you can draw this for the other ones now so these are called lcp intervals but we don't really store them that's just

9:00 something we envision or something in our mind for now the cool thing about these is that if you now compare them with the suffix tree there's a one-to-one correspondence between the lcp intervals and the internal nodes and that's that's shown here so let's pick an example let's pick this aaa which corresponded to this interval these four suffixes all start with an a and so what this correspondence means there is a range where all subjects and that range corresponds to this internal node that groups the same four suffixes together and their shared prefix is the path from the root to that node and that's not coincidental this is always true whenever you have an internal node in the suffix tree for example here this ban leads to that node there is a corresponding lcp interval so a range in the lcp array that is at least a certain value notice that the lcp array in this example where we had a as the shared common prefix all the numbers in between are at least one you never go down to zero

10:28 for this one the interval is short it's just these two and three never goes below three well that's kind of an empty statement what this slide is supposed to convince you of is if you have the l the suffix array and the lcp array basically all information that used to be in the suffix tree is already represented it's a little contrived you have to think around corners to get there but it's all there it's nothing really lost by just looking at these two arrays you can from these two arrays figure out what the suffix tree is okay and we'll explore that a bit uh at the end

11:23 so that's this statement those two arrays really give you everything that this needed for the tree