Video 6-7: Wavelet trees

0:03 I want to show a few other succinct data structures or data structures for more complicated types of objects. And I'll I'll try to do it fairly quickly. Maybe 5 minutes is not enough to cover all of them. We'll do maybe a few next week then and leave a bit less time for for the external memory stuff. But all of these they're going to be covered with much less detail. The first is sequences. So we're representing strings. They're called sequences in this context for no particular reason. But I stuck with the terminology that's that's used there. So you have some array. You can think of this as an array over integers. Sigma is the alphabet but we'll just use this the first integers as letters. And the kind of operations that we want to support are similar to what we had on bit vectors. For those of you who remember bioinformatics, this is eventually used in FM indices etc. So there it's well motivated where these operations come from or what they are used for.

1:11 Well this lecture they kind of just handed to you with the promise these are the ones that are useful or these are useful to support say maybe it's not the only operations that are good. I guess what's missing is also access. So just reading out the character at a certain position. Now are you saying what you're talking here? This is just an array of things. We'll destroy the array that we get as input and represent it in a different way. Same as we did for the compressed bit vectors. And so supporting access to the elements is no longer completely obvious. Also note that for a general alphabet you can't use the rank trick in the same way as we've done for bit vectors. At least not in constant time. We would have to try each alphabet character. Is there a difference in rank between my position and the next? Then I know that character occurs here. But if I have many characters, I don't want to try them all.

2:16 Okay. Other than that, um the operations rank and select are as you would imagine, except that now we have to say which character we care about. And here's some examples. There's a a text and then uh rank and select for the different characters. There's just three that occur. So, rank with respect to A says how many A's are to the left of my position. And otherwise, it should be as uh previously. So, if I ask for position four, it counts how many A's are to the left of position four, excluding that point. And select is the opposite.

3:01 Uh as I mentioned, um the main use of this is in a compressed text index. So, that's a data structure where you give uh again a sequence, a large text, but on top of these these rank select queries, we don't really care about for text. What we care about for text is searching uh patterns in the text. But it turns out you can support that eventually based on rank and select. That's what the this FM index does. And we'll see an example later that you can use the data structure I'm I'm going to show you also in a different context.

3:36 Uh the data structure we'll look at is called a wavelet tree. Uh here's what it's uh what it promises to do. And then I'll I'll briefly show you what it uh consists of.

3:53 Uh so, we can do um reading letters of any position in log sigma time, so logarithmic in the alphabet size. Uh, often times the alphabet is small, so this is maybe close to constant. Maybe not if sigma is big. Uh, depends. And you can do rank and select in the same time. And it overall uses n log sigma space, which is the number of bits you would need to represent this text in plain. So again, you could say it's a succinct data structure. Uh, n log sigma is the lower order term the the lower bound from information theory. If you want to represent n characters, each of uh, range sigma, each could be one of sigma options. And then we'll add a little o of n log sigma uh, for indices How does this work? Um, for that I have a a little animation for you that shows um I don't know if you can read the characters well.

5:07 As I make it much bigger, I can't see my buttons anymore. So here's a a small example um and it has a b c d e f g h, eight different letters. And up here is a sequence uh or a string comprised of of just random letters. The way we store this is by uh essentially um uh, quick sorting this string. What do I mean by that? The first Now, this is not real sorting, so we get to choose a perfect pivot. At the roots, I'm going to um partition my string into all the characters in the first half of the alphabet and the second half of the alphabet. So, the first four letters and the second four letters. Now, I need to represent how I partition. Sorting is in general a destructive operation. After I sorted a list, I can't get the original back. But here we want the original because that's our string.

6:05 So, we'll write down a bit vector at the root that says, "Oh, this element compared less than the pivot. This compared larger than the pivot." And there's no real pivot value. I'm I'm just going left and right. There's no ties. I cannot be equal to the pivot. The pivot is I don't know. Uh character D.5 or so, right? Uh doesn't exist. Um what I'm left with is on both of these sides a string over half of the alphabet. And potentially shorter, but this is like the the string may not be equally distributed uh because this is randomly chosen. It works out to be roughly the same length. But in principle, it could be that one side is almost empty. >> [snorts] >> Okay. Now, with these bit vectors, I still have the information conserved whether I'm left and right. So, on the left and on the right, I just squish all the letters together and forget about the positions.

7:04 The positions where these letters are found in the overall string is in a way preserved in this top-level bit vector. Okay. I'll show you how the queries work in a second. Um you recursively split the alphabet in half until you have a single character. Then you have these leaves where you don't need to store a bit vector because these are uh nothing nothing interesting is happening in the leaves. So, let's first see how you can access the character at a certain position. And maybe not position one. I don't know. Say position five.

