Video 6-3: Rank-Index for Succinct Bitvectors

0:01 up. In the next section, we'll look at how to support rank. And in all of what follows, you should think of this as an index. I'm storing this bit vector in plane. And on top of that, I'm adding some support data structures to support this rank operation fast. Uh but before we get there, let's look at what we can do without thinking too hard or doing anything complicated. Well, the stupid thing I can always um if I ask about the first I positions, I can scan them and sum up the number of ones, right? Of course, in in worst case, that's the entire bit vector. So, linear time. I guess you can try to speed it up with word size operations. So, maybe you can do n divided w if you're on a w bit word ram. But let's not got in let's not get into this here. We can do much better with other tricks.

0:54 Um another idea um I think is worth dropping this this name at least um in a data structures class is using a segment tree. Uh again this I don't want to officially do in detail but let me roughly sketch what this works like. You have this array. The segment tree in general is for doing uh sums of arbitrary numbers. We can do um other operations but let's think of it for the bit vector specifically for rank um let's let's say the the length of the bit vector is a power of two okay then it's cleaner to describe um on top of this so this is individual positions on top of every pair I imagine I have one node So this is always for two positions and this stores the subset sum of of these two positions. So for rank it's just the number of ones. Okay, I do this all the way through and then on the next level I'm again combining two of the previous level into one. So it's like a a merge tree in merge sort. That's the same visual structure.

2:23 Now it looks like this tree is always spanning the entire width, but this is really just a single number. So in reality, it's shrinking geometrically, which also means the total number. So of course then now, right, I recurse until at the top I have one number that gives me just the entire sum of the array.

2:49 So it clearly has logarithmic height log base 2 of n height. Okay. Um how can I use this to find the rank? Well any any position that I might query for will be the sum of log num uh nodes in this tree because there's always going to be some power of two that's smaller. So say uh here's let's draw one more layer that stops just before the eye. So I might combine this one and then on the layers below there's going to be some other one that I can combine with this. And then maybe this is all I need. Okay. And you can even compute which things you have to sum up by looking at the binary representation of this index I that tells you precisely at what levels you have to sum up. the corresponding values but uh we don't need to get into the details. The point is with such a tree you can support these um these rank queries as a general as a special case of summing up ranges of the array. The same trick works if you have some range from i to j and you want the sum of any numbers also works the same way. Then you have this on two sides. So two times login and uh this is even dynamic. You can even change the array and update in login time go through the layers above it. You're only going to update counts that are on your leaf to root path. So this is all good but um it has its limits. First of all it needs a linear number of extra numbers on top of the local of the bit vector at the bottom.

4:37 Right? Uh you have n half on this level. You sum it up n half numbers here. N /4 numbers here. N /8. And you sum this up until one. And if you add this up, it'll be precisely n minus one extra numbers. Each of them needs well you can maybe save a few bits at the lower levels because they will be short but the upper half needs maybe you can do slightly better than but than n login but it won't be much uh it won't be linear for sure. So each of them say if you store them plainly uses login bits. So you use n login log n bits of space and the query time is also not quite as good as we'll see if we can get it. Uh it's logarithmic in the length of the bit vector. What else can we do? Like note that this is kind of overly powerful because it allows dynamic changes updates to the array and uh we're happy if this data structure is completely static.

5:46 Uh we'll also come back later to why um as you can already see it here. If if we can support these updates to the array that's essentially maintaining a dynamic set of integers and we can do rank queries. So dynamic set of integers and rank queries together. Remember that's Fredman Sax's lower bounds. So much faster than login query and update time is not possible. So we're already close to this and kind of reinvented a search tree here. Okay. So this this this reaches limits. You can do it a little bit better in terms of the extra space at least if you don't apply this segmentry for the entire array but you first cover it with blocks of say login bits. Then you treat these login bits as one block and then build the segment tree above that part um the same way. Then you're applying this this n login bit data structure on something that's now using a smaller n and so you're getting this down to linear number of bits.

7:03 Um that's better. And the the login block size here is chosen so that the time you spend in the tree and the time you spend to sum up your block that you still have to deal with, right? Um I'm now essentially breaking this array into chunks. If I want to find up to this position I, there's going to be a a prefix that is covered by entire blocks and that I can get from the from the range tree that's on top.

