Video 5-1: §5.1 Compression context: terminology, Kolmogorov complexity

0:04 welcome back to efficient algorithms com 526 in unit five we'll talk about data compression and various nice nice techniques that relate to what we talked about in string matching and will lead to um more advanced text indexing later

0:28 on the goal for this unit is that you know basic basic stuff about how to represent text in a computer like uh the ne necessity for character encodings and what is what is standard to use there um then on the other end of the spectrum there's some clear impossibility results and you should just be aware of them so that you're not fooled into uh believing strange claims say uh and then we'll look at a few concrete wellknown and widely used compression algorithms or codings uh listed here and uh you will see them while we go um the last bit is is maybe the most interesting for assessments as well I'd like you to be able to take some of those uh existing techniques and slightly tweak and modify them or at least apply them uh when they are useful so as always like in the past units the goal is not just to understand how these methods work but also what their properties are your goal in graduate level jobs won't be usually to implement an existing algorithm that's already invented and has been out there for decades there is an implementation in most libraries what you are for is for understanding what's inside the blackbox so that you can use it effectively and uh um competently where it's where it's

1:49 useful and know its limitations so nothing new on that front um that's the that's the overview it's it's mostly uh subsections for the different types of of compression methods uh we'll get to that um before we do though I want to again set the scene and give some notation that comes comes up in the remainder of the unit and also give a little bit of context and motivation for this for this whole

2:23 thing in unit four where we just came from string matching we looked at how to work with strings and we'll we we will come back to that in unit eight when we talk about text indexing so there's various tasks you can look at what to do with strings well now we've looked at how to find exact matches of a pattern but there's related things you can also do uh our assumption was always that we're given the string as an array of characters so we can basically jump around with random axis So Random axis again meaning I can jump to the 17th index in in one step I can uh use indirect addressing for that uh in this in this unit and the next one the focus will be slightly different um we'll instead look at how to store or transmit strings so not necessarily compute on them but uh pass them around so uh for a computer that means everything is eventually binary that will usually be our our point to to stop as well uh in this unit we'll look at how to save space so uh reduce redundancy in in data uh in the in the second unit on this part unit six we'll look at how to transmit over noisy channels so a little

3:41 bit of of error correction in there now I also want to mention that uh a Modern Trend is to try to combine the two things something I'm I'm researching in as well how can you store things in a compressed form but at the same time compute on that representation without decompressing first so the traditional Paradigm is this split you either worry about how to compute with with your data or you worry about transmitting it or storing it to disk and the the algorithms are separate and the kind of new paradigm or upcoming Paradigm that becomes more relevant is uh to compute directly on the compressed representation um but we'll at most touch on that briefly

4:31 I asked you up front what compression methods you know and there's uh a big collection so there uh there's different classifications that I'll I'll come to in a second lots of archive programs uh that you can use to uh compress files in a file format um and then also specific algorithms some of which you've seen in the outline so we'll come back to some of of those yeah arithmetic coding is is a lovely one always wanted to put it in this unit but it was too full

5:13 already so there's some knowledge in the room um but we'll start from from basics for this part uh so first first discuss some some terms we have two types of texts when we talk about compression algorithms we have a source text which is what we start with and we call that S capital S all the time it comes from a certain alphabet The Source alphabet if we have to specify it and can be of arbitrary length and then we have the coded text which is the output of our compression of our compression algorithms um we'll denote that by Capital C and it can come from a different alphabet often the coded alphabet will be binary but there not always the case because sometimes we'll do a chain of algorithms one after the other and so uh the coded alphabet for one method could be the source alphabet for a second method and so maybe only the last step is to go all the way down to Binary and we'll have two steps when I when I say compress we usually think about just this taking the source text to go to the coded text but it's only half the story the life is only really interesting if you can go back from the coded text as well to the source

6:34 text so there's the two inputs and there's two algorithms and the Order of the role of input and output is swapped in the two cases there's two very broad categories of compression algorithms they can be lossy or they can be loss lless in lossy compression the decoding if you go from The Source text to your coded text and then back via decoding you only only get some uh approximately equal Source text it's not exactly the same and um you have to specify with some domain knowledge what is good enough so they should be

