r/askscience • • Jun 17 '12

Computing How does file compression work?

(like with WinRAR)

I don't really understand how a 4GB file can be compressed down into less than a gigabyte. If it could be compressed that small, why do we bother with large file sizes in the first place? Why isn't compression pushed more often?

414 Upvotes

146 comments sorted by

View all comments

902

u/CrasyMike Jun 17 '12 edited Jun 17 '12

If it could be compressed that small, why do we bother with large file sizes in the first place? Why isn't compression pushed more often?

It is. Compression is everywhere. Installers, most internet traffic is compressed, nearly all music and media files (movies, music, pictures, you name it) are compressed.

The reason not EVERYTHING is compressed, and why sometimes "poor" algorithms are used is because the computer has to compute the uncompressed form.

So, basically, it's an economic trade-off. One resource is disk space/bandwidth depending on what is going on. Storing files we'd be considering disk space (ie. compression of a video file). Transferring files we'd be considering bandwidth (ie. compression of internet traffic). Both of which obviously costs money.

The other resource is CPU time, which also costs money (as a sort of opportunity cost, if you use up CPU processing to do compression you could have been doing something else with those cycles).

Basically, the idea would be to spend as little money as possible (or possibly provide the best user experience where compression might be faster/better for the end user). We don't want to go crazy with compression to the point where so much compression is done that our computers are spending all of their processing power trying to figure out what a file is, but we want to do as much compression as possible to use as little disk space/bandwidth as we need to.

What is happening?

Consider this boring, stupid paragraph:

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.

Lots of repetition in there eh? Repetition is wasted space when we're talking about compression.

What if I told you:

1 = I

2 = play

3 = like

4 = fun

5 = amount

6 = have

7 = to

Then I can change the sentence to:

1 3 7 2. When 1 2 1 6 4. The reason 1 2 is because 1 3 7 6 as much 4 as possible. The 5 of 4 1 6 is based on the 5 1 2.

Nice! Lots of saved space, but it takes extra effort (CPU power) for you to read it. You can learn a few things about compression from this:

  1. Obviously you need the answer key up there to read the sentence. The answer key does take up extra space, but what if the paragraph was an ENTIRE book? You can see how the "2 = pla"y would save space compared to writing the word "play" 500 times. In the case of certain types of data you could see some data repeated thousands and thousands of times, and we can change that data from "play" to "2" thousands of times. 3 letters saved per instance of the word "play" * thousands - "2 = play" saves lots of space. (think HTML, where the same tags are repeated A LOT)

  2. If the sentence was any shorter nothing would get compressed. If the sentence was just "I like to play" there's no repetition to compress. There's no point in doing any compression. This is the reason why small files cannot be compressed very much at all, but in a 5gig file you can see A LOT of compression.

  3. Some things shouldn't be compressed. What is the point of compressing "I" to "1". There's no point! I save no extra space by changing "I" to "1", and then use extra space adding 1 = I to the key. An algorithm for compression tries to take this into account by not compressing "I".

The same thing applies like #2. Why say 8 = possible, then replace possible with 8. Either way I had to write the word "possible" once in my data, then added extra space for the key. If the word possible was written more than once, then we could see a purpose.

4) You can see we saved space, but the sentence is much harder to read. Computers are VERY good at putting things into order and into the right place though. It could be a matter of milliseconds to take the key and throw the words into the matching places.

Then there's lossy compression,

This is things you are familiar with like MP3 files, movie files, etc. The idea is to do regular compression, where we take those two sentences above to the new compressed form, then we decide "CLEARLY playing is fun. We don't need that sentence at the end".

And the compression algorithm deletes it. It would be like taking:

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.

and changing it to:

1 3 7 2. When 1 2 1 6 4. The reason 1 2 is because 1 3 7 6 as much 4 as possible. The 5 of 4 1 6 is based on the 5 1 2.

and then deleting some data:

1 3 7 2. When 1 2 1 6 4. The reason 1 2 is because 1 3 7 6 as much 4 as possible.

Now that data is GONE. It does not come back. The algorithm basically decided (because this is a magical algorithm that knows how to read words) that the final sentence wasn't really needed. This happens in MP3 files, when the algorithm chops out a lot of data points, pitches, and refinements in the music because it figures that it can cut it out with the lowest effect on the sound quality of the music.

