Video 6-2: Bitvectors

0:02 We'll get to the technical parts next time. I want to briefly say a few things in preparation so that then we can get started. A few practical implementation options on this slide. Focusing on C++ just to make the notation concise but there's kind of similar options exist in other languages. The easiest is you can represent each bit as a character or even an int and use a vector for that. There's vector bool as well. I'll come to that. We could have an array of bools. These are the fastest if you need fast read and write access to individual bits. But what they do under the hood is use a whole byte for each bit. The reason for that is that is the atomic unit of addresses maybe even word boundaries but um this is a compromise. So these are faster to access than addressing bits individually. That's why standard libraries make the usual trade-off to be fast not space-efficient.

1:11 There is a a specific override for vector of This should really be bool. I'm sorry. For vector bool that may use one bit per operation is this You know these things go. The C++ specification says there's a special case for vector of bool has a few weaker properties. It's in a way not a proper container class. People um users of C++ are even kind of complaining that this exists because it breaks some correctness properties because it doesn't um behave exactly as the other containers. But fine. um When I tried it out it actually used the same space as the above. So, the implementation may use a single bit for this, but you can't rely on it. And it's also not clear how it's um internally represented. So, you'll see that it's useless for what we are trying to do in the end. You have to do something uh more low-level. Um one option for that is to essentially do the bit packing yourself.

2:24 We use this uint64. It's just an unsigned integer with 64 bits. That's the most convenient base type that you can use in C++ for this. Uh it's a number with 64 bits or 8 bytes, and um we use these bits by explicitly setting and them with bit masks. Uh then for for reading out, you can say uh and that with a certain bit mask and shift it. And for writing, you can do the opposite with XOR uh and a bit mask. Um all of this is is not too hard. If you're If you're interested, maybe we can uh smuggle in some exercise problems on this. Uh there's also um if you want to really use this in practice, succinct data structures, there's a specific library. It's not part of the C++ standard. Uh the SDSL light library. That's kind of the um de facto standard, but it's still um in development. It's very far away from the robustness of a C++ standard library, but that has these many things that we discussed here built in.

3:36 What all of these representation of bit vectors don't give you from the start is what we needed for this toy example, namely rank or and select queries. Rank is uh the clear um the big brother or the little brother of select. All right, select is give me the ith I think I have uh an example here. So, if you have a bit vector, we define these two operations, rank and select. And let me be a bit picky about um the zero-based and one-based indexing and so on. Uh for the lecture here, I hope I'm consistent. I want rank to be like uh the bit vector is zero-based in the addressing as vectors tend to do. Um rank for for a for a certain position then is the number of ones to the left of that position. Right? So, I'm I'm excluding position I. You could ask, "What's the number of one bits in the first I bits?"

4:33 Which is then position zero up to including I minus one. Uh which means I can also also ask this for n for the entire bit string. I can ask it for zero, but the answer will always be zero. Maybe uh not so useful, but fine. Uh it's not forbidden. And select um is the opposite. It gives me the first index where the rank is above a certain threshold. So, it gives me the rth one in the bit vector. And here uh I'm counting from one, which you could say is a bit inconsistent, but this turns out to be a bit more natural, I think. Uh so, that's why we have this um Well, start starts from one. Uh up until the number of ones that the bit vector contains. Is a definition.

5:28 Um yeah, note that the rank is essentially a prefix sum. But for select, this is not so clear. Uh for rank, you could also ask, "What's the number of zeros in a prefix?" But that's symmetric. I can take the length of the prefix and subtract the rank for one. Right? Counting ones and zeros, if that's the only two options, clearly I can do one and deduct the number from the other for the other. For select, that's not the case. If I want um if I want to select the ith one or the ith zero, I need to do both separately. We'll here usually um assume that we're selecting the ith one. But of course, all we do is symmetrically possible for the zero, so you could also do the other one, but it needs kind of you need both separately. Right? But whereas for rank, this is sufficient to do it for once. You can subtract to get the zeros.

6:23 Okay, let's do some examples. Um rank of 12. Well, here's position 12. Um I'm counting the number of ones to the left of this. 1 2 3 4. That's this. Same for the 13. There's a one here for the 13. But I'm counting up until that position excluded, so it's still four. Okay. Um finding the third one. 1 2 3 is this position 10. So that's what I return.

6:59 Um which means yeah, if I take rank of the position I get returned from select, it's not exactly uh inverse functions with this definition. Uh yeah. And the fourth one gives me position 11. Good.

7:20 Uh note that I can reconstruct the individual bits if I want from rank. So I don't need a specific operation to read a bit. If I can do rank, I can also uh solve that one. Uh not that reading a bit is not normally hard, but we'll see representations. Maybe it's um uh it just is one operation less to worry about. Okay. Uh let me finish with um um Right. The The goal to represent a bit vector is to use the n bits that we need for the bits themselves if we pack them into words. And just little o of n bits on top, so a succinct data structure for bit vectors that supports rank and select. That will be the goal and we'll leave that for next week. Uh what I want to finish with is an overview, apart from this toy example I've shown you before, um a few other areas where bit vectors can be used. And if you see this for the first time, bit vectors with rank and select, maybe it sounds like a a really strange problem or a strange data structure.

8:23 Um there's a few examples here that I want to briefly discuss that show that this is really the bread and butter data structure for space-efficient data structures. Uh one is what we've already seen. If I want to store a set of integers, I can represent that set as the um the bit vector with uh an entry for each element in the universe and there's a one if the element is in the set. Um then I can solve predecessor queries on that set using rank and select. Uh I hope I got the indices right here. Want to double-check. Um in that representation on sets, you can very efficiently do intersection and union, et cetera. At least when um efficient means linear in the size of the universe. Uh depends what the parameters are like. But this is indeed uh something people use in databases. Roaring bitmaps is something I've um I've only read in that context.

9:22 Uh if you have some some table with attributes, then uh you can keep a bit vector for every object. Does this have this attribute, yes or no? And you can uh with these bitmaps, you can efficiently do intersection queries, find all objects that have certain properties combined. Uh another cute one is um encoding a set of integers or a sequence of integers when you do that in unary. Now, this sounds inefficient, but if you have many many such numbers and all of them small, it may be efficient. And with rank and select, you can get the prefix sums. So, if you need to store a set of numbers and you need to be you need to quickly find the prefix sum, then that is uh an option to represent them like this. So, a certain number of ones, then a zero to separate them. Uh with that convention, I need select zero here, but fine.

10:15 Um the last one is uh kind of in in preparation. If I have a uh an array that has mostly zero entries, wouldn't it be lovely not to store all those zeros? And you can do that with a bit vector where you separate the non-zero values and store them compactly from well, the positions that they actually occupy. And you could of course store the positions separately, but then access is a bit slow. If you use a bit vector that has a one whenever the value is non-zero and a zero otherwise, then um with in total n plus n bits plus the space you need for the values, you can still simulate reading the original array with checking this one bit and maybe one rank operation. And you get uh the space usage of n plus k times whatever the size here is, say log u, plus little o of n bits, which may be much much less than n times log u.

11:24 Whereas here, you need log u bits for each of these entries, even though most of them are zero. And specifically this last case, clearly we expect to see much fewer ones than zeros. That's something to keep in mind. Also the other operations here and the other applications have this property. We'll come back to that. For the first parts next week, we'll ignore that extra property.

11:54 Okay, so in short, let me close with that that bit vectors with rank and select can do a lot of cool things. Let's build them.