Video 6-5: Compressed Bitvectors

0:04 So, after having built bit vectors with rank and select support, we want to even compress the bit vector itself. So, so far, we've used the n bits for our bit vector B in plain, and then added little index data structures on top, where the goal was essentially to have something little over n that is insignificant compared to the bit vector itself if n becomes large enough. If we want to improve upon this even more, then clearly we have to store the bit vector itself in a different way. We can't keep it in a plain representation that uses n bits. There's no no uh change or no no improvement possible. I've motivated yesterday already that the the applications we've had, specifically um uh when when you represent a set using a characteristic vector, then you have as many ones as there elements in the sets, maybe much less than the total number of bits. Or if you represent a sum of integers so that you can do uh prefix sums using rank by encoding the number in unary, then you may have a lot more ones than zeros if the numbers aren't all small. And if we have an index for a sparse uh array, remember the the idea was to have an array of numbers, and many of the entries are zero or the many of the entries are some default value, either works, and you only represent the outliers, then again, we hopefully want to use this when there's few outliers.

1:33 All these cases give rise to a bit vector B, where the number of ones is far away from, say, n over 2. Uh for the presentation here, I'm always assuming the number of ones is smaller than half. You can reverse everything otherwise. >> [snorts] >> Then uh if that's the case, the number of different bit vectors, if you fix now the two parameters, the length of the bit vector, the number of bits, and also the number of bits that are set to one, then instead of all two to the end bit vectors, now I only have n choose m. So, it's uh kind of a restriction to a potentially small subspace. Note that if uh say m is n half, this isn't actually those that much smaller than uh This is fairly well approximated by n. Um If uh if n becomes large, there's of course some correcting term. It's it's less than n. It has to be less than n.

2:43 Uh but if n is large and you have roughly a half n ones, the overall space you can save is nothing. But if m is substantially smaller than n half, you could potentially save a lot. In the extreme case, clearly if m is zero, there's nothing to store. If m is one, log n bits suffice, and so on. So, this the number of of bits, I should say this is the number of different bit vectors. What I wrote here is clearly wrong. Uh What I meant is log of the number.

3:23 That's the space that we use or that we want to use. If there's that many different objects, succinct space means log of the number of different objects is the target. That's the information theoretic lower bound.

3:38 Um I wrote down this uh inequality here. I think that's is um useful to quickly justify because uh the the two values, I think there's an optical or visual similarity N choose M and N divided M. But these are very different quantities in principle. Uh there's there's two things you could do to this lower bound. So first of all, is it clear what the lower bound is talking about? This is if I restrict the number of ones in my bit vector to M out of N, I have N choose M possible ways to have a bit vector that looks like that. Then log of that number is if I fix N and M is the best worst case space I can use to represent such a bit vector. And I may need additional space for supporting operations. Now the second part, this this quantity is the truth, but it's a bit unwieldy to work with.

4:36 Because this can range from zero if M is zero all the way up to essentially um N as I claim here when M is N half. And there could be in between log N if M is one. And uh I guess and almost anything in between.

5:06 So let's um work with this quantity a little bit and see why we can upper bound it with this more useful quantity. Uh this is an inequality that's always true. Uh it's particularly interesting if M is little o of N. If M is is uh proportional to N for M uh if M is theta N, then this is a kind of not so meaningful quantity because of this linear extra term here. So we already know like you're you're saying an upper bound for the number of bits in a bit vector of length N is 1.4 times the length uh Sure. Uh We can do better if we know more more.

6:01 So, that's far from tight then. Okay, what can we do uh to simplify first of all this this original expression a bit? Uh you know binomial coefficients are essentially factorials, so log turns that into the difference of log factorials.

6:24 And you can use Stirling's approximation for representing uh either the factorial or log of the factorial directly. I think there's even uh The cheat sheet may have directly a formula for both if I remember correctly.

6:46 Always good to come back to the good old Okay, there's the formula for um factorial itself. Maybe I misremembered and I dreamed about the log of n factorial being written here there explicitly. But, if you look at that uh representation, if you take the log on the left, you have log of n factorial what we want, and if you take the log on the right, the main contribution will come from this n to the e to the power n. Log turns the little the long product into a sum, and all those terms are much much smaller than this a plus minus log n from this first factor. All right. Take that with us.

