Maths, Tech

Compression

The majority of strings can not be compressed. By string I just mean a binary number, which is ultimately what all computerised stuff is.

How come? Well, say you wanted to compress a 4-bit string to a 3-bit string. There are 24 possible 4-bit strings, but only 23 possible 3-bit strings: there are twice as many possible 4-bit strings as 3-bit ones.

Compression is a lossless process so that the compression can be reversed, so each uncompressed (4-bit) string should match up with a unique compressed (3-bit) string, in a one-to-one correspondance. Yet there are only half as many 3-bit possible strings as 4-bit ones, meaning that only half of the 4-bit strings can be compressed. Bear in mind, this is just for compressing a string by a single bit. If you want to remove another bit, the possibilities half yet again, and so on.

I think that’s pretty cool.

I’d like to learn more about compression. I realise that a lot of compression is achieved just by removing irrelevant zeroes, but that’s about as far as my knowledge goes.

Add Your Comment