7:39 segment tree. Sorry. So I can get up to this position from the segment tree but then I still have to scan this part uh kind of bit by bit and then if you use login we get uh overall still login query time and we can at least reduce the space a little bit.

8:00 You could try to squeeze this a little bit further if you make the blocks a tiny bit bigger so that this becomes little low of n but you're stuck with the creby time being logarithmic and we already know because it's dynamic it cannot be made much better. It would contradict Redman sax lower bound. So how do we get to something that's even close to what we advertised? um is neither succinct as we stated it and it's not constant time for sure.

8:43 Well, the trick is to do um a different data structure that is much more expensive to update if you were to change things but gives us more power at the quer at query time. uh and so basically all all we can do is look at a constant number of uh precomputed values if we want constant time if you frame it from this perspective what can you do in constant time I can read a constant number of uh memory cells and do some computation and then I have to be done so I I kind of have to premputee almost all answers now I can't store all answers that we don't have much we don't have enough space for that so instead a standard trick in succinct data structures is to try to just break your input into large enough blocks so that the space is okay and see if you can puzzle together your answers from that.

9:37 Uh since this is the first time we do it um I'm just going to show you the results and uh try to do it in in full detail. First of all, we break our bit vector B into mini arrays. That's the green ones here of a judiciously chosen size. Usually you find out what the good size is by working out the analysis and then you check in in retrospect what is a good number. Um let let's just call it capital L and maybe ignore for now how long it really is. uh clearly the number of such mini arrays It's going to be n / l and then I have to round up. We'll almost always ignore the rounding because it's a small error term. We'll choose it so that this is uh is irrelevant. So let me make this maybe like this. That's the number of mini arrays. So looking at the solution, if if capital L is log squared, how much can I store for each of these mini arrays?

10:55 If I want the total space to be little O of N, this times this number of bits per mini block has to be little O of N. So as long as I store little of log uh squared n bits I'm okay. In particular I can store log bits for each mini array.

11:31 Well here we don't have to be particularly strict. we can say big O of login bits without violating our space bound. And so let's do that for each um mini array. Maybe let's pick this one. I I'll store how many ones are to the left of it. And for this one, I'm going to sum up all the entire part to the left. So the entire two mini arrays here. And for this one as well. So these are large numbers potentially. And also note that if you were to try to make this dynamic. If I change a one here to zero or vice versa, I would have to update all those numbers, they all change. So this is not going to be dynamic. But that's fine. Uh we want it static. Okay. So we store these numbers. So I can now answer rank queries um at the boundaries of these mini arrays already from what I've computed.

12:26 And then there's a a log squared n sized mini array left that I have to somehow deal with. Now I don't have time to just read it and uh sum up the bits. That's too slow. So let's try to recursively apply the same trick. Okay. Okay, so we divide this further um and uh break the mini arrays into little microarrays again of a judiciously chosen length little L.

13:01 Now note that the number of these microarrays is now already much larger. in particular n divided log n. So if I were to try to apply the same trick as for the green ones, just store how many ones are to the left of this blue part, I'll need login bits each and that's already linear number of bits. That's too much. I cannot store the green numbers. Instead, each of these blue little numbers stores how many ones are to the left of my microarray, but within my mini array. So, it's mini array local counts. Okay.

13:48 Now, this helps because the mini arrays are already mini. They're tiny. uh the picture is I think I tried to make the picture to scale but because n is still fairly small it doesn't give the proper proportions uh n is exponentially larger than log squared I guess in some right asmtoically so maybe the more typical picture would be a really really long bit vector broken into already rather tiny pieces and so the the little blue ones are even tiny here.

14:26 But the jump from black to green is much bigger than from green to blue. Well, why does this help uh to store these blue numbers relative to the green thing? Well, the numbers can't be very big. In the worst case, the entire green mini array is full of ones. But how many can there be? At most, capital L, right?

