Video 7-1: §7.1 Compression context: terminology, Kolmogorov complexity

0:00 Intro

0:02 foreign welcome back to com526 efficient algorithms we look at a new unit again around strings but this time we'll try to squeeze space try to compress it and store text with as few bits as possible it's a little a different perspective from what we've had before but we'll see there are some connections um it's again a mixture of things you may have seen if you had some undergraduate classes then uh the first third or so you may have seen and then we cover some some more recent things again um that um find their use in uh up-to-date tools on for example the PCR tests uh binding little reads of of RNA in your genome things like that they make use of these techniques these days but before we get to that a few Basics first

1:04 Learning Outcomes

1:06 uh till the end of this um I wanted to understand a bit deeper what we've covered already a bit that characters have to be encoded as numbers in a computer I wanted to take away that there's limits at least if uh what we'll talk about will be um lossless compression so there's some some hard limits to what we can do and then there's a list of things little tricks and techniques um looks like a long list but some of them are really simple and easy I want you to roughly know what these are and the goal is as well give you a set of standard tools that you can apply and and tweak to a certain scenario because that's often what uh what you will have to do you have some type of data in an application that has certain properties and none of the methods directly captures that but with some slight tweaks or a combination of things you can um make use of that

2:16 all right let's start with a bit of context some of this I said already we're still talking we're still talking about strings the last couple of units were mostly about how to compute and we focused a lot on finding patterns in a long text in various ways right uh what we assumed in that uh in all of in all of these units was that our strings are like arrays of characters so I can in constant time Jump to character number 10 175. that's one memory access because I know the position so I have some in low level speak there's a pointer to the beginning of the string and then I add an offset and that gives me the character at that position that was implicit in all the algorithms that we used some of the algorithms don't need that they can also read it sequentially

2:17 Overview

3:18 in this in the next unit we'll briefly look at how to transmit strings and and save space there but a more recent Trend actually is to bring the two things together I'm not sure if I will have um time to talk about that much uh but the like as a as a little spoiler if you want um a lot of the things have been brought together with slightly more sophistication maybe than we can cover you can work on it on a text that's compressed and it's a little bit like if you had a zip file and you could still treat it as if it was uncompressed uh if you if you play around with a huge sip archive on your computer you may notice it looks like you can jump and pick out any file but what your computer has to do is decode from the beginning until it finds the file you're looking for and then copy that out and if you have a really really big archive or slow slow hard disk or something it takes quite a while and there are much better ways to do that but they haven't made their way at least into standard operating systems

4:31 because we're such a lovely mixed group I thought let's before talking about many of these methods let's see which ones you you know let's see let's say by know the how do we Define no having heard about it in some lecture that's probably a narrow definition

5:10 yeah there's a few um there are definitely coming up later again I deliberately made the question fairly vague like compression methods could mean many things some of the things you send are file formats uh which have some form of compression built in

5:46 some others um I'll just ignore it some others are algorithms that by themselves are not directly implemented but uh upon the basis of other things uh what you can't see again what you cannot see is the numbers so seven people sent lossless that's the biggest blob so overall it's still uh the the the sometimes these look like okay everyone has seen you know jpeg but it's really just two people the Graphics makes it looks a bit more more widely known or widespread uh okay

6:30 Terminology

6:31 I'll keep it open you can keep entertaining yourself if you if the rest is uh already known to you the boring bits first uh to make notation concise and to give it the mathematical flavor that I like like so much let's introduce a little bit of terminology first we'll always talk about a source text that's the thing we start with

7:01 and that will be called s and so we have a certain alphabet it's a string it comes from an alphabet so it's letters come from a certain alphabet uh and that's called The Source alphabet we write it as Sigma s because there's also Sigma C which is for the coded text now you will say hold on uh if we're compressing I usually just have some file on my computer it's binary at the end so why do we keep that General uh we'll see that sometimes the best compression methods result from chaining different things together and so there's intermediate stages where it's just more convenient not to go to Binary straight away so we'll keep it General question

7:49 um yeah for each compression algorithm was alternative medicine if you need to learn about because we have a string or main characters and you want to compress it to 2N minus one they are at most if only compressed half of the incredible so like basically yeah sorry so if you can't compare Sports when you have to conduct

