Video 7-1: §7.1 Compression context

0:00 Introduction

0:03 okay welcome back to comp526 this will be the second big unit where we talk about text after the long unit on text indexing last time this time we'll talk about compressing text and this will also keep us busy for a while then if you're afraid that we'll keep going like this the the remaining units are much smaller uh six and seven are definitely more than a week's material and eight will be quite quick and nine will be quite quick and not part of the exam so the bulk of the material is is done after this one but not so fast we have one really exciting unit to go uh again i love this unit there's quite a few really cool concepts in there again if you stitch them together they appear to achieve quite remarkable things but each individual one is doable with

0:57 sitting down a bit of caffeine and and some some patients maybe let's dive into this what i want you to take from it are a few things um i want to talk about the um the basics i want you to take that from from this unit that you know what's behind ascii and utf-8 and unicode and more more generally

1:03 Objectives

1:22 i want you to not only be able to right-click and say zip i want you to understand what are the limits of what can compression do at least lossless compression and we'll look at

1:35 a collection of methods that people have invented to compress some of them just real quick but i think it's it's useful to survey those a bit so that you know uh what is available how they belong together and what what their properties are and then um a last one on the application side of things so the the higher level of the bloom's taxonomy if you want i want you to if if you have some specific scenario i want you to be able to figure out what could be an effective way to compress this specific data that you're that you're dealing with because that's most likely to be the scenario where you would craft a new way of compression many of these techniques we'll talk about are good general purpose compressors but if you know more about the data you're dealing with sometimes you can outperform them

2:29 Subsections

2:30 okay i divided this up into a lot of subsections so each of them shouldn't be too long uh and you see in many cases this is really one one subsection that should be won by topic but i split it in two to have uh bite-sized chunks videos or well big bites sometimes 20 minutes each roughly

2:56 Why compression

3:00 let's first talk a bit about why we use compression what we use it for and a bit like in the string chapter in unit 4 a bit about the notation that we'll use so that we're all on the same page for this

3:15 we've been talking about strings for a while now we've been talking about finding patterns in a long text that was units four to six especially units four to five we were given the text the pattern and then we tried to find something unit six we will try and to build some data structure out of the text so that the pattern searches afterwards become faster and now we'll shift the focus a little bit from working on the text to storing and transmitting the text so we try to be more frugal on space that's what compression after after all is is about but it's not only that it also means often if you compress the data it also becomes faster to work with it and that often has to do with the fact that on modern machines accessing memory or if it's over network even more so the bottleneck is getting the data to you not so much working on it in many cases

4:17 okay the the way we store and transmit strings is about computers we won't talk about analog measures or analog ways of transmitting data here so everything has to be binary at the end of the day we want zeros and ones because that's what our computers can work with uh there's a for the transmission side there's an orthogonal axis if you think about uh well wi-fi communication or the cellular network there's interferences and you would like to transmit even if the the channel your the medium you're communicating over is is kind of noisy lossy and it's not perfect we'll briefly look at unit 8 and a simple way to do that that's kind of complementary to compression you first want to compress the data so that you minimize the amount of data you have to send but then you probably also want to build some redundancy in again for the transmission itself but this depends on the medium if you communicate over a very reliable network you might not need this or you might only need a very little bit of redundancy so for this for this unit we'll only focus on the part compress the data we have as much as possible and assume the the storage medium or transmission medium is perfect

5:43 Questions

5:45 so much for the context where this fits in um i want to briefly show this for the video again so i asked you what types of compression algorithms you already know and a few people knew huffman codes many other interesting variants and a few that i don't know

6:07 there's a few terms also lossy versus losses that we'll pick up okay before we keep talking about this let's fix the terminology so that it's clear what the vocabulary means that we're using in compression there's always a source text that we start with

6:13 Terminology

6:34 and then we compress this to a coded text and of course compression algorithms are only useful if you can also invert that process if you can get back from the coded to the source and that's then the decoding step so source source text encoded text is data and encoding and decoding are two algorithms okay um what's to be stressed about the source text it can come over any alphabet whatever the user or the application dictates is useful

7:29 we'll often assume that this is ascii or the unicode alphabet but it could be different could be rna sequences dna sequences so that's a smaller alphabet the thing is we don't have really control over the source alphabet for the coded strings

7:48 for the coded strings we determine what we want to use but almost always we'll use binary because we want a binary representation but we'll sometimes deviate from that because good compression algorithms often are a chain of different things so you first apply some algorithm that spits out some intermediate representation which is fed into another algorithm and so for this first step it might make sense to not immediately go to binary but to go to something else that's why we keep it general in in here okay so these are just these these two alphabets um any any questions so far

