Video 6-1: Computing over Compressed Data

0:02 In the next unit of advanced data structures, we look at space efficient data structures and specifically succinct data structures, which are I'll tell you in a second what this um stands for and we'll finally come to the pictures in the background. Um The first one today and the second maybe a bit later as well. Um We'll start with some basics and then um I want briefly mention a few other interesting uh types of objects that you may want to store. Let me start with maybe uh just a a toy example uh to motivate a bit what the types of results that we're after in this area are like. And then uh start building towards the first such such uh building block.

0:54 First of all, uh usually and until now in this module as well, we haven't cared so much about the space usage. The primary concern was that it's fast and then about space you start caring if you run out of space. Um so historically people also in in algorithms didn't care about space as much. Um when they cared about space was when the deliberate goal was to compress data so that you could store it with less um well, the in less space. Uh but it was primarily primarily thought as a way to archive data or maybe transmit it over some network or so. Um More and more though, um the realization uh is is coming that you can do a bit more. Uh and the kind of overarching goal with this with this name computing over compressed data is that unlike in this traditional version where you can compress data, you can transmit it, then you can decompress, and then you can work again with it.

2:01 Uh you try to immediately work on the compressed representation. And that is nothing but a data structure, right? A representation of data that you can work with, that's a data structure. So, if that data structure in addition has some some way of using little space, whatever that means in detail, we could call it a compressed data structure or a space-efficient data structure. And if it can still um answer queries, it may be very useful. Uh in that you can use it for both to transmit the data and use and work on it. Now, you can formalize what space-efficient means in many different ways. Um uh sometimes people say compressed when they think of something like uh zip or uh or as Burrows-Wheeler transform-based things, where really the uh data structure is even smaller than the original input as it was written down. Uh here we'll start with some um more uh worst-case oriented um notion, namely a succinct data structure somehow has an information-theoretic lower bound in mind. This will become more clear if I show you the concrete examples. This is often very easy. We're trying to represent some object that is chosen from some universe. If there is um if there is U different elements that are in this universe, this information-theoretic lower bound is just log U bits are needed And clearly, that's the best compression. If I know nothing else and I'm after a worst-case compression scheme, log U bits is the best I can do.

3:55 Right? Uh and then the data structure is called succinct if its space usage is essentially um asymptotically equivalent to this information theory lower bound. Or a formal way to write it is uh the bound times 1 plus little o of 1. Right? Leading order term. We care about the constant. Not just uh the right theta class, but also leading order term um optimal.

4:23 Okay. Um that's a that's the one goal. Why would you care about these things or how would um maybe this get interesting? Uh let me motivate the building block that we look at today with this following toy example. Uh >> [snorts] >> You have a a text, and this is clearly compressible because it has few letters and a bunch of A's.

4:49 So, maybe you would want to apply a Huffman code. Here's a Huffman code computed from the frequencies of the letters as they appear in this string. Of course, it's a small example, right? It's not so powerful, but you can do this of course in in a larger example. Either way, we get some um codes for these letters. So, instead of using, say, 1 byte each as in ASCII, we can represent the entire string using bits. With from the Huffman code, each letter gets replaced by its code, and then some characters take more and others take fewer bits, right? That's easy. Um kind of uh undergrad data structure stuff. Now, what if you want to decode the text again? Sure, I could do that, right? I start at the beginning. You zero can only be an A, so that's the A. Then I start reading 1 1 1. Aha, I'm in one of these guys. 1 1 1 0 0. Okay, I have a B.

5:48 Right? And this is B. So, decoding is easy because it's in Huffman codes have a have this prefix property that no code word is a prefix of another code word. They're also called instantaneously decodable because when you read a code word, you you see that this is a code word, you can instantaneously say this is the letter. So, it's a good code. Now, this is fine for storage and transmission, but what if I give you just this bit sequence plus the Huffman code and ask you what's the ninth character in the text? And uh you don't see this, right? Um how would you do this? How do you know where to start?

6:35 Ideas? >> Yes, we need to we would need to translate uh T0 until T8 for the context, right? >> Yeah, exactly. So, um in a way how would we know where the code word starts? Uh the answer is we don't. Two options. I could start reading from the beginning. That's fine for character nine, but less fine for character 9 million. Uh or I need to store where the characters start. That's the other obvious option. Now, if I just do exactly that, store for each character its starting bit as an index, it turns out that these um starting positions are much bigger than the entire text, even uncompressed. So, uh that whole totally defeats the purpose of the compression. Right? Yeah. Can't Can't we do better? Like, there must be a there must be a better way, right? Okay. Um in this case, um there's a clever way to do much better. Uh we'll come to this not even today in the full version.

7:40 Um but in a way there's uh there's a little data structure that you can latch on top of this uh bit string. And if this has n bits, uh okay, this is this is bad notation. Let's rename this to m and this to n because what I really mean here is the number of bits. This is this is what n is supposed to do. So, I'm storing a little extra, but what I store extra is not even a single bit per bit is little o of n. And then I can answer in constant time where a character starts. And once I know where it starts, I can decode as before. Okay? Uh I find that still rather cool that this is possible and you'll see it's the little o of n. Um Yeah, it's not it's not even it's not even hard. So, um we may not get to it today. We need at least in the first session next week, but you'll you'll see how this works.

8:45 Let's also test the limits of what we may not be able to do. I said constant time I want. And maybe you can uh it's not visible from what I've told you so far, but really what we're doing um we essentially treat this um we'll we'll we'll think of this as another bit vector that tells us a one when there's a character that starts. Now, these are zeros because it's a continuation of the B. Then there's another one and another one and so on.

9:18 So, I could I could imagine storing this second bit vector that tells me where a character starts, yes or no? Now, if I do select on this bit on this bit vector as a set, find me the uh ninth one. That's precisely our question. Okay?

9:45 >> If I can on this bit vector support this operation, select the ice one, then I have my answer. Now, this sounds maybe dubiously dubiously familiar with the lower bound we've just covered. If I could store in it a bit vector where the ones represent elements in the set and zeros not in the set and select Well, select is select, right? I can find the the Kth smallest. That's precisely what the Fredman-Saks lower bound covered, which says that if you want to do this dynamically, you can't really do constant time. Even I don't care how much space you try to spend, you're stuck with this log n over log log n lower bound for for the running time of operations.

10:40 And that's even cell probes. God knows uh if we need more more time to actually implement it. So, it seems there's um a certain impossibility between um between the dynamic and rank and select running time. We can't have both at the same time. I specifically like um from the setup from before, we can't have dynamic bit vectors and rank and select queries in little low of this. Specifically, constant time doesn't work. So, for for me, the um consequence of this lower bound is that we should focus on static bit vectors for now. Uh the theoretical reason is, well, you run into this lower bound, so what can you do? Uh the practical reason is there's good use cases where this uh bit vector doesn't need to be dynamic. I think this one is one if the text is not changing. This is also not changing and so this bit vector is also not changing. And there's plenty of cases where this is where this is true.

11:48 Another practical scenario where the data does change but it's kind of okay if the data structure doesn't support it. It's something like an index. You once in a while rebuild the index. You throw away the old one, build it from scratch. What you care about is that the index is fast. And here is specifically we care about that it's also small. For all these cases static is a bit less less problematic or less bad than it first seems. Um It would be cool if everything was possible but we can't have all at the same time.