8:17 some strings or we must call them must become longer a lot of pressure yeah so I want to cut you short there because it's part of the tutorials yeah uh the comment is you cannot always compress in the sense of getting shorter um I think I have some comment on the slide later as well uh but it depends a bit on the assumptions uh you need lossless compression um in the general case just some Source text goes into some coded text just to have names for the things and then well we say encoding goes from s to C and decoding goes from from C back to S

9:01 [Music] um now sometimes you can get precisely back the source text that you put in then we talk about lossless compression that's what we will um we will focus on but there's also lossy compression where you lose some information so the decoding is only approximately what you what you put in you don't get the source text back bit by bit but something close to it now uh you will ask what close means and I'll pass that back to you and say it depends it's usually useful for some for data that has some other meaning Beyond just the bits so multimedia in some form is is the usual and then jpeg is the one for pictures and an MPEG or well it's a bit dated but um newer video codecs uh do the same for video they try to exploit the usual type of um pictures and videos that people have so jpeg compression works well for for photos of real things if you put in a picture that has random bits read in black and white or what other color it wouldn't compress that well and same for video if every frame is completely different it wouldn't work well it exploits the fact that if you film some scene usually from one frame to the next from one picture to the

10:30 other there's only a small change or some movement that you can track but still these these formats are lossy they throw away detail in a way that is usually not perceivable or not perceived as a big difference by humans uh the thing is there's um at least as much psychology involved in these parts as there is computer science so I'll leave those out and we'll focus on the the parts that are a bit more amenable to these um fundamental rules yep yeah

11:21 like approximate preservation so this is most of the features that are important to humans yeah I'm wondering if the information preserved is also like objective in that okay these are the features that are actually like important if you try to like look at the it's like I could say like not necessary human Independence okay this information has preserved okay what is important or is it like arbitrary is it like I'm not like can you like terminate the how much information is lost Wisconsin right right

12:04 I would summarize the question as can you somehow take the human out of this lossy compression approximation I don't think so I mean maybe you can take out the human if you have a precise definition of what similar means and for some data that maybe that's that's doable um I mean I could make up an example say you compress English language text uh and you say I don't know I don't care about how words are properly spelled as long as it has the same phonetic pronunciation I I accepted that's somewhat well defined I guess it doesn't need a human necessarily let's let's pretend there's a single way to pronounce all English words right first abstraction then you could try to define something like that I wouldn't be super lossy I wouldn't be super interesting either I think that that part is closer to lossless compression of something else namely the actual pronunciation in that case so some sequence of uh sounds I mean um if you could just decode that and throw away the text I think there's an underlying lossless task hidden in there and the lawsuitness really often comes from the fact that we don't know exactly what we what we want to keep that's that's my uh my impression of the two

13:34 if you look very closely some of these definitions are a bit uh vague okay shall we move on from that part so for for us the goal will be lossless we want to do this for computers so they should get bit by bit back what you put in

13:59 What is a good encoding scheme?

14:03 then the question is uh you can you know you can cook up many things you can decide um today I'm doing it this way or that way how do can we touch whether an encoding is good and that again depends a bit just to make make that clear you could have different things like an encoding should be secure so someone who just sees the code of text cannot easily get the source text back that's one way of encoding you wouldn't normally call compression uh something like that that's called encryption usually but it's in the same framework well we'll talk in in Unit 8 a bit about is

14:42 uh what if you want to tolerate some noise in the coded text and still recover what you put in uh well we'll focus on here mostly is the size so we only care about how many bits we need that's what usually people mean when they say compression and to operationalize that a bit and give us a term we can work with we Define the compression ratio which is effectively the size of the coded text divided by The Source text but we have to be a bit careful because um we're working with different alphabets and so the proper way to define it is to take as many characters in the coded text Times log of the alphabet size because you you roughly need that many bits to write down one character If These are nice powers of two you can actually just write it down like that so the typical case as as noted here if the coded text is in bits then this simplifies log of 2 is 1. and for the source text we usually stick with the alphabet