8:34 compression can be lossy or lossless and it depends on the application what makes sense in lossy compression this arrow back going back to the source text means only in an approximate sense so you can get something that's close to the source text back but not exactly the same so the prime example is all sorts of multimedia that you know and i don't have to explain much right if you if you take a picture with your phone it's immediately compressed to jpeg if you have a fancy phone it might also store this raw data format so if you have a proper proper camera and that stores exactly what the sensors in the in the camera give back without compressing it and there's more color depth and more information in there whereas the jpeg loses some of that information but the file size is more more reasonable then

9:30 so that's often what you do for multimedia and we will not look at this here that leads us too far and in particular to do this you kind of need a way to tell when are two texts when the two pieces of data is similar enough for you to accept it and that's highly dependent on the data if you look at pictures then it's not even clear if you can formally define this but if you show it to two humans and they say yeah this looks prompt looks the same to me that could be a measure it's not so good not so easy to automate this so in a way um we'll avoid this by only looking at lossless compression here

10:14 so we want to get back the source text bit by bit or character by character as it was no deviations allowed and of course the benefit is that you can use this wherever you want to deal with data there's no no implication of using the compression in between is transparent to the application the downside of course is as you may know uh from black audio versus mp3 or something like this lossless compression has higher compression ratio just because it can throw away information there's limits to what lossless compression can achieve by contrast and we'll talk about those limits

10:56 Different compression methods

11:01 there's many ways how you can determine for the different compression methods that we'll talk about which one is better than another one i just want to list different ways to look at this here we will mostly focus on the size so we want to get a coded text that's as short as possible but there are other dimensions in applications that might be even more important depending on on what you need it could be more important that things are fast that's say you build a little hardware router that has to forward gigabits ethernet traffic you can't spend a ton of time compressing each packet you probably just want to forward it as quickly as possible but if you can build something that works fast enough and compresses a bit that might be might be good we'll talk about this in unit 8 some some compression is slightly more suitable if there are errors in the transmission but again the proper way is rather to first compress and then apply other techniques

12:06 a completely opposite topic something close to compression is encryption from cryptography there the goal is not to make the coded text smaller but to make it jumbled and hard to read for someone that it is not intended for there's many similarities between compression and encryption but the the key difference is the size is not the big concern for encryption but rather it has to be hard to invert invert without the key

12:37 integrity goes a bit hand in hand with that we'll not really look at that today so we'll focus on the size and we'll measure the compression quality in terms of the compression ratio you probably have an intuition what the compression ratio is it's the length of

12:40 Compression ratio

13:01 so this is the length of the of the coded text so it's it's essentially dividing the size of what what comes out dividing by the original size but we have to be careful how we measure size because we have strings over different alphabets so if if i'm encoding something in binary i need more bits i need more characters than when i'm encoding something with a huge alphabet where each character has many different up different possibilities and the proper way to include this is to take the log of the size of the alphabet because that's the number of bits you need to specify any single character if you don't do anything more complicated so we'll just define the compression ratio like this the length the number of characters in the coded text times the log of the size of the alphabet and for the source text we divide by the number of characters in the source text times the log of the alphabet size again and of course in the typical scenario where we encode to binary this is just one

14:30 the compression ratio should really be below one that means we have achieved something we made the thing smaller than it was before if we keep it at one we haven't really gained much but at least we haven't lost anything if it's bigger than one we lost something then we made the text bigger that sounds not like compression but we'll see that this is effectively inevitable

15:06 now that we have a way to say what is what we would like to achieve we want to minimize the compression ratio we might want to think about how good that card possibly can be

15:19 one thing that's um like in like in previous uh like in in previous units we'll uh have to think about whether we're talking about the worst case or average case or best case for compression ratio we usually talk about the given case so we have a specific text and we look at that one but for an entire compression algorithm we would ideally like to have a statement that is always as good at this and we'll see how far we can get towards that

15:53 Ultimate compression

15:57 there is another another take on this which comes from a completely different idea and so you might recognize this picture as something you may have seen does anyone know what it is

16:18 yeah it's a fractal uh is i think is is the mandelbrot set so it's uh well it's related to a specific equation and you can give it nice colors by the number of iterations you need to reach it uh it's an innocent question here's a picture can you compress this losslessly and suppose i'm fixing the resolution to a certain number of pixels so it's it's quite well defined but can you compress it or not if you look at the the picture as it is and use png as a image format that does compression but lossless compression by default uh if you fed if you feed this image into png it won't compress much a little bit because png will pick up that there's areas here where the picture is almost just one color over a large range but there seems to be these highly complicated regions that are or png not really compressible