You can see it in bad compression on movie files, with those jaggy lines and blocky look. You see it on Youtube, when everything looks blurry and jaggy. You see it in a bad .jpeg, where a lot of the lines look jaggy. That is the algorithm going "Well, instead of making this line curvy....a couple of blocks diagonal from each other basically looks kinda the same"

The more we do lossy compression, the more data we lose. And it's gone forever. And it removes refinements from the data, but in the case where we decide we don't really need that level of detail and want to save the space...we ditch it.

There is a lot more to compression algorithms and types of compression...but...well...this is all I know about it. Business major hah, not compsci. This isn't exactly how a computer does it with just going 1 = word, but it's an easy way to understand what compression is doing without talking about bits, algorithms, tables and computery stuff :)

46

u/[deleted] Jun 17 '12 edited Jun 17 '12

Your example is interesting, but is more like Huffman coding. I feel like the question is directed toward general lossless coding, as used in WinZip, WinRAR, 7zip, gzip, and xz programs . These algorithms are all based on LZ77 style "sliding window" coding. What that means is that as you iterate over the input you keep a "dictionary" of previous input. If the string is found in the dictionary, then you output the (length, distance) pair. Otherwise, you output a literal. Most algorithms have a switch denoting either a literal or a length, distance pair, but we'll stick to LZ77 which always outputs (length, distance, literal).

With that in mind, let's iterate over the previously provided sentence. To make things easy, let's use a sliding window size of 40. That means that neither the length nor distance will be greater than 40. To save space, we'll use a maximum length of 8. That means that we can express the length as 1 digit, and the distance in 2 digits, so we encode the (length, distance, literal) tuple as LDDC, where LL are two digits for the length, DD are two digits for the distance, and C is the last literal. At the beginning, the dictionary length is actually 0.

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.
^

We start out with the first character, 'I'. Since there is no dictionary yet, we output nothing for the (length, distance) portion, and just use the literal. The resulting tuple is (0, 0, I), encoded as 000I. Advancing to the next character we have:

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.
^^

Note there are two arrows. The 2nd arrow is our iterator over the sentence, and the first arrow is the start of our dictionary. So we now have a lookup dictionary with exactly one letter, 'I'. Since the space is not in the dictionary, we have to output another literal, 000 . Our current compressed output is 000I000 .This process continues until we get the next dictionary match, which is the space after 'like'.

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.
^_____^