16:02 now the compression ratio can be lesser one less than one or greater than one or equal to one in in general everything can happen and only when we have less than one we have actually achieved something in terms of saving space

16:26 can't you just like take the hash of the source and then we put it under like let's say you want to transmit a message you can just like send the hash of what the message should be and then the recipients can compare the message to the effectivity well sure yeah I'm not sure like I see the point to have like Integrity features in the including it so right okay so that's that's on this point the the question was can't you just send some hash of the message alongside with the message as a way to detect modifications uh I mean that's definitely a solution that people use right uh now it depends a bit what you mean by hash uh there's a hash by its uh hash is an kind of not not well defined usually you mean some cryptographic hash function like md5 even though that's broken don't use it anymore Xiao one probably still safe if you long enough and so on I don't want to get into these too much so if if these if you never heard about this they won't show up on the exam uh these are functions that are designed to be one way if you put a text in you get the value out but there's no easy way to

17:43 get a given value how do I have to change the text to get that value and that's important right otherwise if I just do a simple say a parody or some some simple function of the text count the number of characters say I can change the text so that the hash stays the same and you wouldn't notice that change so um I think what you what you suggest including this this cryptographic hash as part of the coded text that is the Integrity check right that's what what this means question yes

18:34 security yeah definitely yeah uh so we will we'll focus on the number of bits that we need or the compression ratio and so on uh and often often these things um several things are important but you can apply them one after the other you first zip your files and then you send them via encrypted email to your friend or I don't know if you still use pgp encryption if anybody still does or some other way of encrypting you can often separate things out and do one after the other you do not don't normally have to worry about them at the same time and again turning this into a cryptography course uh I'm tempted but let's not it's another big interesting topic with its own techniques that we will basically not touch on

19:40 Clicker Question

19:41 then um let's have a look whether you're this this looks like unrelated for now let me leave it without much comment for now uh it yeah look look it up it's a lovely little uh computational problem

20:32 I mean what about people are voting it's basically you have pairs of strings there's a top string and the bottom string and the question is you have a set of such pairs and the question is is there some way to take any sequence of these pairs so that you put one pairs next pair and so on and so on so that the top string if you read across all the pairs and the bottom string are the same is it possible or not you're given fixed set of pairs of strings and that's all I'm asking it turns out nope computer in on this planet can do it not even any conceivable computer in any of the computational models that we've come up with is able to do that because in a way these pairs of strings can simulate all computation that we know of

21:28 this is amazing um yeah that's a question yeah most of the uncomfortable problems and familiar with like rice Paradise departing program YouTube soft preference I think the PCP is the closest I could point out yeah uh

21:57 you're right many of these uh problems have this kind of diagonalization I think PCP is an example that's not quite as obvious of that kind we had 50 people vote earlier I don't know um shall we wait till 40 but it seems a lot of people haven't heard about it so in in short uncomputable problems or undecidable problems are just questions that have a definitive answer like this one that I just described if I give you pairs of strings either it's possible to somehow form the sequence of these pairs so that the top part and the bottom part reads the same or it's not possible because you somehow always produce more text in the top one and you can never catch up with the bottom string or something like that um but it turns out you can prove mathematically rigorously that no computer can solve these no computer given this as an input can come up with the answer either definitively yes or no and there's several such the halting problem is the most famous one no computer program exists that can take an arbitrary other computer program and inputs and tell you whether it ever terminates or not is fundamentally impossible and the reason for that is um that you can basically feed a

23:23 description of that program to itself that drives it into a contradiction you can create a program that calls this hypothetical program and does the opposite of what its prediction is and that way you can prove that it's not possible to have such a program in general again this is lovely stuff um did I post this veritasium video about the girdles incompleteness and so on on campus wire because that covers these as well it's uh in the later part of that video it's lovely Theory and so on uh we don't really need that here but I thought uh depending on how people how many people are familiar with this um I might point point out a few connections there

24:10 Limits of algorithmic compression

24:14 it comes into uh the the topic of compression in the following way if you're given some data for example the image on the right you can ask is this compressible again in the sense of lossless I don't want to throw away information I'm not interested in jpeg or PNG or something like that here can you compress it and well if you look at the picture it looks complicated some areas are maybe this is all white so maybe that's all right but then the rest looks pretty complicated and you know these fractals you zoom in right and it becomes exactly