17:27 but the amazing thing because we know where it comes from is you can compress it very much to a really tiny program because this picture after all was generated by a computer program so wouldn't the ultimate compression be just that program so you give give me a program that produces the data that's the ultimate compression because it's the best you can possibly achieve in a decompression step decompression has to take from a certain input and here the input is the program itself the decoder has to somehow take the the coded text and produce the original source now an absurd limit of that is i don't code anything at all the coded text is is the program itself and you just run that to produce the source again that is an option and uh people have studied this it's known as as kolmogorov complexity um so the the size of the smallest program that outputs a given source text that's its common growth complexity uh you'll have to be a bit careful what types of programs you allow but suppose you fix our our good old ram model or a turing machine there's ways to make this very formal and then you can study it but this there's a um there's a big cave yet with this and

18:54 now for this one uh it depends on your on your background if that statement makes a lot of sense to you uh it turns out finding the shortest program is a really hard problem it's not just slow to compute it it's utterly impossible it's an uncomputable problem so you may have heard of the halting problem the the question here's a program and an input does this program terminate on this input and alan turing famously showed that there's this is impossible to do uh it's not just that it takes a long time or so it's with the computers that we envision envisage it's completely impossible to do it and the same is true for finding the kolmogorov complexity of of a given input in general at least so we have this wonderful notion of ultimate compressibility which is also utterly useless because you can't even evaluate it you can't even here's a given a given piece of data tell me how complex it is it's impossible to answer this question with a computer at least in the general in the general case there's no program that always works

20:17 so in a way the whole rest of this unit if you want is trying to work around this try to get on the one side statements you can't possibly compress data like this more than that at least under some assumptions and on the other side complement that with [Music] concrete compression algorithms that work reasonably well for many types of data and you can show that they achieve certain achieve certain guarantees okay this is all without making this concrete i think it's not not so useful uh you can try to work on on both sides try to show that you can't compress more than that and give algorithms that compress to a certain degree but we'll have to live with a certain impossibility here we won't ultimately solve this there's always the possibility that you can come up with a slightly smarter compression algorithm that just approaches the problem differently

21:23 okay so it seems it seems pretty tough uh if from from looking at data even as a human it's hard to figure out if it's compressible or not maybe we have to be a little less ambitious and instead of trying to capture ultimate compressibility we'll look at certain features that definitely mean that data is compressible in some way and we'll focus on on two types of redundancies in the source text that make it make the source text compressible

22:00 one is that if i called this here uneven character frequencies because i didn't want to throw around terms that we haven't introduced yet the idea is suppose you have uh english text there's just many more vowels and e is much more common than what's least common in in well x q q is probably not too common x not too common but what i'm getting at is some characters occur much more often than others and at the moment or the the trivial encodings that will that computers use and we'll touch on that uh they don't make any any use of that and the second way things can be uh redundant is if there's repeating parts that's maybe more intuitive the second part if there's the same text appearing twice then there should be a way to just store it once and refer to it back

23:07 that's the core idea in in the second part but making this automatic so that it always works uh is a little tricky also i want to point out if you take your worst case classes out and you ask i have some compression algorithm what's the worst case compression ratio of all source texts of a certain length say you will be very disappointed because that is always worse than one

23:40 it's in a sense with lossless algorithms it's impossible to always compress and this is a very simple kind of a very simple proof that you'll do in the tutorials after you've seen it you will say uh yeah of course not but it's kind of insightful to do it so uh i'll refer you to the tutorials for that but if this sounds like surprising that um zip doesn't always work in a sense um wait for the tutorials and a funny experiment that you can do in preparation for that what happens if you zip a file and then zip the zip file again has anyone ever done that yeah

24:36 so if you zip it again it doesn't get any smaller if you pay close attention to the exact bite count i think it actually gets bigger ever so slightly like it's not very noticeable but if you keep doing it first of all it doesn't improve and second it actually gets slightly bigger and that's ultimately because of this there's just no way that if zip didn't pick up the redundancies in the first round it won't pick up pick them up later and there's there's files that are just incompressible

25:09 all right i should say for each compression algorithm there are files that are incompressible it's not that there's one hardest file that is incompressible by any algorithm that's a different statement and that would come down to kolmogorov complexity of that string which we know is very hard to get at but for every compression algorithm you can find an input where it utterly fails but this might be a different input for different algorithms