14:52 So I guess I should write this in green. The number of ones in a mini array cannot be more than capital L. So I need log of capital L bits to represent such a number because capital L is log squared. Log of that is 2 * log log. And um multiplying n / login * log login log n is still little of n even though the little o of n's become bigger and bigger somehow. uh we'll see this pattern continue and escalate further but for now um we need so many bits each uh we have n divided little l such microarrays each needs log capital l bits if you multiply that out it's that lovely number and so it's little o of n bits now at this point you may have two questions number one are we done now or do we have to further recurse and second note that I somehow chose 1/2 log n here the reasoning from here I mean there's this factor four here if I chose just login which is somehow more natural this would turn into an no it would be better right it would turn into a two why did I not choose login there's probably going to be a reason for that Um the answer to the first question that you all had I think do we need to recurse further is no. The cleverness of um of all of these schemes is to stop at a at a reasonable level and something a good deal smaller than login bits turns out to be a reasonable level and we'll have to work out why.

16:56 But first, let's puzzle together how we answer queries from what we have. Uh let's do it just by example. If I want to compute the rank of this position, well, there's going to be some entirely contained mini arrays to the left of this position. For these, I know the number. So, let's add it up. That's part of the rank. That's all the ones to the left of this position. Then I'm also going to find entire microarrays that are contained within this mini array. For these, I also have the number precomputed. So I add these up and what's left is local to this little microarray that I'm that my query falls inside. Again, in the picture, this is just four bits. So I might as well just read them. But if you think of larger n, this is still a growing um size. It's still log n bits roughly login half bits. If I can somehow figure out how many bits are one to the left of my position within the microarray, I have the final result, right? I have all the pos all the ones in this range plus all the ones in in this range plus the ones in this range. That's the total number of ones left of my red line. How do I get these purple ones? I have to somehow get these. And again, the goal is constant time. So, we need a trick. Uh, one option is to just scan that little microwave, but that's not constant time.

18:34 Another operation is to say, ha, this is an operation that most CPUs have baked in. And if you think about hardware design, counting the number of one bits in a in a word is a very simple operation. It needs a bit of circuitry to add to convert um the set bits to a number etc. But it's very doable compared compare that to the circuit for multiplication of say two floatingoint numbers or so. This is kind of an easy operation. So indeed most operations have this built-in as a as a pop count instruction. If you're wondering how can I apply this if I only want a prefix of the word counted then you uh take the bitwise and of the word um that contains your your microarray with a bit mask that zeros out this suffix and then you do pop count. So this is indeed that's the practical solution in this case and that's going to be the fastest.

19:36 However, I'm going to show you something uh that is more general and applies to all sorts of operations. Um sometimes feels it's almost applicable limitless, but it's not true. You need some some operations uh have some uh properties of the query that you're answering. But this is always always on the examples is always very clear whether it works. Maybe the third option is to use a big lookup table and premp compute essentially all the answers and we'll have to do the math why that should be possible or why that should work out. Uh the last two options both give you a constant time solution. The green and the blue part is just reading out some premputed number where the index that you have to access is easy to compute from this this rank uh index basically divided by capital L and round up or something like that. Okay. Is clear how the operation how the rank uh query works? If you can solve somehow this purple part in the microarrays.

21:00 So the uh technique that we use in this purple part exhaustive tabulation is more general than specifically just the succinct data structures. Um, so in the general sense it combines two ideas. Well, one we're working on the word RAM. So we assume we can do all sorts of bitwise tricks. And one specific trick we can do is that we can use integers and use them as an index in an array indirect addressing. And of course uh our bit sequences are also just numbers encoded in binary if we want to treat them like that. In particular, we can think of these little microarrays as encoding one number between zero and two to their length. So we can use the microarrays themselves as an index in an array. And the second insight is that we don't have so many different microarrays because they're so short. they tend to fall into um a certain number of of different micro subpros and we can just premp compute those all and store them.