24:59 get equation that creates that property instead of like storing yeah that's exactly the point in one way the image is really complicated because even just predicting what the color at a certain area is is quite tough on the other hand there is a fixed formula that generates this image in fact this one was generated by a fairly small program and you can make that generate as much resolution as you want so what should the answer be is the image compressible or not in a way yes because it has a small program that generates it and so the most versatile com notion of compressibility is give me a program that generates the data for me and the size of that program is my code it's a fairly intricate code that's much different from zip maybe a self-extracting zip archive comes the closest but that's really just a little a little piece of program that tells you how to exactly handle that specific file format it's by far not as sophisticated as this one would require so the most General notion goes by the name of kolmogorov complexity and it's it just says ultimate compressibility is the length of the smallest program that produces the data in terms of prints or something like that now that sounds sounds great right let's

26:24 just use that I mean why not um and the problem is that finding this complexity is uncomputable in the same sense as these other problems I mentioned before it's it's completely hopeless in that sense question yeah

26:55 yeah yeah yeah so if you have like a more like a short program for a let's say you have like a short program for to print an image in the possible language University language

27:22 does it yeah what I should have said is I glossed over what a what that means what's the length of a program uh I mean you're probably thinking of some Python Programming it's just the length of the source code right but you could maybe write a shorter Python program that does the same and in a way uh this made it sound like it doesn't depend on the choice of python over java over whatever else and in a way there's a general theorem that tells you in an asymptotic way it doesn't depend on the language uh but there's a lot um hidden here in a way any any proper language would do as a definition here doesn't matter too much but it's also equally useless in the sense that you any proper computing programming language would also make the problem uncomputable and that's why we haven't dealt with the topic yet that's why there's many of these methods following what people have done instead of going for the ultimate compression is find tricks that exploit some redundancy in the data uh to get smaller representations and so the focus is on things that always work can always be applied but might not always reduce the size as much as possible but that's the best we have

28:46 What makes data compressible?

28:49 so we can ask what what is what are features that can make data compressible in in a sense that we can deal with not in this uh there's a hidden fractal if you look at it through the right in five dimensions and through the right angle uh things that we can easily find and those two things we'll discuss one is remember we're talking about text if some characters are much more frequent than others we should try to take advantage of that for example English text has lots of E's and not so many sets so you should try to give e a shorter representation that's a simple thing you can do sure and the other yep question

29:37 see for example I know that I miss I know that there exists a from a version of that screen that is just the strings so yeah so something you could do which is you search over all programs that are less than n as if you find because like start from such an overall program document one and I'll come out of them to see we find them yeah and that is not incomputable but like it's a finite set although it's like not efficient but the problem with that is okay that I think we have to stop the digressions as fun as they are but then I'll this list last one so the question was suppose I have a string of length n can I just enumerate all the programs up to that length yeah and then I should find if there's a shorter one first

30:29 sure sure I mean the problem with that is how do you decide whether a program that you've now looked that you're now looking at generates that string in general there's nothing better than running that program and it might never terminate and so that's how that fails yes I mean I appreciate the attempts um it won't work eventually in the general case that's that's quite that's proven already but maybe it's it's helpful to think about these things a bit so keep keep going just don't try to reach for the impossible so that's something that I'll I just um announce here and you will work on this in the tutorials a bit uh there are certain I call them no free lunch theorems for compression some things are just utterly impossible it looks like you can always compress but what I what I encourage you to do is take whatever data zip it take the zip file zip it again have you ever done it like Zip is great right it should compress so if you zip it again it's even better anyone ever tried it

31:44 well let me just want display you want to try try it out and tell us what happens that's a different problem yeah so zip bomb is a good thing to Google that's the opposite direction you can have a very small file that unzips to a absurdly big thing yeah that's all right

32:10 I would call that a great example of compression right it means sip works it can massively compress some borrowing files what happens if you zip a zip file again is it gets a little bigger not much but a little bit and I guess internally it basically is there's some Header information and then the rest of the file remains roughly unchanged