7:33 If you take log on both sides, uh there's a a logarithmic term from the first uh factor here, and the main term comes from n times log n divided e.

7:54 I have this error term of log n. Yeah, so if you insert that here, what you get is I'm still showing the cheat sheet.

8:09 I just wrote down what I said. Uh then we have n log n from this term. I'm splitting off the e. minus n log e And then we have minus from the second term m log m minus m log e Now the first thing to note is that here we have m log e, we have n minus m log e. And we have n log e and the terms exactly cancel. Uh I light away the logarithmic terms, so there's an overall error term of log n that I was missing. Now, what about the rest of these terms? Um I can rewrite them by uh factoring out n.

9:29 And by pulling the log n here inside of the logs as a as a ratio. So, I have m divided n, that's coming from this part. Now I have a minus m times log m, I turn that into plus m times log 1 over m. And I combine it with the first portion of these n log n's. I only to take m of those.

9:58 So you get this uh inverse fraction inside the log. And does anyone have uh good memories of such kind of functions? Uh does that ring a bell for you?

10:27 If I were to say p is m divided n, then clearly this other term is 1 minus p. And then this reads as p log 1 over p plus 1 minus p log 1 over 1 minus p, that's the entropy function. So you could write this as n times an empirical entropy where you say m over n and minus 1 over n, these are two probabilities of two outcomes. I don't know, maybe you also want to write h of p instead, depending on uh the notation you want to use.

11:11 So this first of all says this this worst-case space bound, when I pick exactly m ones, that's asymptotically not far away from uh picking a bit uh a a bit vector where every position is IID chosen to be a one with the probability of m divided n.

11:52 So, I um I mean the equality here to be a bit more precise should be the space for storing. And then exactly m out of one is roughly the same as IID bits with a Bernoulli distribution of the same probability. Now, in the second part, you're not guaranteed to have exactly m ones. But, law of large numbers says you're going to be very close to within m ones m plus minus square root n. And and so, the space the number of different bit vectors that qualify for either of the two is close enough that once you take the log the uh term the difference is just a a logarithmic term. This is significant if m is very tiny. But, for the mid-range of m being little o of n, but also little omega of one, um that's a reasonable approximation. So, we call this thing also the uh zeroth order empirical entropy.

13:20 If you treat the bit vector as a word, then uh over a binary alphabet, you count how many ones are there, that's m. Yeah, count how many zeros are there, M minus N. And the relative frequencies give you a distribution and the entropy of that thing is the empirical entropy of that. So, uh we've shown that this optimal space to use for a bit vector of this kind is very close to the space you would use optimally if the bits are chosen independently randomly.

13:50 Now, the next step we still haven't shown this upper bound here. And it turns out this is easier from this second representation. So, if we start with this N times this entropy let me unfold it, though. Uh I think this is cleaner to work with.

14:35 We split off this first term because uh the hope is that um if if M is relatively small maybe we can bound this this second term by something because uh N divided M minus N if M is real is real relatively small, this will be close to zero because you're taking log of almost one.

15:09 So, we start rewriting pulling out the first term again. And you will remember that's the term we had in the upper bound. Now I'm uh changing the base of the logarithm.

15:35 To formally apply this idea that what we have inside the log should be close to one. This is just splitting the fraction and I've um arbitrarily chosen to change the base of the log because this is upper bound for uh the natural log. You know, natural log looks like this and at one it has this upper tangent of 1 + X.

16:13 So, because the log is a concave function, it lies below any tangent. And here the tangent has exactly a slope one if you pick base e. Uh if you plot here ln x, that's particularly clean. That's the whole reason for changing base. So, we're upper bounding this by upper bounding the second term.

16:44 The divided ln 2 will give the 1.44 that you've seen before. And so, the upper bound, formally what we use is that ln of 1 + x is less than or equal to x. That's what's uh what's coming from this part. If you uh change change the parameters, I guess a cleaner way would be to say as is this.

17:09 And then you substitute. Uh so, here um what we get after the plus is just m divided n minus m And then clearly this cancels. Uh we're left with this linear term in m. And this turns out to be 1.4 roughly equal 1.4427. Okay. Uh I tried to show the calculation in a bit more detail because sometimes it's useful to um to manipulate these kind of terms a bit. So, long story short, if we want to represent a bit vector that has fewer ones than uh overall bits, in particular for the range where m is little o of n and not tiny. Uh then we can use we should be able to use like information theoretically the goal would be to use log of n choose m bits and that's upper bounded by this m times uh log of n divided m. So, for example, maybe it's instructive to insert some values for m. If m is square root n, then what we should be what should we expect? There's there's going to be some linear term and there's some log term.

