Video 6-6: Suffix arrays and string sorting

0:03 So I mentioned suffix trees are a good abstraction but we want to replace them in practice with something leaner. What could that be? That's where we uh start in this in this section. Uh we'll try to put our suffix trees on a diet. So if you draw the suffix tree in a specific way and what I mean by that is make sure that the child edges are in alphabetic order. So always the dollar child if there is one comes first that's preceding all the other letters in the alphabet. Then A comes before B comes before N and so on. If you do this at every internal node, you'll notice that the leaves, if you read them in the same order, left to right or top down here, they will give you all the suffixes of the text in sorted order by definition because uh the first come from the branch with the dollar that precedes everything. Then come all the strings that start with an a. Well, then so then they all precede whatever other suffixes there are. But then within all those that start with an A, I'm going to recursively sort by the next character.

1:15 That's precisely what aligning the suffix tree like this does. Now, how about we just forget about the tree and only use this sorted order of the suffixes. I'll call this uh the leaves array. L for leaves. Uh other other texts call this the suffix array. That's the same thing.

1:49 And you'll see in a second that there's um another array where it's very easy and inviting to confuse the two. And so my hope is that this is more pneummonic than just calling it suffix array. Uh we'll come to that. Uh as a first kind of sanity check, let's see if throwing away the tree leaves us with anything that's still functional. And as a sanity check, let's do string matching. If we're given a pattern, can we still find all the occurrences of that pattern in the text even if we don't have access to the tree anymore? And the answer is yes. Um at a slight slowdown at this point. uh but we can use the pattern and do a binary search for it in this sorted list. For example, the pattern A and A. Uh I'm going to do basically two searches. Um one for A and A with the dollar afterwards as the shortest symbol and then one with um an artificial symbol that comes after every other character.

2:57 I'm going to do these two searches. Now, this is binary search. You know how it works. Uh it would start here in the middle. Then you compare. Is uh okay, I have to pick a middle middle string. Let's pick this one. Um is this before or after a in the alphabet? It's after. So, I'm going to cut things in half. Um up here then. So far, it's like this, right? Then let's compare a n dollar. If we look for a not dollar then a dollar comes before strictly before then I might uh have this other check. So a dollar now comes above. So I'm going to move this up and then well two more steps or so I find that clean up a bit. Ana would go here. That's what binary search returns. It's the position in the array where I would have to insert this if I wanted to keep the sorted order. If you do the same thing with the anar hash, it'll come after all the anus. So it'll have to go here.

4:21 And now the beauty of these two positions is that they precisely delimmit the region of suffixes that start with a and a. So with two binary searches I found all the occurrences namely all the suffixes where this uh where the suffix starts with ANA and so um that's the the cost is is that of a binary search but every comparison compares two strings now and in the worst case these might be long strings and they might share a lot of characters. So I have to check from the beginning until I find a character where they differ and then I can decide the comparison. So that's why it could cost up to m character comparisons to do one string comparison. And this distinction between comparing a whole string which might read a whole long prefix and comparing a single character will come up uh in a second again. [snorts] But for now, let's say this is still very good. Essentially, the text is what is really long and the patterns we tend to think of as not quite as long. And the dependence on the text is still logarithmic.

5:42 It's not as good as suffix trees where this was irrelevant. The text could be as big as you wanted. It was constant in terms of the text and we only had m uh steps in the suffix tree reversal. Here is slightly worse. Uh but we're also not storing all this tree nonsense. So all these pointers are gone and we just need the sorted list. And remember this is what we tend to write it for humans like. But really the suffix array is just a bunch of numbers the the starting index of the suffix.

6:14 So even if we just store this single array, the leaf array where this is the the position R gives you the AR suffix in sorted order. You can still do string matching.

6:33 Okay, now uh we found another cool structure that we don't know how to produce uh at first. How do we compute the leaf array? Clearly by definition if I have the suffix tree I can read off in a traversal the leaves in the in order. But hey we're trying to get rid of suffix trees. So let's try to get rid of suffix trees. We can directly do this by sorting though. It's just the suffixes of t. They're there. And we can just throw just just throw any sorting algorithm onto it. That's trivial to code. You literally do that, right? you you sort the integers one to n and as a comparison function you give it read the strings that started that position is a oneliner in Python. Now uh in the worst case um each comparison can be expensive and so the best we can say as an upper bound and even in the worst case it'll be achieved is n squar log n time to construct the suffix array.

7:39 That's in a way even worse than the stupid construction of the suffix tree when you insert the suffixes one after the other. Ah, so we've managed to make things even worse. But of course, we can do better. Number one is we don't need to use a stupid general purpose sorting method. We know what we're doing. We're sorting strings. So let's uh exploit that fact. So let's um spend a few minutes on the general problem. You're given an arbitrary list of strings that you want to sort. Uh kind of I'm stressing this here because the ultimate solution here will be slightly different because we know it's not just an arbitrary list of strings. It is a very specific list of strings, namely the suffixes of one big text. And that is extra information, right? This is not an arbitrary list of strings in in our application, but we can actually get quite far with just exploiting that we're sorting strings here.