Note that our "compressed" string is now 000I000 000l000i000k000e. However, now we have our first match in the dictionary. We have another space 5 characters previous to where we are now, and we go to the next character 't', which does not match the following match in our dictionary (it's the 'l' in "like"). So we output 0105t. This may seem larger, but on a computer this would be represented as 15 bits (length requires 3 bits and offset requires 4 bits), which is actually smaller than ' t' in ASCII. I'll skip ahead to a more interesting example:

I like to play. When I play I have fun. The reason I play is because I like to have as much fun as possible. The amount of fun I have is based on the amount I play.
               ^_______|_____________________________^
                ^______.|_____________________________^
                 ^_____..|_____________________________^
                  ^____...|_____________________________^ 
                   ^___....|_____________________________^
                    ^__.....x_____________________________^

Here we see the encoding of the string "play i", over the 6 characters. The first 'p' in the dictionary is 30 characters previous, and the match goes on for 5 characters. On the 6th iteration over "play i" we get to the letter 'i', which does not match , so for those 6 characters we output 630i. Since this reduces 6 bytes to effectively 15 bits on a computer, we get a large savings here.

Note this is a naive example using the original LZ77, written 35 years ago. There have been numerous improvements since then, such as using a 1 bit marker to delineate literal vs (length, distance) pair. I can go into more detail if desired.

9

u/aznpwnzor_ask Jun 17 '12

What's great about LZ77 compression is the maximum compression LZ77 offers is also equal to the entropy of your information set.

3

u/squeakyneb Jun 18 '12

... does this basically mean that LZ77, if driven hard enough for long enough, can achieve the perfect compression for any data?

→ More replies (5)

4

u/[deleted] Jun 18 '12

What's wrong with Huffman encoding? It's one of the easiest encoding methods to understand and it's used all the time, for example in the fast lossless video encoder huffyuv.

→ More replies (2)

3

u/1919 Jun 18 '12

Absolutely fascinating, though I do have a followup question.

Lets say you aren't coding a string, and instead you're coding something like a fixnum?

→ More replies (1)
→ More replies (3)

134

u/ebix Jun 17 '12 edited Jun 17 '12

I'm going to hijack this top level thread to expound on (what I find to be) one of the most interesting results about compression:

There is NO algorithm that will guarantee strict lossless compression (a reduction in size) on every input.

So not only is there a trade off in terms of time to uncompressed and process, but you can risk increasing the size of some files.

A quick intuitive proof of this result:

  1. Assume False, then there exists some algorithm that strictly compresses every input, without loss of data.

  2. Take 3 large different inputs

  3. Repeatedly apply our algorithm until each input is (losslessly) represented by one bit.

  4. There are only two possible values for this bit, but each input must be represented by a different value, and there are three. Contradiction

EDIT: I see that OlderThanGif below me beat me to the punch, so props to him, but he didn't include the proof, so imma leave this here.

EDIT2: Formatting, thanks arienh4.

0

u/[deleted] Jun 17 '12

[deleted]

12

u/Snark_Jones Jun 17 '12

Not necessarily. The PNG algorithm works by running it repeatedly to obtain smaller and smaller file size - to a point.

11

u/arienh4 Jun 17 '12

Exactly. The repetition is a part of the algorithm. If you could run PNG again once it's finished and get an even smaller size, then the algorithm can be improved.

10

u/Snark_Jones Jun 17 '12

You can, actually, but we might be talking about two different things.

If you maximized PNG compression, then ran it again and got a smaller file size, you would be correct.

The repetitions in the PNG algorithm, though, are a file size/processing time trade-off. It is, therefore, possible to take a lightly compressed PNG file, re-process it with PNG, and achieve substantial compression.

It is now obvious to me that I should have assumed you were referring to the maximized compression capability of any algorithm in question. Sorry for the tangent.

0

u/[deleted] Jun 17 '12

[deleted]

3

u/ebix Jun 18 '12

honestly; study math.

Information theory, combinatorics, and graph theory are obviously and immediately applicable to a lot of compsci. But even things like group theory, topology and analysis will help you in the strangest places. Moreover they will train your brain, and everything will seem easier.

To quote /r/compsci; "contrary to popular belief, computer science is mostly math"

→ More replies (2)
→ More replies (4)
→ More replies (27)

7

u/CrasyMike Jun 17 '12

Yes, I should probably be more clear that I'm avoiding getting into algorithms, restrictions, how to represent this in bits, how it's done in different file types, etc.

I should probably almost call this an "Explain Like I'm 5" explanation of compression, where I'm just trying to answer OP's questions in a manner anyone can understand.

5

u/ebix Jun 17 '12

Yeah, this was not in any way a critique of the explanation. As someone who is all about mathematical proof I think this is a beautiful example of how you can conclusively prove a statement that seems "far too general."

Maybe the more proofs like this one sees the better chance one has of understanding and believing crazy results like Godel's Incompleteness Theorems.

Props for the the excellent ELI5 explanation though. I gave you an upboat.

0

u/[deleted] Jun 17 '12

[deleted]

→ More replies (2)

3

u/m_Pony Jun 17 '12

at the risk of violating the spirit of formality here in AskScience, I hereby congratulate you for using "imma" instead of "I am going to" in your note about data compression. Well met.

→ More replies (6)

4

u/NEED_A_JACKET Jun 17 '12

Does video compression mainly work by 'adjusting' existing pixels? For example, 'this block of pixels moves over there' rather than giving information on the whole lot every frame?

I've always thought that's what keyframes were, a 'full' frame with the full detail, and everything in between the keyframes are just 'this part of the keyframe is now here'. Is that basically what's happening?

I've never read into it much but when you see compressed videos lose frames (bad signal / playing videos that aren't fully downloaded etc) they seem to skip the colour content of frames but still keep the movement. I always assumed that was what happens when it misses its 'key'.

6

u/Rusted_Satellites Jun 17 '12

http://en.wikipedia.org/wiki/Motion_compensation

Yes, they do move blocks of pixels around. Say you have a car driving along the street from left to right. The algorithm gets value out of saying "move these pixels x to the right" for large blocks that make up the car. However, if this is a live action car, that's not enough, since the lighting, reflections, and shadows will change, the car will not be going perfectly straight, etc... so after the motion vectors are applied, corrections are applied to get closer to the uncompressed next frame.

4

u/xNEM3S1Sx Jun 17 '12

I've always thought that's what keyframes were, a 'full' frame with the full detail, and everything in between the keyframes are just 'this part of the keyframe is now here'. Is that basically what's happening?

