Video 7-1: §7.1 Compression context

0:00 <Untitled Chapter 1>

0:03 welcome to unit 6 of comp 526 this is a unit on compression on how to represent text with using less space the outline is as follows i will give you some context what this is all about and we will look at a plethora of different compression methods i will also motivate why this is necessarily the way to approach compression and we'll talk about many of these some of which you've apparently seen already but i'm sure some of the more advanced ones you have not seen yet or not all of you have seen it's also another unit where i can bring you very close to the state of the art in research and definitely close to the methods that are used in practice for compression so even though we start with very basic things again putting the basic steps together in the right way gives you the state-of-the-art methods

0:13 Outline

1:07 for compression of say english language text and that's that's a really nice and beautiful outcome of this of this unit so let's get started with what compression is about if you remember the last couple of weeks and before the easter break we were talking about strings and string matching already and these units were really about how to work with strings if they are represented in a convenient format for us in particular we talked about extensively how to find substring how to find matches of a substring that are not exact matches but approximate we talked about other related questions finding repeated parts finding all sorts of more esoteric features that people have identified for example in computational biology to be of interest and we solved all these problems in one way or another but what we started with was assuming as a string is given as an array of characters where i can in constant time jump to the character at position one million five hundred thousand four hundred thirty seven in the next two units we will switch gears a little bit and look at how we can store and transmit strings in a sense this is something that underlies the previous units as well because we assumed strings before to have characters from some alphabet

1:20 What Compression Is About

2:45 but really to work with them we have to store them in the binary memory of our computers so it's inevitable to talk about how to encode characters at one point or another and that is part of of this unit as well but then the more important and more interesting aspects come into play when we try to store strings with the least amount of space possible and in the next the unit 8 we will also look at how to transmit strings over noisy channels when there's um a communication channel that that introduces uh bit flips and little mistakes how can we still guarantee a reliable transmission with very high probability uh that would be in a sense the opposite of compression you don't try to use as little space but you try to make it as robust as possible but they uh they turn out to use similar ideas and similar techniques um the methods are related in a way so that's why we discussed them together but for this unit we will focus on how to represent strings with little space now let me come to the question i already asked so here's our nice tag cloud of compression methods i see huffman coding huffman encoding huffman codes are well known a couple of people

4:14 also voted lzw the lymphocytic welch algorithm that we will discuss in detail um probably tomorrow and a couple of others um so i see there's lossless uh lcr i'm not even sure i know this one um yeah des is i think some some encryption methods yep and zip of course i was expecting many people to report zip or variance of it so any type of data compression method the ones that you use for sending well for sending data across the internet um chances are that it's actually zipped on the way somewhere in between um so these are these are really everywhere these methods they're you they're applied ubiquitously okay and some more esoteric ones as well um codecs for for video and audio cool uh thanks for participating in that one so uh you know what these things are you have seen a couple of examples um at least many of you and uh in case you have submitted none you will see plenty of them in this module i want to start with a bit of terminology so this is um just that we talk about the same things with the same names

5:38 Terminology

5:50 i'm not sure if this terminology is very universally agreed upon in the in the literature and on the web but for this module we'll we'll try to stick to it we always start with a source text and that will be denoted by s that comes from some alphabet sigma s and it can be of any length that's the thing we start with and we want to store or transmit it and what we transform it into is the coded text denoted by capital c and it comes from another alphabet sigma c and often we actually use the binary alphabet because we want to represent or transmit things on a computer but the terminology here or the methods are not necessarily tied to this choice even though it's the most the most prominent one we will the process of taking the source and transforming it into the coded text that will be called encoding

6:50 Encoding

6:56 and the process of going the other way around back to the source from the coded text that would be called decoding i think the terms are are probably self-explanatory but i want to be very clear and also i will use these letters s and c without explaining on the slides what they stand for these will always be source text encoded text another thing

7:26 we will focus on text because that's convenient and it's a nice formalism but it can actually be any anything in particular the same the same terminology can can well be applied uh to multimedia files to audio to video to pictures to uh time series of certain measurements to i don't know 3d data from make up whatever you want at the end of the day if you want to represent something in a computer you have to convert it to the sequential binary format that computers speak and so it's ultimately a text at one page at one stage or another you always need to represent things as a text so in a sense this is no restriction it's just starting at a lower level for for certain types of data