8:42 As we saw uh in the worst case, if I just use blackbox string comparisons, I guess that might be worth uh saying explicitly again even though it's is mentioned here. Comparisons can be between entire strings or individual characters. What I mean here is entire strings. These can cost a lot of character comparisons.

9:04 Now, these are costly if and only if the strings share a long prefix. Okay? Uh this is lexographic sorting. If the strings differ in the first character, I'm checking this one character and I'm done. Is only really a problem if they share long prefixes.

9:26 Now, whether or not that occurs or not in practice depends what you sort. If you sort URLs in the standard way where you start with the top level domain then the next. So you kind of reverse the way we usually write the domains then they might have a lot of common prefixes right everything that's from the same page from the same web uh from the same host say uh starts with the same top level domain then domain and so on. So it's uh it's not atypical that strings that are sorted have some long common prefix. So we should optimize a bit for this.

10:00 And the key to doing that is to avoid comparing shared prefixes over and over again. It's as simple as that. And uh there's there's two main options as with sorting. Merge sort and quick sort are the way to go. You can in both cases for merge sort and for quicksort find ways to make them not stupidly compare prefixes again and again. The tricks to do that are fundamentally different in a way. Um, and I've uh decided to just show the second one. You could do merge sort uh where the merges everything in merge sort is about the merges, right? The rest is just recursion. Uh now in the merges you have to remember the longest common prefix between the current value and the next in the sorted run. And if you do that then uh whenever you do the merge you're picking the minima of the two runs then you know what's the common prefix between the current key and the previous one and you know this for both runs. So that if you take the smaller of the two you know how many characters you definitely can skip and so you can also produce these values again in the output run. Um I'm not going to further look at this. Uh this is just for uh for your interest at the level I explained it here. I think it's not part of the exam. Uh if we find a nice uh nice excuse to put it in the exercises, maybe that's a way to teach you about it. Uh what I want to show in a bit more detail is the quicksort version that you can extend to sort strings efficiently.

11:45 uh there all you need to do is to have a partition function that looks at a single character namely the de in uh in this uh write up. So I'm only focusing on the de position in all the strings and my pivot is also a single character. I I'll pick a pivot string but I'm only looking at the de character. So there's three possibilities what the D symbol of all the input uh strings and my pivot string are like they can have a smaller character or the same or a larger character but we need the three-way split here unlike standard quicksort where you just have smaller larger uh here we need all three then on the smaller and larger I do a recursion just as for quicksort but on those that start with the same have the same def character I'm going to skip that character in the recursive call.

12:43 So initially I set D to zero. I'm starting with the first position. But then suppose I'm sorting URLs and they are all from or Wikipedia whatever. Then uh the first position they will all end up in the equal position for the last character for for the for the first character of the top level domain. And then they're all going to stay in this equal uh partition, but I'm advancing D to one. So the next partition step, I'm going to find uh according to the second car the the the character at position one where they are. Maybe they're still all equal, but I don't forget that they're uh have been checked. I'm not going to look at these characters ever again. Uh let me show this on an example a bit. Uh here's some some strings. And I highlighted the D character that we're currently looking at. So initially here's uh my list and I pick some pivot string is always going to be the first one in the example. Then I partition according to the first character and S.

13:49 There's two strings that start with something smaller than S. There's a bunch of things that start with S and two strings that start with something bigger than S in the alphabet. And you see for these I still have to look at the first character. I still might have to uh sort them like these are not in order. But for all those that start with an S, I already know they start with an S. I don't need to ever check this again. So I move on to the second character. So here you pick another pivot. Um now you separated the two strings. So it's singleton. That's done. Here I pick a pivot again. And now I partition all those strings according to the second position. There's a bunch of characters that have something smaller than H. These all start with an E, but I don't know that yet. All I did is compare with H and found that these are all less than H. There's one bigger than H, and then there's a bunch with H.

14:47 And for all those, I advanced to the next character because I know they start with SH. And that's uh how recursively you go here. In this case, you're you're not going to make much progress in splitting, right? They stay together. it's the same string, but I don't know that yet. So, you move through this step by step. Uh, once you have a single partition, you stop. So, here is another case where you move through all the strings. But you see, in each in each case, you either split something up or you advance and make more things gray. You're not going to not make progress. Okay, I'm going to spare you the rest of the example. Um, you can look through it if you want. And here it would take a few more rounds to check all those characters.

