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

Show parent comments

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)

2

u/arienh4 Jun 17 '12

Whoa, you're giving me far more credit than I'm due. I'm more of a hobbyist, to be honest. I know some of this stuff from working with compression personally, but I'm not starting CompSci for another year.

What I provided was more of a reworking of Ebix's answer than real original content, to be honest.

They might be able to help you, not I.

2

u/UncleMeat Security | Programming languages Jun 18 '12

Sipser's book is considered by many to be the best introductory text on theory of computation. It covers a lot of things that are needed to understand PL theory, but not PL itself.

There is no "best" text on PL that I am aware of. It depends on if you want more practical ideas like parsers and compilers or more mathematical ideas like algebraic type theory. The "dragon" book is a well known book that covers the first set of materials. Fundamentals of Programming Languages by Mitchell is a pretty good guide to the second set of materials, but it is a little dry.

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

2

u/TwirlySocrates Jun 18 '12

Why would a compression algorithm neccessarily be able to compress anything to one bit? A compression algorithm recognizes repetition and patterns, but if you compress something into a stream of bits that is otherwise indistinguisheable from noise, it shouldn't be compressible anymore, no?

→ More replies (1)

3

u/DDB- Jun 18 '12

I am going to hijack this comment and present it in another different way, which might be more intuitive to some people.

  1. Given a file that is N bits in length, there are 2N possible such files. (For each bit in the file of length N it can either be a 0 or a 1)

  2. Suppose that every one of these files is compressed. Therefore each one must have a size of N-1 bits or smaller (otherwise it wasn't compressed)

  3. If we have a file that is only N-1 bits in length, there are 2N-1 such files of this length at most.

  4. Since there are at most half the amount of compressed files as original files (2N-1 is half of 2N ), this implies that two or more of the original files compressed to the same thing, meaning there would be no way to reconstruct the original (because how would you know which original to go back to if 2 original files compressed to the same thing)

The implication: Whatever the lossless compression algorithm, there must be some files for which the size is increased by the algorithm.

Source: Copied directly from my course slides on Data Compression. My professor for the course was a co-inventor of Dynamic Markov Compression so I trust his teachings in the data compression field.

Imgur Link to the slide of his I used.

2

u/Nate1492 Jun 17 '12

Yes, I agree with the fundamental concept that there exists a perfectly constructed data set that cannot be reduced by an algorithm. There is potentially infinite sets of data that cannot be reduced for each algorithm. But that's pretty much cherry picking your data. And it doesn't take into consideration the scope of computers and their data sets. Computer data lends itself to repetition and compression, this is why we can utilize compression so well in the digital form.

There is clearly an upper limit on the amount of non-compressible data for a fixed number of possible characters, which is an interesting math problem, but I won't get into it.

Almost every algorithm guarantees real world compression on the vast majority of files. A typical computer would be unlikely to contain a single file that fails to be reduced in size. (As long as there has been no compression ran already).

TL:DR In theory, compression algorithms can't always reduce the size of files. In real world situations, this is rarely the case.

2

u/ebix Jun 18 '12

I agree I am totally cherry picking data. One interesting question that the OP asked was "Why don't we compress everything."

I think this was an attempt to intuitively explain why we don't compress everything. Furthermore, I would disagree that almost everything can be compressed, there is a fairly large class of files none of which can be compressed, namely, compressed files.

This proof attempts to develop an intuition for why we can't just compress things into oblivion. There are much more concrete things which can be said via information theoretic methods (see ratazana's post below). However, these proofs have perhaps less layperson appeal.

→ More replies (4)

0

u/[deleted] Jun 17 '12

[deleted]

2

u/Nate1492 Jun 18 '12

That fails to meet the criteria of not already being compressed... Which I briefly covered.

→ More replies (1)
→ More replies (11)

1

u/yatima2975 Jun 18 '12

Slight nitpick: you have to deal with the case that one of the three inputs is the result of doing (possibly repeated) compression on one of the other :)

The proof I've been taught goes as follows: there are 2n inputs of length n, and 20 + 21 + ... + 2n-1 = 2n - 1 messages of length strictly shorter. If a lossless compression algorithm existed, it would compress all 2n messages of length n into something shorter, which is impossible by the pigeonhole principle.

→ More replies (3)

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]

1

u/spiral_of_agnew Jun 17 '12

That's better reasoning, thanks.

1

u/ebix Jun 18 '12

Everything here is 100% spot on.

That said, I think most askscience readers would read the first half of your theorem and run for the hills. Were this /r/compsci, or /r/math my post would look a little more like yours =D

Still though, hi-five.

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.

0

u/[deleted] Jun 18 '12

[deleted]

2

u/itstwoam Jun 18 '12

Right I see what I didn't read there. My mistake, sorry.

1

u/ILikeBumblebees Jun 18 '12

Or, more broadly, for a lossless compressor to work universally, there must be a complete one-to-one mapping between the set of all inputs and the set of all outputs. But because the size of those sets is determined by the number of combinations of bits available within each, and since a compression algorithm by definition reduces the number of bits in the output corresponding to each input, then the set of all possible outputs must always be smaller than the set of all possible inputs, meaning that there can be no strict one-to-one mapping between the two sets; there will always either be inputs that have no corresponding or output, outputs that correspond to more than one input.

→ More replies (3)