8:33 the other big um piece of uh the other big remark here is there's uh two types of compression really that differ substantially fundamentally in the techniques and in the ideas that they use and this is the question about lossy versus lossless compression the first one lossy compression is only representing the the source text approximately so you start with some source text you encode it and then you can go back to something that's similar to s in a certain sense but you will not ever get back the exact same as so this is what you usually use for multimedia data where as a human or even as an ai you are you're usually not not even able to tell the difference between those two if the compression has high enough quality so why bother recreating the exact same source text if all you want is a nice representation of that picture you took with your phone right so this is uh for media files where they are always just the approximation of whatever they whatever they capture are only an approximation of reality also the compression can be just an approximation of the exact source text

8:37 Types of Compression

8:46 Lossy versus Lossless Compression

10:02 the main thing here is you need a good notion of what it means to be approximately the same and this depends a lot on what you want you will remember mp3 for representing audio

10:15 well you will know mp3 for representing audio and that one is actually a very very crude approximation of the original audio file if you look at all the frequency bands it just happens to be that our ears the the human way to receive um and and process audio means that for us the mp3 coded version and the original source text version sound the same or very much the same but this might not be true for other animals for example so it this is a very specific thing and usually you have to come up with a specific idea for every type of media lossless compression on the other hand always has to come up with the exact source text as it was originally so you go back to the exact same source text bit by bit and uh in this unit we will focus entirely on lossless compression algorithms because these can be universally applied to all kinds of data you can always apply the universe the lossless compression without losing anything that's in the name and it can often be combined with lossy compression in a meaningful way uh and the second reason is the the techniques for lossless compression are very much algorithmic combinatorial in the realm of uh of this module whereas lossy compression would have to talk a

10:58 Lossless Compression

11:12 Lossless Compression Algorithms

11:45 lot more about perception about brains about specific types of data now we've seen there's different types of compression what makes a good compression what makes a good encoding scheme so a combination of encoding and decoding algorithms that entirely depends on the application uh typical criteria can be how fast can i encode and decode how efficient are my algorithms for doing that can i tolerate certain mistakes or noise in the transmission totally different thing is how about the security is it easy to decode if i maybe not want this to be possible by someone else do i require a certain keys to enable decompression or decoding integrity is it possible for me to detect whether some malicious third party has made changes to the coded text another thing and uh lastly that's where we will focus on the size of the coded text how long is the coded text can i compress it below the size of the original text so as i said we'll focus on the size of the text in this module almost entirely

12:01 What Makes a Good Encoding Scheme

13:15 so we try to find encoding schemes that minimize the size of the coded text and this is this is generally called data compression and there's a specific um quality metric a simple number that that people usually use to compare compression and this is just dividing the length of the compressed text so this is length of the coded text

13:19 Data Compression

13:49 divided by the length of the source text oh it crashed again that is annoying i don't know what the problem is today with this the uh compression ratio the method of the the main measure to compare how good a data compression works is taking the coded length and dividing it by the source length and that gives you a number now if the coded text uses a binary alphabet then the size of this alphabet is 2 log of that size is 1 so in that case you can just write it number of letters number of bits in the coded text divided by the length of the source text you might wonder why do we have this log of the size of the alphabet factor here we'll come back to this indeed but there's a simple argument behind this whenever you want to represent something from a set of n different outcomes you need log n bits to represent that if n is a power of 2 this works out nicely so if you have 16 different symbols to represent you can do that with 4 bits um for something like 20 different letters you would need actually five bits because you cannot do it with four and a half well arguably uh sometimes you can in a

15:51 specific way but let's not get into this discussion here we're computing the compression ratio we just assume that there is uh such a fractional bit representation for the letters so we just take log of the size of the alphabet ignoring the fact that this might be a fractional number and we might not be able to easily represent this in an array but for computing the compression ratio we still use it like that and the compression ratio is nice because it has this intuitive meaning if it's below one we've successfully compressed the text we've found a smaller representation the coded text is smaller than the source text if it's exactly one then we achieved nothing we're just as as space efficient afterwards as before and if it's bigger than one we actually made the coded text longer and unfortunately yes that happens we'll come back to that

15:55 Computing the Compression Ratio

16:17 Compression Ratio