7:23 similar but what that means formally depends on what you're doing so usually lossy compression is done for some uh multimedia formats or well just media formats so images videos sound all that where even the source text in binary was just uh an approximation of some real world thing so if you take a picture with your camera it's not the same as what you were seeing at the time it's just a some representation so it's acceptable to modify that representation if it still looks the same to humans so uh in in this case um similar would mean a human being cannot easily distinguish the two then that's close enough even though if you compare them bit by bit they might be very different now in this unit we'll uh in this module will'll not look at lossy compression so that's kind of um a separate topic because it needs much more domain knowledge it has to be specific to a specific application uh it's not to say that it's not interesting um so what's behind all these um is is another cool topic but not for this module instead lless compression reproduces uh the source text bit by bit in exactly the same

8:52 way so if we restrict ourselves to lless compression then the question can still be what is a good encoding scheme or a good compression algorithm um I'll I'll use these two terms synonymously so a compression algorithm I always mean that there's also a deco decompression or uh yeah decompression algorithm decoding algorithm so uh encoding scheme makes it a bit more explicit or we think about encoding and decoding but the two terms mean the same for me uh there's again depending on the application different goals we can have um we will most just focus on the size of the encoding in this case for this unit at least that's all we care

9:41 about um and we have a specific way to measure this and that's uh you can be expressed in terms of the compression ratio and so we should we should briefly discuss um what is the size of a string now uh the length of the string as the number of characters is definitely part of the

10:12 equation so if I have some string uh sorry element and here I'm using the notation Sigma to the end remember that's a string of n characters from this alphabet

10:30 Sigma we could just say that's the length of the string H but if we ignore how many um symbols in the alphabet there are you can cheat you can Define um the coded alphabet to be Sigma to the N just the all endles of characters and then your coded text could just be S with a as a single character and so it would have size one you compressed it down to one if that feels like cheating that's because it is cheating uh you can't ignore how big the alphabet is if you think about writing this down in binary you have to somehow encode each character we'll come back to that in a second in much more detail but uh to just cut that discussion short we'll multiply the length of the string by log of the size of the alphabet as an approximation for how many bits you need per character now for the experts knowing arithmetic coding arithmetic coding actually achieves this to a good degree we'll see um methods that come close to this but not but not quite for the computation of the compression ratio we ignore this that's just a rough number so we just take the length of the strings Times log of the size of this alphabet and uh then we take the ratio

11:53 of those two of those two things the coded alphabet the coded string and the source text often when the coded alphabet is is 01 then of course log of two is one and so this simplifies to what's here and the way to interpret the compression ratio is uh if it's below one then that's good then we made the overall information less we found some way to compress um but it could also be that it doesn't compress or that it even expands so sometimes you try to compress and the output becomes bigger uh so little little fun question on this um has anyone tried what happens if you zip a zip

12:46 file maybe do it it's a fun experiment think about what should happen and um and then you can explore it uh I think it's a good it's a good little motivational exercise

13:09 there's another another question I asked you earlier before we even started with all of this so uh very likely you won't have to um answer this again I want to briefly connect compression to some theoretical computer science topics that I think here um very well motivate why you want to study those in a computer science undergrad degree and uh for the conversion Masters why you should at least have a little glimpse of what they

13:48 are and the connection is as follows if we think about compression as a general way to um to reduce reduce um redundancy or information uh you easily come into the realm of this of these questions so here's here's an image I suppose many of you will know what that image shows it's a fairly well-known one um the question is is that compressible now of course you all you all know about JPEG and other more more modern compression methods for images okay jpeg is not what I want because it's lossy but there is loss less compression methods like PNG has a kind of compression method built in for images is um and there's again more advanced modern uh web formats for image compression I know all that but is that the best we can do can we compress that image further um on one side it's an intricate shape with lots of little detail which often means it's hard to compress so if you if you use PNG for this it doesn't compress it very much maybe the parts out here where it's almost the same color it will compress press but uh these intricate details here no on the other hand you know where this comes from it's a fractal it's called the mandle pro set so there's a formula