18:45 Uh log of n divided square root uh up to constant factor is still So, we should use square root times log of square root. That's 1/2 log n.

19:07 Uh and uh plus this uh square root n plus this extra term. So, is a very potentially a very substantial saving possible. Instead of using n bits, we use almost just m bits, square root n here, but we have this log factor on top. And the factor 1/2 comes from the power.

19:34 Okay. Uh so far, so good. So, theoretically, in terms of the information contained in these bit bit vectors, there's a lot of scope for storing them with way fewer bits.

19:58 Um let me pull something forward. Because uh I want you to remember uh the second lower bound we worked with. Um can I get this easily copied somehow? Hm.

20:40 So, we we've used um the other lower bound before, namely the uh dynamic ran um rank query lower bound, to say we cannot have a dynamic bit vector that uses uh whatever space even and support constant time rank queries. That's fundamentally ruled out. And the best we could do was essentially this log n over log log n uh query times. Now, here we're talking about static bit vectors. There's no dynamic rank lower bound in the way. There was a second lower bound though, the predecessor lower bound. And this was a bit um I mean, it was very unwieldy if you uh give me the um the imprecision.

21:33 The point is that we can use rank and select to use to to compute predecessors. Why does this bound even apply? If you have um If we store set S as a subset of some universe, um Okay, let me let me convert to the notation in in the bound. But, we have to translate. U will be N in our bit vectors, and M will be the size of the set. Uh uh inconvenient that S here has two meanings, right? That's kind of bad.

22:32 Okay, the space should be some some calligraphic S or so. And that's the same here. I can answer. If I store this as a bit vector in the usual way as characteristic vector, so my B of I is one exactly when I is in the set.

23:06 Then clearly I can use rank and select to answer predecessor queries. Um on the set S I can ask for the predecessor of some number X.

23:26 is the the ones marking elements in the set. Now I ask about some value X. I'm going to do a rank query to count how many things are smaller.

23:37 And then I'm going to do a select query for this same same number. Uh subject to the plus minus ones to correct for the zero-based indices, this is what you have to do. And that gives you the predecessor of X in the set. So I can solve the predecessor problem using a static bit vector. That's the observation. And with the static bit vector um I mean if I encode the set as a characteristic vector. So that means this lower bound should apply to our bit vectors. Is that a problem? Have we somehow done something illegal already by um designing our succinct bit vectors before?

24:43 Let me write this like this is the universe. I have one bit for each possible element in the universe. And then if you go through the bound what this means, we have to compute this quantity A as log of the space that we used divided by n. And here s again should be some calligraphic s. I'm sorry for the stupid notation. Um and that's u divided n.

25:16 And so the the lowest lower bound comes from uh the green part in this range in this regime. So the lower lower bound says whatever this this green thing is is telling us. Log and then l is the size of the numbers. That's [clears throat] log u.

25:43 Log u minus log n divided by this a. And a I can insert that's log u over n. And now note that this just cancels out. This is log u minus log n. That's log u divided n. So all of this goes away. It becomes one and the whole thing says ah you need at least zero time. That's true. Okay, so there's no contradiction. For uncompressed bit vectors, the lower bound tells us nothing. It doesn't restrict our time. And that's good because we also proved that we somehow can do constant time. This was more of a sanity check. But if you look at our um compressed bit vectors, what we would want, that's what we just computed, is that this again this calligraphic space so m is say much less than one uh then my optimal space usage that I'm hoping for is roughly m times log n divided m. If you translate that to the uh, quantities we have here uh, n turns into turns into a u and m turns into an n.

27:11 It's uh, annoying. Maybe let me color this differently. So, this is in the world of of bit vectors. In the world of the predecessor lower bound we would have space s um, n times log u divided uh, n divided uh, u. Sorry. No, n. This is an m.

27:48 I can't apply this homomorphism. So, that's the space we'd like to have. That means our little a turns into log of log of the space divided n. That cancels this log, but it's log log u over n left.

