Compression functions are only practical because "The bit strings which occur in practice are far from random"?

Question

I would have made a comment, as this pertains to Andrej Bauer's answer in this thread; however, I believe it is worth a question.

Andrej explains that given the set of all bit strings of length 3 or less, a lossless compression function can only "compress" some of them. The others, for instance "01" would have to actually be compressed to a string such as "0001", with length 4. The compression ratio is simply the average compression across the input set.

This makes lossless compression seem impractical, but the important quote is this:

The bit strings which occur in practice are far from random and exhibit a lot of regularity.

I have a hard time believing that, for instance, multimedia files are represented by anything other than random bit strings. Is there truly a pattern that compression functions leverage to make the algorithm useful in reality?

Answer 1

First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is nothing but a compression algorithm!
A consequence is that further compression will not yield any noticeable compression (and indeed, lossless compression on already compressed (multimedia) files has never been a road to success).

You're also right on your other point: Lossless compression cannot compress on the average. To see that, say, your possible data set consists of $2^n$ different elements. How many bits do you need per file to always be able to distinguish elements from your set? Right, $n$. In total all files will be represented by no less than $n \cdot 2^n$ bits. Now if you represent some of those files by less than $n$ bits, some files will be represented by more than $n$ bits. That's about all there is to say.

In short, lossless compression works because text files are far from random (just consider the letter distribution of my answer and compare the number of e's with the number of z's!), and compressing random data (e.g. already compressed data or encrypted data) does not make any sense.

Answer 2

Multimedia data is very far from random, which is why it compresses so well. For example, a single second of video at 1920x1080 pixel resolution, with 24-bit colour and 24 frames per second is about 150MB of data uncompressed. Multimedia files have already been compressed so are hard to compress any farther.

However, even uncompressed multimedia data will probably look pretty random if you just consider it as a stream of zeroes and ones. (Having said that, GIFs are compressed using LZW, treating them as, essentially a stream of bits; that works decently well.) When you look at multimedia data knowing what it means, there's a lot of structure in there.

• Images have a lot of colour gradients and blocks of similar colours. JPEG uses something a lot like this.
• In video, almost every frame looks very similar to the one immediately before it, with some parts moved a little. MPEG uses this extensively.
• A lot of the sounds we're interested in are waveforms from resonating objects, not random frequencies.

I've mentioned JPEG and MPEG which are, of course, lossy. But I suspect you could use these ideas, in principle, to produce good lossless compression ratios of this non-random data. I doubt anyone would try to do that, though, as the time taken to compress would probably be impossibly huge.

Answer 3

Yes, lossless compression takes advantage of the fact that many files are not random. Yes, most multimedia files are not random.

Fax images are a good example of this effect. In their simplest form, a fax image is a 2-D black-and-white image, obtained by scanning a single page of some document. If you represent this image as a sequence of bits, one bit per pixel (0 = white, 1 = black), then you will discover that the resulting binary data is not at all random. For instance, here are some non-random patterns you will spot:

• Typically fax images have a lot more white pixels than black pixels.

• Also, each pixel is more likely to have the same color as the pixel to its left than to have a different color.

• For a more sophisticated pattern: Imagine scanning pixels horizontally, left to right, and counting the length of each "run" of consecutive pixels with the same color. Then long runs are more common than short runs, and long runs of white pixels are more common than long runs of black pixels.

Fax compression algorithms were designed to take advantage of these non-random aspects. Early fax compression algorithms are a particularly good example, because they are simple lossless compression schemes that very directly exploit these non-random properties of scanned images.

For instance, one early scheme for compressing fax images used run-length encoding combined with Huffman encoding. Run-length encoding replaces each run of same-color pixels with a single integer counting the length of the run. For instance, 00000110001 becomes "5 2 3 1". Run-length encoding exploits the fact that pixels tend to come in runs of the same color. The Huffman encoding further exploits the fact that some run-lengths are more common than others. See here for a detailed example of how one of these early schemes worked -- the scheme is simple and elegant, and directly exploits the patterns mentioned above.

These schemes would not offer any compression, on average, for random files. However, scanned fax images are not random, and as a result these compression schemes can offer substantial savings.

Similar comments apply to other multimedia files. The patterns present in other kinds of multimedia files can be more complex, but there are still many patterns present that make the data non-random.

Answer 4

A random audio file constitutes a kind of noise. Most people store audio files with music or speech, not noise.