Transcription
Hi everyone, welcome. Uh, so we're going to be onboarding on our journey for the class E274 on Data Compression Theory and Applications. And today, it's all going to be about introduction and logistics. And then we'll just deep dive into the material towards the second half.
Um, so this is your course staff. We have, uh, Professor Saki Weisman, uh, standing right there, um, in the cool jacket. Um, we have Sham, who's also there, and he'll be taking the second half of today's lecture. Um, I am Pul, um, and I'll also be part lecture. And then finally, we have our awesome TAs sitting there. So for any, any class-related material, uh, we also have Kadar, who was the instructor from last year, who will be helping us from the sidelines. So you have another extra resource at your disposal.
Okay, so let's just dive in. Um, so this is like a curve which you might encounter at some point in your life. Okay? The Y-axis here is the data volume in zettabytes, and the X-axis is the year. So this is like the volume of data which has been created and replicated worldwide. Okay? And it has a trend which is like, okay, it's exponentially increasing. Uh, but like, and, and this kind of curve kind of shows up in all sorts of applications. Uh, but like, what, what do these numbers really mean? Like, right? Like, what do they reflect more precisely? Like, what exactly is a zettabyte? Like, why should I care? Right? So let's, let's try to get some sense of these numbers. Okay?
So let's start with a megabyte. So a megabyte really is six zeros behind that one, and it's roughly the space which is occupied by a lossless image in your smartphone. So this is the image of my cousin's dog, Ace, and the unfiltered version of it was taking approximately a megabyte on my phone. Okay? Continuing, as you add three more zeros behind it, you get a gigabyte, which is approximately the space which is occupied by a typical 4K video of a few minutes duration. And, uh, this was supposed to stream automatically from YouTube, but it was basically a video clip of your favorite anime. Okay? Continuing, if you add three more zeros behind it, now we start talking about terabytes. Okay? And this is something which I'm sure at some point you might have encountered when you went on to buy, uh, an electronic device from your favorite manufacturer. U, this is what that manufacturer kind of charges you for each extra terabyte storage. Okay? And you need that extra terabyte storage year after year, right, to store all those photos and videos which we just talked about. Okay? So at this point, with the, I guess, 12 zeros behind, we are already at the typical storage which is available on your laptops as of now. Okay?
Let's continue. Add another three zeros, and what we get is actually a petabyte. And at this scale, we are now talking about the databases which are stored by, like, really, even medium-scale companies, uh, as of today's standards. It's actually the de facto cloud storage unit. So if you have ever heard of AWS S3, Google Storage, Azure, like all of these are cloud storage services where you can store your data. And when you talk about, like, how much data is being stored by these companies, you typically talk in units of like petabytes. And again, a petabyte, like at each of these steps, we have been adding three orders of magnitude behind what we have been seeing before. Okay? In fact, like, a cool fact, like Meta was roughly generating more than a petabyte of data to be ingested every day, like, every day. Okay? And so at this scale, basically, what you're talking about is millions of dollars of management if you are a business person from a company managing this data, or if you are a, if you are a team at AWS S3 or GCS, you, you are, like, by managing petabytes of data, you're talking about millions of dollars of data in management under your control. Okay?
So far so good? Let's add another three zeros, uh, because why not? So now we are at 1, 2, 3, 4, 5, 6, 6 * 3 zeros behind the one of the bytes which we were talking about, and what you get is an exabyte. And this is roughly the estimate of data which is being transferred over the internet daily, every day. This is the amount of bytes you are, like, sending to and back. Okay? And this finally leads us to what this number zettabyte really is, right? One zettabyte is actually three orders of magnitude over what I just talked about the last thing. So I want to wait a second, and I want you guys to really appreciate. These are like 21 zeros. We started with just six zeros behind one of your photos. It's not multiplied by two, it's multiplied by 10 to the 15 from that single photo which you are very carefree to capture on your phone, right? And this zettabyte is what's being shown on this curve. So when you went on from, let's say, 2 zettabytes around 2010 to something like 64 zettabytes, it's actually 62 of 21 zeros of data added in the world.
Okay? So clearly, managing this much amount of data is an issue. Like data is growing at an exponential scale, and this is a serious problem in all applications, right? You have to somehow manage this data, you have to somehow understand this data, you have to use this data to drive your business, or you have to use this data to really come up with the cool machine learning applications if that's what you care about. Okay? So this clearly states that, like, there is a need. Like, if this continues, like, we, we, we won't just have enough space to store data for ourselves, right? So you have to worry about the storage at this point.
But interestingly, it's not just about data at rest. It's not about just, okay, I collect this data, I store it at one place, and life is great if I can do that. It's also about the data in motion. Once you store this data, you will use it for a thousand different applications, for analytics, for just transferring data to your friend, so on and so forth, right? And that's also a very big issue. Like, you have to move this data around. So this is like an estimate of, like, the proportion of internet data traffic around, I think, 2021. Um, and here, what you see interestingly is videos are taking roughly 50% of your internet data traffic daily. And this is a serious issue. How can I convince you that back during COVID, Netflix got a technical request, like, legal request from the EU to reduce its bandwidth because they were just not able to support it, they were not able to support the increase in data traffic around their networks? So Netflix was basically asked to either reduce the quality or improve their compression algorithms, improve the compression which they provide, right? Um, and again, like, these are just, like, some conservative numbers of, like, what you are really streaming when you are watching your favorite show, like how much data you are consuming without even thinking twice about it, right? So these numbers, if you, if you just look at them, like a high-definition Netflix stream can use as much as 3 GB of data each hour. Okay? These, these numbers, and the world which we live in, is unprecedented, and it's an, it's an exponential growth scale with respect to the data.
Great. But the interesting part is, I said about videos and Netflix, right? But it's not just about videos, it's not about any single kind of data. Data compression shows up and is of value wherever you collect data and whatever kind of data you are collecting. So things like text, log files, code, even like, if, if you do, if you ever use GitHub, um, and you do a git pull, this is like a standard message which comes up. So this is, for example, an instance of when I was updating the website for the course, and very interestingly, here it says something like "compressing objects," right? So if you have never ever actually looked at it carefully, even GitHub, every, every time you are doing a pull, push, any of those things, you have to compress. Otherwise, you can't really do a version management, you just can't create copies at every single change which you're making and committing to your favorite repo. Okay? So this is like working in the background. But not only that, there are like genomic data, emails, all your Google searches, tweets, images, videos, things like EEG, which is like electroencephalogram, like sensor data. Like, if you think about, like, the biomedical applications, the amount of data you're collecting is immense. And again, there is many times, there is like, it's not even possible to transmit this data, collect this data, let alone, like, do any sort of analysis on top of it. Like neural recordings, your Multiverse, and not even that, even LLMs and ML models. So if you, if you care about machine learning, like there is a big push for machine, like, there is a deeper connection between compression and machine learning models, and there is like bidirectional communication. In the sense, like, people have been using machine learning to improve compression, but not only that, compression has been an integral part to understand what's happening in machine learning. So if you have, if you are aware what's happening of, maybe I don't know, Llama and so on and so forth, you would also know there are all these sorts of quantized models. Like, why do you need these quantized models? Why is everyone after them? Because unless you do that, you can't run any of these things on your favorite devices.
Okay? So what I really want to highlight here is, like, it's, it's omnipresent. No matter what's your application area, maybe you are a bioengineer, uh, maybe you don't care, you're just a software engineer and wants to have the most efficient version management for your software, or or you're just a machine learning engineer, right? No matter what you do, you will see compression at play at some point during, uh, during your lifetime.
Even more interestingly, your compression, it's, it's filled with tradeoffs. It's not really like when GitHub says, like, okay, compressed, there were a lot of design decisions which were made in the, in the background. And what we'll teach you in this class is also to understand, like, how to make these design decisions, right? It's not just about taking a file, uh, right-click, compress, and be done, right? It's, it's always about, like, the tradeoffs. Give your applications what you really want to achieve. And this is like a curve which we'll see a lot in the, uh, or like variants of it a lot in the second half, and Saki will cover its theoretical aspects too. Uh, but basically, what I'm showing here on the X-axis is size, and on the Y-axis is error. And for those of who, uh, those of you who are aware, it's like the rate-distortion curve, if you would have heard of it at some point in your life. And the basic idea is this, that when you have higher size, you can get away with smaller errors in your, your files, right? And as you keep decreasing your size, you will have higher and higher errors, right? And this kind of leads to some very interesting tradeoffs. And maybe let's get into some of them. Uh, let's try if this works or not. Okay?
So now, hello, yeah. Now I'm going to play some audio files for you, and let's just see what you guys feel about them. Okay? So this is the first audio file. [Music] Okay, uh, I don't know, maybe some of you recognize what was being played, maybe not. But this is like that audio file at roughly 5 MB. Okay? And that's maybe this point. Let's reduce the size and hear what this file sounds like. Okay? Uh, any thoughts? Like, was it good, bad, don't care? You have, you have some thoughts. Oh, shouldn't play. Okay. Anyone? Yeah, you felt the quality went down. Oh, a little bit. Okay. Uh, but was it okay? Like, in the sense, would you still... Okay. Actually, any other thoughts from the class? So right, felt that the quality went down. Anyone else? Any thoughts? Couldn't, not sorry, what's your name? Okay, so here said that he couldn't notice much difference. Great. So we have some difference in opinion here already. And we reduced the file size to something like half. Okay? Let's, let's go down a little further and see how that sounds. [Music] Like, okay, what about now? Worse, but you might still live with it. Okay, that's fair to say. Um, anyone else? Any thoughts? Yeah, the frequencies are distorted. Like the last one was much more shrill and like, okay. Uh, sorry, what's your name? So here observed that the frequencies went went down and he found that the last one was like a bit shrill, um, and just like something was off. Um, and again, like the point which I want to highlight is that at this point, you have compressed the file, and even in this classroom, which is really small, the scale of the world, we have some difference in opinion, right? Maybe said he can live with 2.5 MB, he doesn't care. Is not cool with that. Like, uh, even, even going from 5.3 to 2.5 MB is like, this is, this is my favorite song, I can't, I can't hear it like that, right? And when we went down even further, there was again some more disagreements, right? Like again, like some of you might be okay, some of you weren't. And these are the real tradeoffs which you face in the real world, right? Like you have to take a call. Like, if your phone just has, I don't know, a megabyte of space left, you can't do anything. You have to go down to that size. But something interesting to note was, even at, I don't know, we reduced it by roughly 5x, the audio quality sound still okay. Like, if that was the space which you have left in your phone, you might still want to keep it. But let's say if you're streaming it over the Stanford network, you wouldn't like to do that. You would like to hear the best quality, right?
Okay, so this was just an example of the audio. Um, continuing, we can look at the same example for image. Uh, so this is like a popular, popular character out there, just an image of the character. If you don't know, don't worry. If you know, hope you like the show. So it's, uh, this is the image stored at 585 kilobytes. Again, let's reduce the size further, and this is at 280 kilobytes. For me, I am okay, right? Let's reduce the size further, and now this is the same thing at 13 kilobytes. Okay? We have reduced the file size by, I don't know, around, like, 500x, right? And there are two comments, like, more or less, I think this is okay. This still captures, like, the big part of this image, right? Like, you can still make out the character. But if you are a connoisseur, if you really like to watch a lot of movies and like whatnot, maybe you observed that there were like some distortions which started showing up, like ringing artifacts, right, around here. Um, and during the class, we'll get into such details, why these things happen, what are the compressors being used, when you can throw away stuff without introducing a lot of distortions. And this is like, this is basically the job of all the big businesses. Like Netflix optimizes its stream so that you can get the best quality, or, or your favorite streaming provider, right? Same with Spotify. Like, if you look at Spotify settings, you would see like, whether you want the highest quality or the best data saving mode. This is the curve along which they are basically playing. So hopefully, by the end of the class, you can appreciate all these things better technically and be able to understand these tradeoffs more intricately.
Okay, so I'll wait. Any questions so far? Cool. And so, okay, so this is really the punchline, right? And I'm quoting Saki, who's just sitting right behind, because this is where I heard it first from, and I really think this line kind of summarizes data compression. It's, it's basically the succinct representation of information. Okay? So you're okay to throw away stuff as long as you don't throw away information, or you try to keep basically whatever message being communicated through whichever medium as close as possible to the original one. Yeah. And like we have been saying, like, why do we care about compression? I think I'll go through this, like, because I did show you guys some examples of why you might care about the compression. Uh, but basic, basic points have remained the same. So like storage is costly, and like we are generating exponentially exabytes more data, right? More so, it is really the purest form of information processing. Compression integrated is related to your, um, signal denoising in a way. You are basically trying to keep the most useful part of the information in whatever thing you are outputting out of this compression, right? And in the same way, it's equivalent to communication without noise, right? So when you're communicating, maybe you're adding some noise, you're spending some storage to actually, or some bits to actually spend on those noise. And what compression tries to do is extract the relevant information out of it. Okay? So you also have these compressed representations which might be very easy to transmit and search on, because now you have thrown away the fluff and kept really the information part of the things. And it can even simplify implementations. For example, if you're working on just the compressed representation instead of, like, the whole big data, you may not be able to move that whole big data. Versus if you're working with a smaller part of it, maybe you can do something about it, right? More so, it has a very fundamental relation to data modeling, prediction, and even like your favorite ML, as to say, right? And this is a point which we'll try to drive home at some point, that basically a good compressor is a very, a good predictor, and vice versa. If you basically somehow are able to come up with a good predictor, you can use it for compression, sans some conditions which we'll talk about, and, and so on and so forth, right? So it's very fundamentally linked to what you are able to predict. And finally, it is really a very critical building block in today's, like, I would say, any scalable and efficient system. Okay? In fact, my first foray into compression wasn't even through the standard compression thing. I was trying to build an application, uh, for for brain-machine interfaces, and there was absolutely no way I could have collected that data and transmitted it. Like, it was just impossible. I would have been working on some eye prosthesis, and I would have burned the eye like way before I would have been able to collect the data I would need. Okay? So what I'm really trying to highlight is, no matter what application you are into, at some point you might run into compression, just as, as a necessity. Or we have actually sitting in the class, and like in her case, like she, she, she used compression as a tool for her application. And that's another way where, like, you might come up with some of the tools we'll talk in this, uh, you might use some of the tools which we might come in this class in very interesting ways in your application. And that all stems back to all of these things that essentially it has a very deep connection to prediction, it is basically the purest form of information processing. So compression is basically, what I want to highlight, it's way beyond again, right-click, compress, zip, done. It has, it has, it is very interesting. In fact, it is so interesting.
Actually, let me pause here. Any questions so far? Okay. Yeah, so compression is super interesting, no matter what your interests are. Okay? So what I want to highlight is that there is something for everyone who's sitting here. You love theory, you, you really like to understand the world in mathematical formulations. Compression has very deep connections to information theory, and here it's Claude Shannon, who like the father of information theory. Okay? Uh, for example, I have, I started this presentation with exabytes, megabytes, kilobytes, whatever, terabytes, so on and so forth, and all of you are like, yeah, we understand, very cool, right? Sure. So we are in a digital information age. Everybody knows what bits are, what bytes are, right? But basically, it has a very fundamental connection to whatever we have been doing. It has a fundamental connection to information, and it's, it's, it's not coincidental or arbitrary that we are talking in terms of bytes. And in fact, we'll cover the basics in this course. Uh, next week, most likely, you'll start seeing the exact bits coming up. But if you're more interested, I would encourage you guys to take E276, which is a specific information theory course, again, um, taught by Saki. Okay?
Another interesting question. So take your favorite compressor, I don't know, whichever one you want to pick. Input it a file. Like, I don't know if you have ever thought of it, but why can't I just keep applying it in a loop? Like, whatever output I get out of, I don't know, zip, let me zip it again, zip it again, zip it again. Why am I not able to get to zero bytes? Like, why where am I taking any space? Right? So, so actually, very interestingly, apart from the implementation inefficiencies, no matter what you do, there is like a fundamental limit to where you can compress things, and it's very well understood mathematically. And that's where, like, the entropy terms kind of, uh, entropy term gets introduced, and we'll explain it to you. So, funny, if somebody comes to you with their billion-dollar pitch and they say, "We can reduce all the file sizes by, I don't know, 99.999999%," you can turn it down very politely, uh, after taking this course. Like, don't entertain. Okay?
Another fundamental question is, like, for example, which we saw in the audios and videos case, images case, which is, how much can I compress if I'm okay to lose some information? Right? For example, in that image case, we went from 515 kilobytes to 13 kilobytes, right? And we got some quality. Was this the best thing I could have ever done? Could have done something better? And again, there is like a very interesting to the core, beautiful mathematical theory for it, which is called rate-distortion theory. And you'll understand that there are like fundamental limitations to what you can do there, again. Okay?
So if you are into theory, there is, there are some very interesting questions which involve compression. Okay? Maybe some of you are from CS here and you don't care about theory as much, but you get very excited with algorithms, right? Like, you, you want to just like, okay, there are like extremely elegant algorithms which are involved in compression, right? And we'll introduce some of them in the class. Uh, so here's a picture of Lempel-Ziv and zip, which is the LZ. And hopefully, by the end of this class, you'll be like, you, you will know. So I'm throwing lots of acronyms here at the end, but the hope is, by the end of this class, you'll be familiar with them, you'll be conversant with them, you'll be able to talk with your peers and others who work in compression, uh, about them and be able to understand these things technically. So, for example, there is like existence of universal lossless data compression algorithms, which is like the reason for popularity, popularity of all these LZ-based schemes. For example, Gzip is an LZ-based scheme. Okay? Even more so, there is like all this usage of transforms in multimedia compression, like KLT, FFT, DCT. And you'll, you'll understand why these algorithms and to be able to do these things efficiently is extremely important for compression. And finally, like, again, very interestingly, like, there are questions like, how are numeral systems, like 2 * 10 + 2 = 22, how is this related to compression? And might, might find you might find it very surprising, but it is. And you'll learn in this class how.
And finally, if you are someone who is, who's like, even like a true engineer who works down, goes, writes down the assembly code or writes the most efficient software code, you don't really care about the algorithm, you want to optimize to the, to the dot. There are some extremely clever implementations involved in compression because, as you might imagine, like, nobody has the time to wait for your video file to decode in a day if you, if you want to watch your favorite Netflix stream or whatever it is, right? Just absolutely no one has time. And so there are some very extreme clever implementations which people have come through in this. So, for example, like, I'm, I'm going to just combine this in a single go, which is like, can we cache computations? Very simple questions, right? But if you are someone who has done computer architecture or hardware, um, like, you'll be surprised to know there are like specific hardware implementations in your laptops right now, just for being able to run a video decoder, without which your videos won't run real-time on your favorite browser. So people have not only optimized software, they have went on and worked at the level of instruction set architectures to optimize the compression algorithms and theory which which which just preceded. Okay, this is, this is a fun one. Um, I don't know if you guys have noticed, but if you are trying to go back and forth on YouTube, Netflix, Prime, whatever it is, there is like some smallest delta at which which you can go back and forth. Maybe it's 5 seconds, maybe it's 1 second, 2 seconds, depends, right? But notice, like, try it after you go home today. Like YouTube, you maybe will have to check. I think it's five. No, it's one, I think. I don't know. But some point it used to be five. Um, and if you go back and forth, you, you can't go back and forth in units smaller than them. Okay? And that's also very interesting because it comes around from a clever implementation for you being able to stream videos real-time. If you don't do that, if you try to give a millisecond-level stream, like millisecond-level seek for the videos, you won't be able to decompress at real-time, and then you'll start seeing the annoying bar which everyone, the annoying circle which everyone hates. Okay? So that's actually a side phenomenon which is coming from the from a clever implementation. And there, basically, you have something called frame groups, IPB frames, which is again something which we'll touch in this lecture at some point. Um, and finally, there are also some interesting data structures which shows up, like suffix trees and BWT transform. In fact, there were like data structures which were designed for compression and now are mainstream in certain places like genomics. Okay? And so really, the takeaway of all of these examples is that no matter what you like, there is something fun for you in the field of compression. And in this class, like, how this class, I would say, differs from the other offerings, even at Stanford, is that we'll try to give you a flavor of all these three and like, kind of packed in in a quarter's framework. Yeah.
So in particular, the first half of the course, so now we'll get a little bit into the course. The first half of the course would deal with lossless compression, which is like, if you don't lose any information. Um, and the second half would deal with the lossy compression, which is like, okay, I'm okay to lose some information. What's the best I can do now? And throughout the course, we'll keep showing you workings of various tools and code snippets. So there'll be a mix up. We'll also show you some theory, some proofs, but we'll also show you like lots of tools and code snippets. So hopefully, it will be fun for everyone, and you'll try to appreciate the same material from different angles. Uh, so this is just the course outline. It's also available on the website, but let me just go through real quick. So on the lossless compression side, we'll talk about entropy and its fundamental role in compression, like we have been saying, um, for the, I think, till week two, roughly. And then we'll start getting into the lossless compressors, right from week, week three of the class. And there, we'll study like lots of compressors like Huffman, arithmetic coding, asymmetric numeral systems, your LZ. On hopefully, by the end of it all, you would have a deeper understanding of how Gzip works, or how you can improve do lossless compression much better for whatever application you have. We'll also talk about how you can handle correlated sources or things like adaptive arithmetic coding. And this is going to be roughly till lecture 10. So first half of the class. And then the second half of the class will be around lossy compression, where, like I said, I've been saying, uh, for some time, we'll talk about rate-distortion theory and mutual information. We'll talk about quantization. We'll talk about transform coding, like all these different transforms, why do they show up, why do they matter? And then we'll have, basically, a very deep dive into images. I think roughly two and a half, three lectures, almost, where we'll talk about image compression, because a lot of these principles kind of tie together there. In particular, we'll talk a little bit about how JPEG works, BPG works, as well as how ML, in particular, has been used to improve compressors. So like the new age compressors, people have been trying to incorporate all these new ML findings. So we'll have a dedicated lecture on that on, like, how you can do learned compression. And finally, we'll kind of wrap it up with, like, video compression, because, as I think I've been highlighting, video is really a big part of your streaming pipeline, and some role of, like, human perception and, and lossy compression. And the hope is, by the end of this, what I'm showing here on the right is just like, there's this tool which gives you properties of, uh, a compressed file, in this case, a JPEG file on my laptop. And there are a bunch of things, and maybe some of you are familiar with some of them, maybe all of them, maybe not. For example, things like what is, does this encoding process mean, baseline DCT, Huffman coding, what does this VBR sampling mean, what does this color space mean, right? Things like this. And hopefully, by the end of all of this, you would be able to appreciate these things and understand and make through.
Okay? And then finally, it's, it's a rich field. We are only going to touch, like, the tip of the iceberg. But there are like, a bunch of interesting extensions which we would encourage you guys to play with during the course project. So I don't know, like, I've been saying, so if, if one of you, if some of you are really proficient in ML, and that's what you want to do, uh, you'll come talk to us, and we'll try to frame a very concrete problem for you around, let's say, compression and neural nets. Maybe it's not just about using ML, but also like, like you have this big neural nets, how do you apply compression to them, right? So it's, it's, it's a, it's a two-way thing. You can use ML for compression, or you can compress your ML models to improve efficiency. So this is just like one of the examples. Or again, like, I think I said at some point, like, so if some of you have architecture and hardware background, maybe the way you, you can dive deeper into this material is by picking up one of the algorithms and trying to implement it in your favorite assembly, like favorite low-level language, right? So it's, it's going to be up to you, but there are like lots of topics. And in particular, I'll say, like, so we are going to organize something called Information Theory Forum, and, uh, is going to, uh, have guest speakers, basically, like leaders in their field. Also going to come and talk to us about various different topics. So think of them as like complimentary aspects to the course.
Okay, let me pause here for a couple minutes because after this, we'll just, uh, go into the logistics of the class. Any questions so far? Any comments, thoughts? No? Cool. I think, uh, we should move on to the next part. And I think I would like to just end here, shamelessly stolen from Saki, but this is really the spirit of this course. Like, try to have fun. We are also here trying to have fun. We just find this material very nice and interesting, and we are always open to feedback. So do come talk to us if something is not working or something is working really well, we can do more of that. So going ahead now, Shubham, uh, will take a deeper dive into the actual material. We start the actual material, um, and the first half again would be more on lossless. So we'll start our journey into the lossless compression.
Hi, hi everyone. Welcome to the class. Um, so today, a short, short lecture. I will speak for a bit, introduce what lossless compression is about. Um, right, so, so the plan for the first few lectures, as Pulit described, is we will cover a bit of theory, uh, some concepts from information theory. Uh, you will already start seeing some algorithms as we start with the theory. And, uh, you might have done other theory courses or seen theory in other classes. Uh, one thing I find very nice about information theory and compression is the theory is really useful. It's not some abstract thing. It's it applies to some very specific simpler settings, but those simpler settings are very prevalent in real life. Even like this Monday, I was, uh, uh, something in my work, and I thought, can I compress this better than this Gzip or Z standard is compressing it? And I just, like, wrote a short Python notebook, was able to determine, no, there is a gap, um, with just some very simple theory that you will in the next few lectures. So it's not very hard. There is no, like, very fancy math involved, but it's simple, but it's, it's very interesting, it's very intuitive. You should have fun with that. So let's get started. Stop me at any time if you have questions, okay?
So, so there was a question before about, uh, what probability background do we expect? Uh, so you should be familiar with probability, random variables, expectation, conditional probability will come in a bit later, sort of joint distribution of two variables. Uh, yeah, that, that's really it. Expectation will come, come in a lot. So you should know what expectation is, what is a conditional expectation, that sort of thing. Uh, you don't need to know, like, uh, sort of advanced probability, uh, like Borel spaces, that sort of thing. No, that's just basic first course in probability is what you need. Okay?
So let's get started with a very simple setting. You have an alphabet. So every probability space usually has an alphabet, right? So, so here the alphabet is just A, B, C, D. You have just four symbols in your alphabet, and we have a very simple distribution. We have all of them are equally likely. So each of them has a probability of 1/4, right? So what I do is, I, I create a text file. I just independently sample among these, uh, with this uniform distribution, and I, I get a file. Uh, I, I sample 1 million symbols, right? So as you know from, like, the law of large numbers, what I would see is in the file, I would have like around 250,000 A's, 250,000 B's, 250,000 C's, and so on. Um, so can somebody tell me, what will be the size of this file on, on disk? Um, it depends what you choose to represent the symbol as in terms of bits. Like, if you use one byte per symbol, then it would be, um, 8 million bits. But you can use two bits because there's only four possibilities, and then that can make it two million bits. Yeah, yeah, yeah. So, so, so the answer I got was, it depends on how many bits you use per symbol. Um, and a typical file, as we will see shortly, like a typical way, if you write, write in Python and like just create this file, you would, you would use 8 million bits, or 1 million bytes. And we'll see why shortly. Thank you. Uh, so before we start about it, Pit talked about a lot about like going up to even exabytes and zettabytes. What, what, what is a bit? What is a byte, right? Um, so this is just from the dictionary. So a bit is just a unit of information expressed as either a zero or a one. For us, the way to think about a bit is a bit is either zero or one. So it is like two possibilities, right? Every bit is a zero or a one. And, uh, those who are familiar with, uh, computers, you know, like, bit is sort of the fundamental unit at which things work with semiconductors and transistors and so on. Uh, and, and a byte is a group of eight bits, so 256 values, right, right? Each bit is two values, a byte can take 256 possible values, 2 to the power of 8. Okay? So one byte is 8 bits. And then, uh, what 1 kilobyte is, uh, 1,000 bytes, which is 8,000 bits, and so on. Uh, just, just a warning that sometimes people use powers of two instead of powers of 10. So usually it's very close, but, but like in my work sometimes, right, uh, so you have 1 exabyte. If you represent it as 10 to the power of 18, that's one number. But when you represent it as 2 to the power of 60, it actually starts to matter at very large values whether you use powers of 10 or powers of two. Uh, so just a warning, like when you're dealing with big numbers, be careful whether someone is talking when they say a kilobyte, do they mean 1024 bytes or do they mean 1,000 bytes? Okay?
So, so if you actually create this file, check the size, what you would see is the size is 1 megabyte, 1 million bytes. And we are basically spending one byte per per each symbol, right? A, B, C, D. Uh, and, and why so many of you assume are familiar with ASCII? ASCII is just an encoding. So when, when you need to represent anything in terms of bits, you need a way to encode it. Uh, so this is like a standard way to encode it. You can see a few of your favorite things here, right? You here you see like A through Z uppercase, here you see A through Z lowercase, here you see your numbers, punctuations, here, here, right? Um, and, and for each of those, like A is represented as 65, and then B is represented as 66. So it's just a way of representing all of these things we see on our keyboard as, as numbers, and hence as bits. So, like, this is the ASCII table, for example, uh, for A, B, C, D, our alphabet, right? And you see we are using eight bits for each of the values. Um, any questions? Uh, this is very simple. As Saki said, it will get progressively more interesting and complicated. Um, okay, so actually, someone already answered this question. Can we do better? And what they said was, yes, we can do better. Why? Because if you see here, this, this doesn't seem like, if you know that your file only has A, B, C, D, this doesn't seem like the best use of your bits, right? See, this, this part is like the same for all four, 01000. So you just seem to be like wasting a bunch of bits for each of those symbols. To, to sort of explain what I mean, let's see this code, right? So what we are doing now is we just use one, sorry, two bits per symbol. Um, right, two bits for every symbol. So if you have the same file of 1 megabyte, 1 million symbols, now it would use 2 million bits, which is, uh, 250 KB, right? So now, now it's like 250 KB instead of the 1 MB we were using before. Can someone suggest, like, if I use this code, are there any considerations? Like, if I, if I create a file using this code, right? I use two bits per symbol, and then I send this file to anybody, somebody, what do they need to know in order to read the file? Good. They need to know what symbol represents, like, what bits. So if they think that 00 is equal to D, then they won't be reading it right. Yeah. Do others agree? Any other suggestions? Yeah, yeah, yeah. So, so the, so the answer was, they need to know how to decode it, basically. They need to know this table, right? In, in simple words, like, if they have this table, they can decode the file. Like, did they receive this 001 and so on? Um, but unless they know that I, my four symbols are A, B, C, D, right? How do the, it was not E, F, G, H, or 1, 2, 3, 4, or something, right? Just because they get the file, they can't. That's why we use ASCII, right? That's the whole point of ASCII, that everybody knows what ASCII is. It's a standard thing. So when you send a file, they, they know it's an ASCII file, they can read it. Um, and, and we will see a lot of compressors in the class, and every time you use a compressor, you need to indicate to the, to the receiver, basically, like, what compressor did you use. Um, you might have see find file extensions, sometimes they play that role, like you have a PDF or .zip or whatever. Um, okay, so I guess this should have been X, which is what we are using for the alphabet. Um, so if you have K symbols, then you use log base 2 of K bits in a fixed bitwidth code. Let me explain. Um, so, so if you have two symbols, you just need one bit, right? Because two symbols means you have just zero or one, right? If you have four symbols, we already saw for four symbols, you have like 00, 01, 10, 11, right? If you have like eight symbols, then you could do like 000, 001, 010, so on. What would I do if I had three symbols, let's say? How many bits do I need? Good. Two bits. Two bits. Uh, what are the two bits? Like, how, how, let's say it's just 1, 2, 3 is what I'm trying to encode. Can you suggest an encoding? Yep, yep, yep. Yeah, so that's one where you could have a bunch of possible things. Doesn't matter really, like, you could do, okay. Uh, any of the possible sort of combinations here. Um, right, so is this clear to everyone? Good. Can, last, oh, I see. Okay. Uh-huh. Yeah, let me rewrite it here. 1, 2, 3. 00, 01, 10. Or you could do like another encoding which is like this sort of thing. Lots of possibilities there. Uh, for the three symbol case, do we think this is like the best you can do, or do you think we should be able to do better? I guess the person answered, oh, good. Yeah, yeah. In this case, we should be able to do better because, for instance, we could have like one of them just starts with one and the other two start with zero. So you could, you could have one of the symbols in code with only one bit instead of two. Yeah, yeah, yeah, yeah. So the suggestion is that like, who is nobody's forcing us to always use two bits per symbol, right? Maybe there are other schemes where we use different number of bits for different symbols. That's a good idea. Uh, there is another idea which you will actually see in the quiz today, that's, uh, a slightly different idea. Ultimately, it's a variation of the same thing. But yes, as you can see, like for two symbols, this seems like, okay, this is exactly right. Like, it, you, you exhaust the whole code space in a way. For four symbols, this looks exactly right. For three, already you start to see that, like, it's, it's not trivial. Like, you need to do some work to, because why, why are we using the same number of bits for three symbols and for four symbols, right? So clearly, there is some efficiency. Uh, so, so what you will see very soon is this fixed bitwidth code is not like a particularly good code in most scenarios. If you want to use the same number of bits for every symbol, very soon you run into like all sorts of limitations. Um, and, and we will see, like, in a minute, something better. Uh, yeah, what we don't, for each code, like letters, and how can you decode it? Like the, the L there is, yeah, yeah. So the question is like, if we don't, uh, fix the bit width, how, how will we even decode it? Um, we'll see a code later today, and I will ask you to actually decode it at home and come back to me in the next lecture. Uh, yeah, yeah, there are ways. We'll, we'll figure it out together.
Yes, uh, but that's a valid point, right? Like, one thing to like about the fixed bitwidth code is it's like trivial to decode. I give you a file with, like, let's say you are using, uh, like, you're using, like, a three-bit per symbol code, right? And then I give you, like, a file of, like, I give you some file like 000101110, whatever. You just, like, divide it into sort of sections of, like, three, right? And and then you can decode each of those. It's very simple to to decode it. Uh, but but the more complicated codes will be more complicated to decode. Also, okay?
So, so with this, we already saw, right? Like, if you have a uniform distribution, like each of these are equally likely, you spend one bit per symbol. This seems good. This seems optimal. We don't think this is, like, there is any issue here, right? Like, obviously, like, if A and B are equally likely, you should be need to use, you should need to use one bit per symbol, okay?
Now, see, I slightly modified the distribution here. You had just A and B, and both are, like, 50/50. Now I said, no, I have C and D also, uh, but but they have, like, lower probability, right? So what I'm saying is, it's almost always A or B, but in very rare cases, it can be C or D. This looks like a very similar distribution to the one we already had in the last slide, but now suddenly you see that if you use your fixed bitwidth code, you you start to use, like, two bits per symbol. See, you already should start seeing some inefficiency, right? Like, no, clearly this is not, like, the best thing you should be able to do. This is so close to the previous one, we want to be able to use, like, basically one bit per per symbol, okay? Uh, any questions so far?
See, this is my, uh, genomics background coming in. In genomics, you have, like, uh, base ACGT. And accidentally wrote it anyway. Um, okay.
So, one solution, which sort of was hinted by Pulkit, but which we won't really do now, is I don't care about C and D. If I see a C or a D, I will just encode it as A or B. It will only happen one, 2% of the time. Who cares, right? Uh, this would actually be fine in, like, some of the image and video compression parts, because because they, the what matters is human perception, right? You don't want to, uh, you're fine with if one pixel changes, for example. And and we'll see much more nuance there. But, uh, usually for text or logs or databases or PDF files or something, you don't want to lose any bit at all. It it has to be lossless. Uh, that that's the traditional way people do it. Maybe things will change, but but lossless compression is important, not only because the application demands it, but also when you do lossy compression, you will see that the lossy compression is of often built on top of lossless compressors. So the first half of the course will basically, like, provide you the foundation for the second half of the course. So we do want to Los losslessly compress it. We don't want to lose the C's and the D's. Um, right.
So, actually, like, some people have already suggested a solution, which is to use variable length codes, which we will now see. Variable length codes. This is, like, the key idea for today's lecture, really. Uh, this is sort of, this should be a takeaway. Uh, and let's see it here, actually. Okay.
So, simple idea. You have things which are more probable. You have things which are less probable. Let's use less number of bits for the more probable stuff and more number of bits for the less probable stuff, right? That's sort of obvious. You want to reduce your overall, uh, expenditure of bits. You want to make your file as small as possible. So, let's do it. And and we'll come back to the question that was asked about, like, how will you even decode it? Uh, let's come back to that later. For now, like, trust me that this can be decoded. Uh, so, do we understand the code, right? So, what are we saying is that A will be decoded as zero, B will be decoded as one, encoded as one, zero, C is as 11, 10, D as 111. So, like, let's say you had, like, A C D as your thing. After you encode it, what you will get is A will become a zero, C will become a 110, D will become a 111, right? So, hopefully, hopefully that part is clear. Like, the code just is a way to, like, you have a sequence of input symbols, you are able to encode it as a sequence of bits, right? And why do we use bits? We already talked about it because bits is the unit of storage on a computer. So you need to ultimately convert everything to bits. Um, right.
Any questions so far? Okay. Um, right. So, remember this idea, right? Really, this is takeaway for today. Uh, fewer bits for more variable symbols. Very obvious. Now, see the last one we had, like, uh, the the previous code we were talking about was two bits per symbol. That was very simple to evaluate. You would just, it is using two bits per symbol. Here, it's trickier, right? Here, it's for some symbols, you're using just one bit, for some symbols, you're using three bits. So, is it better than the previous one? Can somebody suggest, like, how would you, first of all, do you think it is better than just using a two bits per symbol code?
Good. It should be better since, like, half, roughly half the time, we're using one bit instead of two. And then to evaluate it, you look at the bit symbility together. Yeah, yeah. So, so that and Serv was which is correct is, uh, you can say that half of the time you're using just one bit, right? So, in this case, you're just using one bit, and here you're using two bits. So, on average, you are, like, roughly using 1.5 bits per symbol, right? The other two, we will ignore for the moment because they are very low probability events. So, basically, you're using 1.5 bits per symbol instead of using two bits per symbol. Um, is that roughly clear, right? Like, because each of them, like, A and B are really the things that occur more often, right? For A, you use one bit, for B, you use two bits. So, it's on average, like, 1.5 bits per symbol. Um, let's make it precise and then then we'll come back to the inter, um, expected code length.
So, this is the measure we will use to evaluate all of our codes in the first half, basically, of the course. Uh, so, so what, what is this? This is one way to think about it is compressed size divided by uncompressed size. So, how many bits you're using per symbol of input, uh, right? On average, right? So, so, so there is a expectation floating around. Uh, let's come to that. Okay. Sometimes it is called compression rate, sometimes it is called compression ratio, sometimes people use compression ratio to mean the reciprocal of this quantity. So, so lots of confusion. Don't worry too much about it. We will, whenever we give you a homework or a quiz problem, we will clarify what we mean exactly. Um, but, but, but really, what it means is the bits per symbol, like, like, this is sort of the way to think about it. How many bits you are spending per per input symbol. Um, so, so let's say you have a symbol X with code length LX, right? So, in the previous slide, for example, A had a code length of one, B had a code length of two, so that sort of thing, and probability PX, then the expected length of of your, uh, of a single symbol is this. This should be clear, hopefully. If, if it is not, if, if you think you have, like, you need to brush up on your probability, let us know. We can find some resources, send it to you. Uh, but hopefully, this is very basic stuff. Hopefully, everybody is comfortable. Um, yeah.
So, for this code, like, let, let's just compute the probability. Uh, okay. So, let's write the length down, right? So, zero is length one, this is length two, length three, L three, hopefully this is clear. Uh, and then we just need to do, like, PA * LA plus PB * LB and so on. Can somebody do it for me?
Go. Yeah. 1.53. Yeah. So, a couple of students correctly answer 1.53, which, if you recall now, like, is very close to 1.5, right? Which we expected already from our sort of back-of-the-envelope calculations. Uh, yeah, here is the full math. You will have some quiz questions. If you're, if you need to brush up, you will get an opportunity. Uh, yeah. So, this is good, right? Like, calculations aside, like, we went from two bits per base, uh, two bits per symbol to 1.53 bits per symbol. So, so that's good.
We have an unanswered question, like, can you decode it, which we will answer next, next time. Um, so, see, this is, this is the point, basically. Is the code lossless? So, what I would suggest for, uh, next week, do this, I guess. Uh, let me write something and then I will ask you to decode. Don't, don't see me writing it because otherwise, like, you will know, like, what order I wrote it. Uh, okay. Let's say, like, uh, so, just decode this and, like, uh, so, next lecture, we will see if we are able to decode it, right? And whether everybody decodes it to the same thing, or do we get, like, five different answers? Um, yeah, right. And we'll talk about this in much more detail next lecture. You will, you will understand if you are able to decode it, why you are able to decode it. Exactly. There is a reason. Um, right.
The other, other thing you, you should have seen is that the non-uniform distribution we saw it, the 49, 49, 0.1, 0.1, it was worse in a way, right? Because you had two extra symbols. It wasn't as simple as the original one. Like, like, I'm talking about these two distributions, like the AB and the other one we saw with the AB CD with the 49, 49, 0.1, 0.1, right? So, so one thing you might have noticed is these two look very similar, and so, so you would expect that the optimal code, like, the best you can do for both of these distributions should also be similar. That's just intuitively, right? So, right now, we got from two bits per P to 1.53. That's not really optimal. And and you will see it in a few lectures how you can actually achieve, like, the best for this distribution, right? And you might think, okay, why do we care? It's a weird distribution, but, but as you will see later, right, like, when you have a video compressor going on, and it produces a some sort of intermediate thing that can have any distribution, and you need to be able to encode any distribution optimally to get, like, to to the best results, basically. Um, right.
So, so that's what we'll do for the next few lectures. So, we will compute the optimal compression rate for this setting. We will show that it's roughly 1.14 bits per base, right? So, it's not quite one bit per B, one bit per symbol, it's 1.14. Um, and very interestingly, we will show that we, we'll show how to achieve this, and we will show you cannot do better than this with any scheme in the world, with infinite compute, whatever you do, if you want lossless compression, this is the best you can do for that that particular distribution. That that's, like, one of the beauty of information theory that you can prove these impossibility results. Any amount of compute, any any thinking, like, even Albert Einstein, like, the smartest person on Earth, cannot compress it better than because you can prove that you cannot do better than that. Uh, yeah. So, so, yeah, just remember your homework, decode it. Uh, and, uh, I will see you in the next lecture. Thank you. Happy to answer any questions.