28:08 And so, if you look at this term we don't get this cancellation. We have log u minus log n, same as before, but now we divide by this much much smaller term.

28:37 So, we're basically stuck. Look that uh, the the denominator here is just a log log log, so triple log that we subtract. This does nothing. So, you can ignore this. Um, leading order term, it's log of the numerator and that's log of U over N. So, we get log log U divided N. Which is famously not constant, right? If my Um, again in the other notation, if my N is much smaller than U, that remains essentially log log U. Not surprising, that's what the predecessor lower bound gave us and that's how Wi-Fast tries also worked. So, we run into a problem here. If we wanted to use this optimal space that we get from information theoretic arguments, we run into the predecessor lower bound that tells us don't even try to get constant query time. Now, we have two options. Either we say, "Ah, tough luck. Let's do something slower and keep the optimal space, but make queries a bit slower."

29:41 Um, I'll show you a uh heuristic version for that. Um, that's one one result I want to show. The other option is maybe we cannot use this in the full regime for all values of M, but there is some intermediate range, uh maybe uh let me call it slightly compressed.

30:10 Uh, I think this is uh this is actually a very bad term. It's fully compressed, but for a narrow range of M. Uh, let's say the large-ish regime for M.

30:32 Uh, and it will be fairly narrow. M can be between uh little of N, but it should also be little omega of n divided log n.

30:48 And you may object this is a ridiculous narrow regime. Uh but it turns out in this case the predecessor lower bound is still just telling you constant time is possible.

31:03 And uh so there's some hope to do that. This looks like a a narrow slither for these values of m that is totally insignificant, but I don't think it's true because many times you have precisely this use case. You want to represent something as part of a bigger succinct data structure. The leading order term is of order n and you can add a bit vector for free in terms of the lower order term a little o lie that everything in little o of n is not costing us anything. Asymptotically true. Uh then these compressed bit vectors are indeed very useful. Okay, with that bit of um motivation let me show you what we can do.

31:53 Uh the construction will not surface any balance that the construction works for any m. The trick will be maybe you can pay attention to where this uh kind of happens. Um I want you to remember or recall uh what what components we had to store for the bit vector index.

32:26 The bit vector with rank and select consisted of several components. Um there indices for the mini level. And there were indices for the micro level.

32:52 What I mean by indices is some uh rank values and certain uh for some of the dense blocks, the positions of the ones, all these things. Um but all of these were um fairly small, so they were in size with the worst bound um log n square root.

33:19 So, in a way, these are all fairly small compared to n, at least. Uh then we also had the um exhaustive lookup table. This was even smaller, right? This was uh n to the 1 minus epsilon for some constant epsilon that you can choose. Uh and on top of that, we also need the bit vector. That's where the dominant contribution came from.

33:57 We used the bit vector in essentially just one place during queries, namely to get log n bits to then have a lookup index in our table.

34:40 >> So, how about we apply some compression tricks to store the bit vector with fewer bits in any way we uh think is is fashionable or is is uh conducive to the task. As long as I can still get access to consecutive log n bits in constant time. As long as that is true, all the rest of the construction can stay unchanged. And I'm getting rid of the most significant terms for the space.

35:09 So, let's try that. Let's try to replace only that part. Mhm. And let me first share kind of a simple idea. Um conceptually previously we've stored this uh this vector as one long uh array. We could have just stored it as chunks of half log n little L bits each.

36:07 So, you could imagine you store this as chunks of half log n bits each. And then a constant number of chunks answers you these queries. In fact, for our lookup tables it was precisely one chunk each, but you uh doesn't make a difference in terms of constant factors at least. So, we could encode the chunks with some clever codes that represents them represents the same information with less bits. Of course, that's not generally possible, but we know our bit vector is sparse. It has few ones.

36:56 So, one option would be to store a pair for each for each of these chunk each of these chunks chunk I I store with MI and OI a pair where MI is the number of ones in the chunk.

37:23 And OI is some offset among all the bit vectors that have a precisely M1 ones and length L. Now, the trick will be these MI are very small. MI is the number of ones that can be at most L, so MIT takes just log L bits.

38:14 How much space does the OI take? Well, log of that thing. Which is what we computed before. Now, if if worried about how to get this offset, think of any possible There's some bijection if you can't think of how to compute that efficiently, it turns out you don't need to. We'll chuck it all in lookup table. But there is a way to bijectively map all the bit strings with a certain number of one bits to the first that many integers by simply going through them in some canonical order. And you could even say uh um let me let me do this maybe uh on on a small example. If um L is five and my M I is two.