15:09 to compute that image and it's a very short program actually so uh I mean look it up on Wikipedia if you've never read about this uh you can find lovely visualizations online and so on that's uh it's a lovely math topic that has nothing to do with with the actual content here all I'm getting at is there's a very short program that produces exactly that image why don't we take that short program as its compressed representation the program is much shorter than a p&t representation if I take the high resolution version of this image so it's much better

15:51 compression and this is what people um observed or what what people studied uh and it it's been given the name korov complexity or uh um descriptional complexity if you're given if you're given a text a source text S the color complexity is the length of the shortest program that produces that output so think of a a little Python program with lots of little print statements in there and you want to find the shortest Python program that produces a given text now it could just be print here's the text that always works and it's roughly as long as the text you you started with but sometimes as in the case of this image uh you can compress it much better by exploiting where the image comes from you can write python code that computes the fractal from its formula and then it's a much shorter code than representing the image explicitly that's kind of cool because that's in away the definitive answer to compression any any kind of decoding algorithm has to be an algorithm that produces the text again so if I take the shortest such program that's the ultimate

17:11 compression so why do we have a list of different compression methods if there's a single answer for the best possible compression well the the unfortunate answer is that uh color complexity is is undecidable or uncomputable you can rigorously prove that there's no algorithm that always tells you the shortest program and so it I mean the pessimistic point of view would be it's utterly useless uh it's an ultimate measure of complexity that you cannot use at all because there's no way to find or compute that measure um so the positive take on it is well okay we have to find methods that work well for the type of data we care about um maybe this is only a worst case statement there's no algorithm that always works to find a good compressed form but that doesn't say we can't find methods that work well in many

18:25 cases uh before we come to to that let me uh point out something slightly related I just want to mention this as a little bit of motivation does anyone know about the hter

18:43 price okay does anyone know about I AI XI the is is a an artificial intelligence uh Theory um where this uh this person hter is involved so compression as we've seen this color complexity the idea um it seems to be getting at some fundamental question of is there structure in a given text and that in a way is also what artificial intelligence has to do about its environment if it somehow shall be able to predict and act according to its inputs it somehow has to uh extract the structure of the environment say learn the laws of physics in some sense that's a form of compression and there's a a widely ranging statement that essentially says uh if you solve the problem of optimally compressing your environment then you've actually solved the problem of compute of constructing the best possible General artificial intelligence uh if you want to read more about the formal the formal version of that you can do in in Hud's book uh the price is um motivated by that where he said says okay let's try to um operationalize that a bit if you take a 1 gigabyte of Wikipedia just the text of some articles and you can compress this to uh something much smaller than before then you must have learned something about

20:14 what makes Wikipedia articles what makes human text what makes human knowledge maybe even more and so he set up this competition and you see it's it's very active just uh this summer someone improved it by another little bit and earn five grand for it so just as a little um as a little note aside uh compression can sometimes be just uh the dry Act of compressing your uh zipping your your submission before you upload it to Canvas as you will do for your assessments right uh but it is actually a very deep theoretical topic with lots of implications um all right right but coming back to uh the module um here will will be a little less less ambitious um if we can't always compress in the ultimate sense um we can instead ask well what can we do and lossless compression methods that exist usually come in they kind of fall into one of those two categories most of the time they either exploit that some characters occur more often than others or they exploit that there's repetition in text in the sense of certain things occur almost literally like that before and those are the two key parts that we'll exploit I also want to point out at this at this stage uh another negative result

21:50 um that you'll cover in the tutorials in more detail um you cannot always compress if you want an algorithm that works all the time it has to make some things bigger and that's also why I asked you to to zip a zip file and see what happens uh I mean I I can spoil it and say it gets bigger every so slightly and you can zip the zip file the zip zipped uh the zipped zip file again and it gets ever slightly bigger again and so on maybe at some point it stabilizes but that's one kind of example that illustrates this there's no PR lunch in this case