22:11 Uh so we do that in one big lookup table where the micro array itself is the index. I need on top of that also the operations. So for our specific case let's look at that. Um and here it becomes important how exactly we choose the uh length of these micro blocks. Uh what we build is this. You should imagine this as a huge lookup table for a slightly bigger n. I've drawn it here for the same size as before with four bits. So there's 16 different microarrays and that is all they can possibly ever look like. Even though already in our example uh this looks like it's precisely 16 uh which is uh a bit unfortunate. I think if I had made this twice as big it would be hard to read. So there's a compromise but you should remember the scaling is such that uh the number of microarrays that we break our large bit vector into is n divided log n roughly n divided little l and that's almost n. I mean we divide by n but that's not that much. It's still a very large number but then the number of different microarrays is way smaller. So they all tend to look kind of the same.

23:37 How much space do we need for this table? Well, there's 2 to the L rows. Now for each row, I have to store uh the different query answers. I'm mentioned that. So for each possible way the microarray can look like I'm going to write down up front what all the answers to the rank queries look like and these are as many as the uh microarray is long that's why L is the number of row number of columns yeah nobody can read that number of columns as many as I can ask rank queries for every possible position and what I have to write down in each cell is a number but it's a small number because it can only be a number up to little L. So with log L bits I can write that down. And so if you compute for our choice of L what that turns out to be the 2 to the L is the much most is the most important factor but that's a square root N because I have this 1/2 log N and so the rest is some poly logarithmic factors but all of this combined is still indeed much smaller than N. This little O of N is indeed a small little O of N. it's polomially away from the others.

25:06 That's the trick why this works. And in general, the number of microarrays that we use is much bigger than the number of different microarrays.

25:15 So even though it could happen that some of these rows are not needed in our application, it's important that we include all rows because we want to jump to a specific position using this bit pattern as an as an index. I've written here two columns for the microarray and for the index. But note that these are kind of the same, right? This is just the number written in binary.

25:39 So we can uh um save a lot of space by encoding all possible microarrays but each only once and we'll have many occurrences of the same sub problem in our in our actual input.

25:57 And now the uh purple axis is very simple. If I have my microarray type, so the number of bits, that's just the chunk of of my bit vector that's this microarray occupies, I use that to get the proper row. Um, maybe I should do the example from before. What do we have? Uh, okay, it's indeed seven 011.

26:27 So we use the microarray type to get the row and the local offset as the column. Now I forget I think it was rank three. And so the local answer was two.

26:47 Uh okay, whatever. I mean you can look it up. Okay. And then we just return the appropriate value. Uh well, this was matching the previous example. Um hopefully so here locally we have 0 1 2 3 and uh so I'm I'm querying three but it's the ones to the left of that position thanks to my intuitive convention.

27:46 So also here right um the rank three says 0 1 2 3 sum up these two these three bits that have two ones so it's a two okay uh now how to compute that table I didn't put on the slides but it's kind of easy I guess you just iterate over all possible microarrays and you just compute those ranks even if you do that uh with scanning each time because the number of rows is so small compared to the other work we do. This is a a lower order term. Um now we may need to talk about this type. You somehow have to write down what each microarray looks like. But then again, we don't have to really because that's the original bit vector unchanged. All we need to do is uh pick out the right starting position and then read the next little l bits from our original bit vector and use that as index into the table. So there's nothing really need needed to get the type. Uh here it's just reading some bits from B. Okay.

29:03 Uh with that we get overall this result. Um I we haven't formally proven things but I think the construction on the example is is kind of indicative enough. Uh if we're given a bit vector then in linear time all of the substructures you can compute in a scan over the bit vector we can compute an index data structure which means it uses access to the original bit vector but adds little helper data structures on top. And the size of the helper data structures is big O of N log log N divided log N which is a little low of N term. That many uh bits of space are needed to support rank queries and the running time is constant once the uh index is computed.

29:53 Now note that the index uses B at query time which is also necessary because we store not even a single bit for each position. we can't really distinguish all possible bit vectors.

30:07 Uh but you can turn this into a positive thing. You could say um this data structure can even be applied when we don't have this bit vector explicitly written down at some point point but rather when I can ask you with a given position can I get the next login bits from that start position in your bit vector if you're able to compute those for me on the fly I'm also fine the data structure doesn't care it needs the bit vector initially for the pre-processing And then at query time, everything is precomputed for the blue and the green green and blue parts. And for the purple parts, I need to read these uh little l many bits in the bit vector. If you have that stored explicitly or pre or recomputed somehow, that's okay for me.

