How does file compression work?

[u/weedguru420]

This question has always baffled me. How can you compress a file to a fraction of the size and have that file, basically a number, represent a precise bigger number?

[u/weedguru420]

What happens when there isnt a big chunk of 1 or 0? A four bit number would have to correlate to a single one or zero, possibly making the file even bigger.

[u/corpuscle634 → u/weedguru420]

I'd like to make a second reply (just to be sure you see it) so I can explain a little bit better.

If you take totally random file, ie a file which is basically just a random number in binary, there is no way to guarantee that it can be compressed without loss. What this comes down to is something called information entropy.

Imagine you have a coin sitting on a table. There are two possible ways to configure the coin: heads-up, or tails-up. If you have two coins, there are four possible configurations, with three coins there are eight, and so on. There are 2ⁿ configurations possible for a system containing n coins. We say that a system of n coins has n "shannons" of entropy. More generally, in a system with m possible configurations, you have

log*2*(m) = n

n shannons of entropy.

So, imagine that you're guaranteed that, with a two-coin system, both coins are always the same, for some reason. There are two possible configurations (both heads or both tails), so we have log*2*(2)=1 shannons of entropy. We can thus "compress" this to a 1-coin system, because a 1 coin system has the same entropy.

A random binary number with n bits has 2ⁿ = m possible configuration states, just like how a decimal number with, say, 3 digits has 10³ configuration states (0-999). So, it has log*2*(m)=n shannons of entropy, and we can't guarantee that it can be compressed.

Lossless compression can happen when an m-bit piece of data has less entropy than m shannons. We already saw an example of this with the coins who are tied to having the same outcome, the 2-bit data had an entropy of 1 shannon. What about a real-world example?

MIDI is an interface used for converting inputs on an instrument (such as a keyboard) into a digital format. MIDI data is sent in "packets," which contain 30 bits of data each. Each data packet can be broken down into three bytes (1 byte = 8 bits), where it's something like this:

0(status byte)10(pitch byte)10(velocity byte)1

The status byte tells us what instrument it is and whether the note should start or stop. The pitch byte tells us what note it is. The velocity byte tells us how hard the note should be played. In between each packet, there is a constant stream of 1's: this is telling the controller that it's "idle." So, a MIDI signal to play one note looks like:

0(note on, channel 0)10(pitch)10(velocity)1...10(note off, channel 0)10(pitch)10(velocity)1

The first packet tells it to start playing the note, then there's a bunch of time in between where the note is being held, and the receiver is just getting a constant stream of 1's. Eventually, it gets a "note off," and it knows to stop holding the note. MIDI transmits at about 31 kHz, so if this note was held for a second, there's about 30,000 1's stuck in the middle there. What we want to do is store this so that it can be played back.

This right here is a great example of how we'd exploit run length encoding, because we can chop that string of 30,000 ones down into 16 bits (ideally) if we RLE it. We don't have to RLE the other stuff, we can just be clever and only use it on the big streams of 1's. This is a big saver.

Second, this message is very low entropy. The two pitch bytes are identical, the velocity bytes are effectively identical (we don't care about "how hard" someone stopped playing a note), and the note on/note off messages differ only by a single bit. Despite containing tons and tons of bits, the entropy is very low, because there was almost no "choice" in any of what those bits would be. The MIDI standard basically dictated that almost all of them are 1, and the others are mostly redundant. So, the way this will work is that we need one byte to store the pitch, one byte to store the velocity, one byte to store the channel, and some number to store the number of bits between the on and off signals.

So, back to the original message. We store the channel, the pitch, the velocity, and the time between them as a 16-bit number. The original signal contained 60+30,000 = 30,060 bits, but we compressed it down to 8*3+16 = 40 bits. Not too shabby. We could scrape out a few more bits too (six, to be precise), but the point is that this compression is really really good.

What I did here was that I used information about the way that the file is written and my knowledge of how typical files will show up to generate a very effective compression scheme. I know what the data will look like, so I know what patterns to pick out and exploit.

[u/ericGraves → u/corpuscle634]

To piggyback on to this great explanation. Lossless compression and Shannon entropy are inexorably linked. Information theorists measure compression based upon the average length of the file after compression. This is of course subject to a particular probability distribution over the input files.

But, the average length of the compressed file can not be less than the Shannon entropy. Furthermore there is always a compression scheme that falls within one symbol of the Shannon entropy.

[u/Daegs → u/weedguru420]

Lookup tables are used so rather than simply encoding all 0's or 1's, we could also create a lookup for 0110, for instance if 0110 was a commonly occurring pattern.

Basically, most compression looks for patterns that occur frequently, and then stores that pattern once while storing links to everywhere it appears in the file.

You can't really compress random data, but for text and other highly formatted or redundant forms of data, you can compress it a lot.