7:44 So, you find You started the root and you find the character at position five. Uh position six, excuse me. Uh all you have at the root, I mean the the string here is not really stored. All you have I should have said this, all you store is the bit vector. You know the size of the alphabet, that's assumed to be statically fixed, and you store the bit vectors. The strings themselves here are just to help you in the animation. So, we see here that the letter will be G, but we don't really know that yet. All we know is uh we're in the second half of the alphabet. So, I should go uh to the right-hand side. That's for sure, because there's a one at position six. But now in the right-hand side, I I kind of lost where my six is, because six was in the original string. Here I have some random subsequence.

8:32 But it's not really random, it's all the letters that are bigger, and all the letters that are bigger have a one here. So, I'm going to do a a rank query in my top-level bit vector. That tells me the how manyeth character in the right child I am with my position six. And here there's two ones, so I'm the second. That's why here recursively I'm looking at the second character of that subsequence. And then you recurse, right? So, here again I'm going right. And I'm the second one, so I'll be the second position here. And now I have zero, so I know I go left. And there I find my letter G. Leaves remember what letter they stand for. And so you can uh read out a symbol from this text, and clearly that the running time you need is one rank query per level, and there's log sigma levels.

9:33 Um you can also do uh rank queries that way. Suppose I want to know um how many A's are to the left of say position a bit larger 13, whatever.

9:50 So, um I started at my position 13 in the root. Now, how many A's are to the left of there? I don't know. At the root, I only know whether I'm left or right. So, I check if my letter A, the one that I'm counting, is in the left or right half of the alphabet. Here, it's in the left half. So, all I care about are the zeros. All the other letters certainly don't contribute an A. The zeros may or may not contribute an A. They may contribute other letters.

10:21 These ones? But rank only counts the prefix. How many A's are to the left of my position? So, these also don't matter. So, I count the A's in the front, so the result should be two, right? We can already see, but the data structure actually doesn't know. All it knows is there's a bunch of zeros in front of this, and certainly the ones don't contribute. So, I'm going to go left. Now, I also need to do the rank here on zeros to know which position I'm recursively looking at. Same as for access. So, here um this I don't know, what was it? Uh 1 2 3 4 5 6 7, so I'm at position seven here.

11:05 Um that's recursively what I'm looking at. I still want A's. A is going to be in the left child, so again look at the zeros. The ones at this level again don't contribute. And you recursively do this until eventually you find in the leaf your position, and then the number of A's to the left of that position is how many A's you have. And uh I think here uh the tiebreaking is not consistent to how I did it. The positions also start with index at one. So it there's a mismatch in how things are counted. If you look at the the details of the indices. But conceptually, you find the position that corresponds to your original position in the leaf. And the leaf is pure. It's the same letter. So that position is the rank with respect to that letter. Cool, huh? I like this data structure. Um you can also do select. Say we want to find A is probably the most interesting one.

12:10 The third A. Um then we start in the leaves for select. Because that's the only place where I have the A's bunched together. And then conceptually, what I need to find the position of the third A here is clear in the leaf is obvious. Just put this position three. Where is that A in the root? That's what I need to find. And now I'm doing the the same game in reverse. I know my parent. I know I am the left child of my parent. So I need to find the third zero in my parent. Now with A's it's always going to be the zero. In general, you'll find whatever is your child link. And here you find this position. Now this was the the fourth zero at the fourth element in [snorts] this case. So you need to find the fourth zero in the parent.

13:03 And again uh here you're counting inclusive and starting at one. Sorry for that. Uh so here what's that? Uh eight. So you go for the eight zero up here and there is your A. So I think conceptually is is a a very simple data structure. And there's really not much to it other than bit vectors.

13:30 Um Um we're a bit over time, so I'm going to mostly leave it at this. Uh you can because it's based on bit vectors, essentially throw a compressed bit vector on the data structure. And essentially this works. So That's that's all uh of the main idea that you need to represent the text in compressed form. Now compressed for the text is the zeroth order entropy of your of your text times the length. That's the space that you eventually get and some lower order term.

14:33 Now there's there's two things that are maybe non-obvious. First of all, we now have uh potentially a lot of bit vectors and they each bring their little lower term. So you need to make sure that the little lower terms don't dominate.

14:59 So you can improve the lower order term if you concatenate the bit vectors across a level. And you can still work out where you are because you recursively know how many you've skipped. Uh I'm I'm glossing over many details. Now the second part is I'm now storing a compressed bit vector where I'm putting together several bit vectors that may have different numbers of ones relative to their size. The The cute observation is that our compressed bit vector representation is entirely local. Each log in chunk is kind of compressed in isolation. If one chunk has a lot of ones, fine, then it's become it's compressed like that. If it has very few ones, it's going to be compressed like that. It's always this MIOI representation.

15:44 And if say the first half of the bit vector is all zeros and the second half is all ones, overall it looks balanced, but locally it's not, and the compressed space is actually adaptive to the local structure. So, that's the second observation that our our compressed representation And that's why you can do these two things together and still get uh compressed space for the overall text.