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

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?

• I'm no expert but there is definitely a lot of regularity in things. Consider a picture of a tree; green and brown will dominate the image. Because we see these values a lot we can compress them to smaller values. Next off consider the idea of lossless compression, it is too good to be true. Something has to give. That something is what is being talked about here. Lastly try an experiment where you randomly generate strings and see what the compression ratio is averaged over many times. If you do things right (which might be hard) you should see no real overall advantage. – Jake Mar 24 '15 at 3:30
• Also, even if you were deliberately storing random data as a multimedia file, the file itself has structure which is repetitive and can be compressed - headers, frame data (for things with frames) and so on. – Luke Mathieson Mar 24 '15 at 4:24

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.

• I think you are mixing issues, slightly. "Zipping multimedia files has never been a road to success" -- does LZ work on uncompressed multimedia, e.g. WAV or TIFF? LZ was designed for strings, i.e. with certain assumptions that may or may not hold for non-string data. – Raphael Mar 24 '15 at 14:44
• I can certainly see your point when concerning text files and letter distribution. Very interesting stuff. – AlexMayle Mar 24 '15 at 15:42
• @Raphael You're right, compressing WAV or TIFF should yield a noticeable compression. I included the word "compressed" in the corresponding part. Regarding your other point, yes, the LZ algorithms were defined for strings, but as far as I know zip etc work for every binary data. – john_leo Mar 24 '15 at 15:44
• Okay, but one further comment: not all multimedia compressions are lossy. For instance, FLAC and PNG compress significantly without losses. Comparing ZIP to FLAC or PNG (starting with WAV or TIFF) may be educational with respect to the impact of design assumptions. – Raphael Mar 24 '15 at 15:53
• @Raphael instead I chose to eradicate the reference to any actual compression algorithm, I found that talking about ZIP, FLAC or WHATNOT might be a different subject. – john_leo Mar 24 '15 at 16:03

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.

• Some good examples here. – AlexMayle Mar 24 '15 at 16:00
• 1920*1080*24*24 is 1.11 Gb of data uncompressed. 150Mb is just enough for 320x480 grayscale.@ 1fps. – FRob Mar 28 '15 at 18:01
• @FRob Bytes, not bits. I've corrected "Mb" to "MB". – David Richerby Mar 28 '15 at 19:45
• Regarding the last paragraph: something like this is actually done. There are lossless audio codecs which are based on a stream using a lossy compression algorithm plus the difference of that to the original compressed in a conventional way. – Carsten S May 11 '16 at 16:58

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.

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

• Thank you for your contribution. Could you elaborate and add some examples? The idea you gave is good, true, but it was already presented in 3 previous answers. – Evil May 10 '16 at 1:46
• @EvilJS, quite possibly true. I do not think that it should take half a page to explain that there is a difference between speech and noise, though. – Carsten S May 10 '16 at 8:30
• It shouldn't take half a page to explain the salient facts so that your answer explains why speech and music compress but random noise doesn't. – David Richerby May 11 '16 at 16:37
• @DavidRicherby, that random data does not compress was already accepted in the question. The question was "but isn't multimedia data random?" to which the answer is that it is obviously not. – Carsten S May 11 '16 at 16:54