15:39 Uh, I want to briefly analyze how many comparisons we need for this because this seems like a a big mess. In particular, um, it seems to depend on the input strings, how many characters I need to compare. Like here, uh, if I have lots of strings that are the same or have a very long shared prefix, I can't say how many of these rounds I have to do without looking at the specific strings. It's not going to be a function just of n, the number of strings. Uh, but it is actually very easy to analyze with a clever trick. We divide the kind of comparisons that we do into two classes depending on the outcome. This you can only do in the analysis, but that's that's fine. We do the analysis. Uh there's decisive comparisons, which are comparisons that decide a string comparison. So it's a character comparison looking at two individual characters uh where the outcome was strictly less or strictly greater.

16:42 The reason they're called decisive is that if you were to compare two strings, then there might be a bunch of comparisons of comp character comparisons that come out as equal, but then once the first one comes out as less or greater, you're done and they decide the string comparison. So that also means we can have at most one such decisive character comparison per string comparison. If you were to revisit the original algorithm and this algorithm doesn't look like it does it that way, but if you uh combine rounds effectively you're partitioning the strings by sh to the extent that you have to. So for this partition you already know they're less than sh. For this you know they're bigger than sh. for these you don't know yet but you're going to continue. So eventually you know that these are uh these are SH E with something behind. So these are bigger. These are S A um S and then something not H. So they're smaller. And these are SH and then something bigger than E. So these are bigger. Over the course of potentially several rounds, you will eventually have compared the strings with shei.

18:07 And all of these comparisons, every string with shei, over the course of several of these rounds, there will be at most one decisive comparison, exactly one, I guess, uh, between any of these strings and she. It might just be delayed. You might only discover this decisive comparisons later and when exactly is not clear but it will be just one. So in a way you can analyze uh the decisive comparisons just as in the standard sort where you have uh comparison based sorting forget about strings. It's going to be the same number. And for quicksort we know how many these are. If you take pick random pivots, uh we know precisely what the expectation is. The other comparisons I called LCP comparisons because they're essentially uh telling you about a common prefix. They come out as equal and that means there's two characters at the beginning of some string that are equal. The important bit here is that we'll never ever compare these characters again because the structure of the recursion with this parameter D means that we remember that they're equal.

19:25 And the way to analyze how many you need there is is a clever reformulation of the problem. The LCP comparisons are precisely the steps that you would need if you were to insert all the strings into a try in so a standard uncompressed try where you just have notes for every for every character that you uh go down. We're I'm not I'm not saying that's what we do to implement this, right? This is um it's just a metaphor for the analysis. If you imagine you would build a try for these for these strings, you would start here. Then there's maybe an A here. But then you don't need to go further to compare R E.

20:10 Uh that's no longer needed. The A was enough. So it's a it's I should maybe say it's the kind of try um where you contract unary paths to a leaf, but you leave other unary paths un unchanged. So, uh, but it's not a compact try. Let's do one more example. So, there's the B, which only has the buy.

20:54 Uh, then it gets more interesting with S. There's a lot of S. And now here, um, there's S E and there's SH and there's S U. But then with SU, we already have the surely.

21:26 Whereas SE is split up further, right? all of these here. There's an A and there's an L. And if you have um if you have twice the same string, that's a bit of a degenerate situation that we probably for the analysis would try to avoid. I think we would um in this case assume there's uh L s and then there's two dummy leaves one for each copy of the string. So you would you would build the string like this and if there's a unary path that further splits at a later point you would leave it. Um but otherwise uh you would include all the strings. Now the number of LCP comparisons is precisely the number of of edges here that you have to follow to insert a string.

22:48 And so this maybe doesn't look like it's all that helpful because it still depends on the strings, but it tells you precisely that that's the number. And the good thing about this try is it's it's the minimal number of such comparisons that you have to spend to even just verify that a given claimed sorted order is correct. If if you were given the strings as a list and you were to check are they in sorted order, you would compare this the first and second. Well, you have to compare the first characters for doing that. Then the second and third at some point you might have cells and cells. We know that they're equal, but the algorithm doesn't. So, it has to compare all the characters. And that's precisely these these paths down here.

23:41 which means that uh that number of comparisons is needed by any string sorting algorithm. So the number of these is kind of optimal even without doing much as long as you don't repeatedly compare things. uh and the other number we can we can bound by another analysis.

24:09 Okay, so overall um this is still simple to code. All you do is quick sort with this extra um partitioning method where you check a single character and it works well for typical kind of strings. uh in particular um if if the uh input are random strings where each character is is randomly chosen independently of the others it's still an efficient algorithm uh but it does have the same worst case because uh if you take this text of all a's the suffixes have maximally shared prefixes and the try to build uh for all these there's nothing you can leave off so um in the worst case this is uh still bad and there's no hope to do better with any other kind of string sorting method. It's not quicksort's fault. It's just a inherent as long as you use a general purpose string sorting method, this worst case will will remain. In many practical situations, this is already good enough and you would probably not see anything that is as repetitive as this text. And so probably it's fine.

25:19 But we'll see. We can do much better. We can do linear time even in the worst case.