16:56 before we come back to that i want to discuss the limits of algorithmic compression of lossless compression i want you to look at this image which is maybe something you've seen before is this image compressible the answer is tricky because on the one hand it looks like a very complex shape it sure is a complex shape i don't know if i can zoom in here a bit more to show this better you see that this is uh well you might know this it is a fractal and you can

16:57 Limits of Algorithmic Compression of Lossless Compression

17:33 you can zoom in in the original representation you can zoom in indefinitely in this pixel image that i created from it you can only zoom in to a certain point it is definitely a very complex shape and seems to have complexity in it however and and that means if you store this as a png image which is a format for storing pixel images that uses lossless compression

18:02 it if you do that it won't really compress very well but knowing where this is where this image comes from knowing that it is a fractal and in fact it's the mandelbrot set knowing this we we know there's a very small mathematical formula that tells you exactly what is the value at each pixel it's basically uh computing a certain value and mapping it to a color so we can generate this picture out of nothing with a very small program just specify the parameters what's the viewpoint what's the the color map and what's the formula so in a sense this program should be a valid compression of this image right and uh this is this is the idea behind kolmogorov complexity it says the coded text can actually be any program that outputs the source text so it's a say a java program or a python program and you have print statements that output the source text this is not so esoteric as it might seem at first if you remember self-extracting archives that was a big thing when

18:49 Kolmogorov Complexity

19:19 well when there were not so good tools and internet was not so widely available it was convenient if you use some more esoteric compression format to actually not just create a zip file but a self extracting zip file that contains the program to extract itself and yeah windows installers are similar to this still so this is this is the idea in kolmogorov complexity the coded text is an encoding for a program that tells you how to to compute the source text and then the kolmogorov complexity of a string is the length of the smallest program that generates that source text that sounds like a very sensible foundational definition of compression if you don't this is this is the the least restricted version you can think of because a program can really be anything but it has a problem and that is that finding such a smallest program is one of these uncomputable problems and uncomputable here means provably there is no algorithm that solves this problem it's mathematically proven that it's not possible to write a program that solves this task reliably and that is on any on any type of computer that we can build so this is a very strong impossibility result we've talked about impossibility results before we had a lower bound for sorting

20:55 work for comparison based sorting and we've talked about lower bounds in in other contexts very briefly that sometimes in computer science you can make very strong mathematically rigorous statements about certain things that are not possible and this is a strong thing that sets us off from from the natural sciences uh in many in many uh instances and this is another such an ex another such example it's impossible fundamentally impossible to write a program that finds the smallest program represent that generates a certain source text

21:40 but that also means there's no optimal encoding for this kolmogorov complexity it's not possible to write a compression scheme a compression algorithm that does this for all inputs that's a very uh discouraging result um but it also means on the positive side for u.s starting computer scientists it's also sometimes called the full employment theorem it means at least for compression and for other problems you will always need to be inventive and creative to get efficient algorithms okay so much for these limits so what can we do um what is this inventive what can we do what can the creative methods look like from what i will show you in this unit you will see lossless compression exploits certain types of redundancies in the source text and there's fundamentally two different types of redundancies that people were successful in exploiting the first one is when some characters are very infrequently used in a certain text they only occur very rarely then we should spend more bits on those because they don't happen so often and on the other hand make the codes for the characters that are very frequent shorter because we use them more often and that's a substantial boost for many applications

22:04 The Full Employment Theorem

23:16 and well the prime examples of this type are huffman codes for those of you who've seen that already the second type of redundancy redundancies which is more a more modern version are repetitive parts in the text so there's a certain text somewhere at the beginning of the file and much later may potentially there's a fraction a piece of of the file that looks of the source text that looks almost the same and that will be these repetitive texts that will also be something we look at that's what uh lemposif methods are used for um but we'll we'll see some more sophisticated ones as well

23:59 all right uh i'll stop with the introduction with a um with a piece of warning as you will see in the tutorials there's no such thing as a free lunch in compression it's in a again another pro another proven impossibility result is you cannot possibly compress everything it's not possible to find a compression method that always works and in a very strong sense so so again we'll have to focus on methods that are efficient not like the uncomputable kolmogorov complexity uh but also we'll have to focus on methods that work often we cannot potentially we cannot possibly guarantee something like they always work but for the type of data that arises in many applications they've proven very effective and so for this module this is what we will focus on