31:02 Uh sometimes this is convenient. Um, in particular, I think uh for my original motivational example, let me briefly go back to this because it's a rather cute instance of this long way ago. This was this one um random access into a Huffman coded text. So the idea again was we have a text and we somehow represent it using a Huffman code or some other uh variable length code. Uh to read a specific position in the text, I need to know the starting position of such a uh code word.

31:42 Now um let me just copy this part and then we can go back. Come on. Okay. So we would like to have uh a way to jump to the right position.

32:07 Now the operation that we'll need is select not rank and we'll come to select after the break. But just to illustrate why it's convenient to have this this index axis, uh imagine I gave you um a second bit vector that says one whenever I start a new code word and zero otherwise 1 1 0 1 1 0 1 1 0 1 0 0 If I can select the arth one in this bit vector, I know the position where the arth character starts.

33:08 It has to be as long as this capital C the coded text. If I in s select the arth position that gives me the arth character of the text. So that's where the code word starts and I can decode the Huffman code from there. Right now you can store this on top of the coded text C. You double the space plus the little O of N. Okay, maybe it's not that bad, but you can do better. Um, note that we can recomputee this S from C and the Huffman code. If I have some position in C and I know where some code word started, I can I can locally re uh construct this this S. So in a way I can avoid storing s explicitly and always just recomputee it locally. Uh I need to leave there's a bit of cheating here because I need to know some starting position. So uh you need um some bits of of s maybe explicit so that you know where to start and and re uh compute the rest of s. Um, but we only need we only need this for relatively few positions. So maybe you can get away with the low of end space here.

34:45 So here even on demand. Uh let me finish with a little historical remark on this exhaustive tabulation technique. Uh if you check in the literature, it's often called the four Russians trick, which is a a horrible name. Uh it's from a paper. I'll show you the context briefly. Um the original publication is in Russian which I can't read which I cannot read. Um there's an English translation in official where you can check. Um it's fairly fairly tur so I think it's it's kind of fair that people uh took a while to attribute it to the right people etc. Uh but somehow I think it's Americans that coined this this horrible term. It's rather othering right? Okay, we don't if it was Americans, we would cite them by name and if it's Russians, we just say four Russians like okay. So, uh exhaustive tabulation says what it really does is a much better name. But be prepared that sometimes you see this for Russians name and if you do, you should recognize that it's the same thing. That's what the slide is for.

36:12 In the original um application again um we don't need to go into details was just for boolean matrix multiplication. If you have two boolean matrices that you want to multiply then you can uh apply this same trick by breaking them into small micro matrices.

36:38 And matrix multiplication has this cute property that if you um uh the result then also consists of micro matrices and a micro matrix somewhere in the middle consists of multiplying some row uh sorry the other way around some column of one matrix of micro matrices with a row of micro matrices and each of this is the result really is the sum of multiplying this micro matrix and this microme matrix plus this micromeatrix times this micromatrix. So you can decompose everything to be uh in terms of operations on micro matrices and if you choose your L small enough for example a quarter square root login because you're squaring uh then there's only n square different products again it's important here that we have boolean matrices okay there's only zeros and ones then there's only so many different little products and you can premputee them And uh then um instead of multiplying these these two boolean matrices in overall cubic time, you can do it in slightly subcubic time.

38:00 Maybe uh n cubed divided by l cubed or otherwise known as n cub divided by log to the 1.5. Uh the details are not so important here. Um but I think uh kind of kind of nice to know the historical context. It's the very same trick. Uh you go to a size where the number of different instances of that size is much smaller than the number of times you use it. And so you have a speed up. Note that this has nothing to do with space efficiency in this case. It's just about the running time. But the same trick gives you a a slight improvement in running time. Um in our case we use it for saving space.

38:51 If you read very carefully the original trick is actually uh uh you can actually refine this a little bit. Um it turns out for the matrix problem going regular in the two matrices make breaking them into squares is not optimal. Instead you want uh one matrix to be divided into vertical and the other into horizontal strips. If you think about how we do matrix multiplication, this is maybe natural. So the the proper best running time you can get from this technique is slightly better. But okay, a square root login factor