They are a "full" frame, but not necessarily uncompressed. These reference frames are still compressed, (like a jpeg vs bmp) and then the following frames are all information based around that frame, indicating hue, saturation, or luminance changes. (HSL)

I've never read into it much but when you see compressed videos lose frames (bad signal / playing videos that aren't fully downloaded etc) they seem to skip the colour content of frames but still keep the movement. I always assumed that was what happens when it misses its 'key'.

It will typically switch to pink/green, (I still don't know why most artifacts are pink/green, I would have to guess that it's cmky vs rgb related) and then only the parts of the picture that change regain information in their HSL values. This means that the moving part can get darker, or lighter, and more or less saturated or change hue, but doesn't have to do all of them, it could just get darker, or just get more saturated, and not change colour. (or any combination of the three)Some parts of the image, however are static, and will remain pink, until, of course, there is a new keyframe.

→ More replies (11)

3

u/Epistaxis Genomics | Molecular biology | Sex differentiation Jun 17 '12

The reason not EVERYTHING is compressed, and why sometimes "poor" algorithms are used is because the computer has to compute the uncompressed form.

So, basically, it's an economic trade-off. One resource is disk space/bandwidth depending on what is going on. Storing files we'd be considering disk space (ie. compression of a video file). Transferring files we'd be considering bandwidth (ie. compression of internet traffic). Both of which obviously costs money.

The other resource is CPU time, which also costs money (as a sort of opportunity cost, if you use up CPU processing to do compression you could have been doing something else with those cycles).

So if it's a tradeoff, is it possible to compute the break-even point, i.e. the point where it actually becomes faster to read a compressed file and uncompress it on the fly than to read the uncompressed file, based on disk read throughput and CPU speed?

E.g. I tend to work with data files that are gigabytes of plaintext, which I store with maximal compression, and then pass them through a parallelized decompressor on their way into a text-parser (don't judge me! I didn't write this software or the file formats!). How fast does my decompression have to be (how much CPU power or how low of a compression level) before this actually results in better performance relative to just storing those files uncompressed (if I could)?

4

u/[deleted] Jun 17 '12

It's hard to give a specific point, because it depends so much on the hardware and what you are doing with it once it's read. In my experience, if there is any significant processing being done and you're reading straight from the disk, the disk is probably not the bottleneck (i.e. the disk is feeding the CPU as fast as it can process it). If it's read over a network or other slowdown (usb, etc) then perhaps - if the processing isn't bottoming out the CPU (i.e. it spends time waiting for more data to process) then using that to decompress a file instead can indeed be worthwhile at times - if it's highly compressible data with plenty of headroom in the CPU department having things on a compressed drive can increase the "end drive speed" as it's crammed through and decompressed.

This is somewhat speculative and I apologize for that - it's only personal observations slinging similar data over networks.

2

u/errandum Jun 18 '12

Actually, I've been studying something unrelated, but came by this: source

Compression-aware databases [1]: It is clear to any observer of the computing scene that CPUs are getting faster at an incredible rate. Moreover, CPUs will increasingly come packaged with multiple cores, possibly 10 or more, in the near future. Hence, the cost of computation is plummeting. In contrast, disks are getting much bigger and much cheaper in cost per byte, but they are not getting any faster in terms of the bandwidth between disk and main memory. Hence, the cost of moving a byte from disk to main memory is getting increasingly expensive, relative to the cost of processing that byte. This suggests that it would be smart to trade some of the cheap resource (CPU) to save the expensive resource (disk bandwidth). The clear way to do this is through data compression.

So, to sum it up, the bottleneck in your pipeline should be the gigabytes of plaintext and not the computing power (assuming you run modern hardware). So if I had to guess, compress everything with a common algorithm (zip, etc) and you should be fine. But since I have no idea on what data/setup, this is all speculation.

Oh, and by the way, finding a way to calculate that sweetspot is, literally, a million dollar question. If you ever come by it, congratulations, you might have just won the lottery (:

→ More replies (3)

2

u/mrkurtz Jun 17 '12

Great explanation.

2

u/purenitrogen Jun 18 '12

I like the simplicity of this explanation, so can I ask, what if the "sentence" contains "1".

"I am 1 year old"

If we say 1 = year, "I am 1 1 old"

Now our algorithm reads back "I am year year old"

How is this avoided?

→ More replies (2)
→ More replies (30)