39:06 How many bit strings are there that have two ones out of five? Well, I can do the last two. Then I can start to sign some somewhat calendar shift shift the first one to the left until I can no longer do that. That's the first bunch. Then maybe I move this the last one here I kept in place and I move it one position further. So you can sort of systematically do that. I hope you see where you hope you agree.

39:40 Now um I shift this one more position. Sorry, I'm getting confused. Then 10100 and 11000. It should be all, right? And so I just assign those numbers 0 1 2 and so on.

40:11 Uh yeah, 10 in total sounds right. I was worried when it ended with an odd number, but I started at zero. So there's some way to map the bit vectors of certain length to integers. Um if nothing else, you could just write this down and make it um a written-down table that maps one to the other again. And this is indeed what we'll do. Uh for for a more general case.

40:37 Uh how many how many bits does this need? Well, precisely log choose m i. And we know that this is from our calculation before is roughly m i times log l divided m i. Maybe you can further upper bound it. The point is this scales with m i. If m i is small for most of these bit vectors, then also the space for the pair that I represent is smaller than l. And it's precisely the same kind of calculation. If you want this l over m i is kind of a density, how many ones do you have on average? And the m i's, if you sum this over all the chunks, they'll sum to the total number of ones. So the space for this is essentially the optimal space.

41:26 This you would have to um do a a calculation and use Jensen's inequality, but uh let me shortcut here. So this simple encoding is good enough is optimal asymptotically. So I could represent all bit vectors in compressed space, and I still get my constant rank and select queries. Great. Haven't I now certainly broken the predecessor lower bound? Does anyone see why not?

42:21 There's no contradiction because I've compressed this part to be now for a very small m this is now tiny. I cannot compress the other other parts. And if my m is really small, say this square root m square root n then these parts dominate this this part really dominates. And then again I'm in the regime that the predecessor lower bound says, "Ah, you're using so much space. I'm okay." Like no contradiction. So this overall this scheme works for any m but it's only a succinct representation if m is in this ridiculous range that I sketched earlier.

43:02 In this range the above is succinct. If m is smaller than n over log n roughly then the lower order term dominates and is not wrong but no longer a space optimal representation. So basically with that we've shown this this theorem. If you have a bit vector that has m bits then by simply encoding the chunks a little bit more clever you have the leading order term reduced to this optimal term but you keep the same redundancy and so this one dominates if m is too small.

43:53 But you can still use it and you get the query racing constant time. That part is not not a lie. I glossed over a bit how to do the queries with this weird representation.

44:04 And let me um what we need again from the bit vector representation is a way to get log in consecutive bits of the original bit vector to query the look up table. All right, this is the crucial observation.

44:22 How do we get that with this weirdo representation though? Uh Take any code that represents some bit strings of size L with whatever you really like. I mean, I'm going to say some uh code words. I think they need to be bounded in size uh some some reasonable length, otherwise it will be too slow. But in principle, the idea works for anything. Um a bijective mapping or I don't I don't care. Uh injective. Invertible is important.

45:15 So, you take your original bit vector, you break it into these micro blocks. Each of the micro blocks you convert with this code to C of B1, C of B2 Now, I should draw this differently because hopefully these are shorter, right? Um >> So, if you have a way to get from your code word for the mini for the micro block, you can use that as an index in the invert table in the inversion table that has every code word listed as an index and its plain bit representation. That's all this all code words that you could think of in one big table. And then the inverse of that.

46:57 Uh then you can decode these codes no matter what they look like in constant time and get back your bits that you can then put into a lookup table. Uh what this code may what makes this code convenient is that you can you somehow need to find your code word for the block. And if these are of different lengths, that's in principle not so easy. Right? They they could be shorter and longer code words if it's a a good compression. Um so this specific encoding is chosen so that all the M eyes are of the same length, so you can represent those in a normal vector normal bit uh array. And once you know the L eyes uh and their prefix sums, you know where to read the offset. And that part for general code needs a bit of more thought. Uh that's precisely where you would use such a bit vector to be honest, but uh we can't use it in its own construction.

48:05 That was the last missing part, I think, for this for this result.