37
$\begingroup$

A long time ago I read a newspaper article where a professor of some sort said that in the future we will be able to compress data to just two bits (or something like that).

This is of course not correct (and it could be that my memory of what he exactly stated is not correct). Understandably it would not be practical to compress any string of 0's and 1's to just two bits because (even if it was technically possible), too many different kind of strings would end up compressing to the same two bits (since we only have '01' and '10' to choose from).

Anyway, this got me thinking about the feasibility of compressing an arbitrary length string of 0's and 1's according to some scheme. For this kind of string, is there a known relationship between the string length (ratio between 0's and 1's probably does not matter) and maximum compression?

In other words, is there a way to determine what is the minimum (smallest possible) length that a string of 0's and 1's can be compressed to?

(Here I am interested in the mathematical maximum compression, not what is currently technically possible.)

Improve this question
$\endgroup$
6
  • 7
    $\begingroup$ We would also have '00' and '11' to choose from. But the argument is the same, if you use those, there are only four different strings you can compress. $\endgroup$
    – RemcoGerlich
    Commented Nov 28, 2015 at 9:02
  • 3
    $\begingroup$ mathoverflow.net/q/160099/34859 : Pl see here that vide the pigeonhole principle there will be always an infinite number of strings which can not be compressed ... Irrespective of the algorithm used.(See the section titled 'Background' in the question $\endgroup$
    – ARi
    Commented Nov 28, 2015 at 13:52
  • 4
    $\begingroup$ Compression depends on the knowledge you have about the structure of the data. There was this article about compressing chess moves that shows how adding knowledge helps increasing compression. $\endgroup$
    – spectras
    Commented Nov 29, 2015 at 23:37
  • 1
    $\begingroup$ Can you clarify: Compression can be "lossy", or "lossless" (or some "hybrid" which may use both). Are you talking about maximum compression using only "lossless" compression methods, or are you including (allowing) the use of "lossy" compression methods as well. In other words, I guess there are 3 possibilities: looking for "maximum compression" where (1) the data must always be able to be decompressed exactly as it was before compression, (2) the data must be able to be decompressed, but some "loss" is allowed (3) it is not a requirement that the data be able to be decompressed. $\endgroup$
    – Kevin Fegan
    Commented Nov 30, 2015 at 17:18
  • $\begingroup$ Hi @KevinFegan, in this case it would have to be option 1: "the data must always be able to be decompressed exactly as it was before compression" $\endgroup$
    – x457812
    Commented Nov 30, 2015 at 17:33

5 Answers 5

Reset to default
47
$\begingroup$

Kolmogorov complexity is one approach for formalizing this mathematically. Unfortunately, computing the Kolmogorov complexity of a string is an uncomputable problem. See also: Approximating the Kolmogorov complexity.

It's possible to get better results if you analyze the source of the string rather than the string itself. In other words, often the source can be modelled as a probabilistic process, that randomly chooses a string somehow, according to some distribution. The entropy of that distribution then tells you the mathematically best possible compression (up to some small additive constant).

On the impossibility of perfect compression, you might also be interested in the following.

Improve this answer
$\endgroup$
2
  • $\begingroup$ but, compression is one of the techniques for estimating entropy. Can compression and entropy be two facets of the same thing? $\endgroup$
    – Paul Uszak
    Commented Nov 30, 2015 at 4:52
  • 1
    $\begingroup$ @PaulUszak, yes, they are very closely related: see, e.g., Shannon's theorem. But, please note: comments should be used only to suggest improvements/clarifications to the post, not to ask follow-up questions. To ask a new question, use the "Ask question" link in the upper-right part of the page. $\endgroup$
    – D.W. ♦
    Commented Nov 30, 2015 at 4:57
35
$\begingroup$

For any given string there is a compression scheme that compresses it to the empty string. Hence it is not meaningful to ask how much a single string can be compressed, but rather how much a collection (or distribution) of strings can be compressed to, on average. In general, given a collection of $N$ strings, any compression scheme needs at least $\log_2 N$ bits or so to encode a string from the collection in the worst case.

Also, in many cases we don't care about exact reconstruction. This is called lossy compression, and is how music and videos are compressed. In this case the lower bound stated above doesn't hold, but you can come up with other lower bounds.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Veedrac No, you understood me correctly. Your argument (more or less) shows that any encoding scheme for $N$ strings requires $\log_2 N$ bits for some strings. The side-channel here is the decompression procedure. $\endgroup$
    – Yuval Filmus
    Commented Nov 28, 2015 at 7:27
27
$\begingroup$

Here's a simple scheme that can compress arbitrary bit strings lossless, with the smallest result being just one bit:

IF the string is an identical match for the recording of Beethoven's 9th symphony, fourth movement, in AAC format that is stored on my computer's hard drive, then the output is a single bit '0'.

IF the string is anything else, then the output is a single bit '1', followed by an identical copy of the original string.

This scheme reduces one possible input to exactly one bit, and increases every other input in length. There is a general principle: If a compression algorithm can map any input string to a compressed string, and there is a matching decompression algorithm that maps any compressed string back to the original string, and the compression algorithm maps any input to a shorter string, then it must map some input strings to longer strings.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Good job of making the answer clear and obvious. It's worth noting that this is similar to what a good compression algorithm attempts to do - for a given input domain, try to shorten the most commonly expected types of inputs, in exchange for less common inputs being lengthened. $\endgroup$
    – JBentley
    Commented Nov 29, 2015 at 17:26
6
$\begingroup$

For every compression scheme you can come up with, it is possible to produce data that will be uncompressible by it. So even if your compression scheme is very efficient with some types of data, it will never consistently compress to a certain ratio.

The way to produce an example of uncompressible data for a particular compression algorithm is simple: take any kind of data and run it through the compression algorithm repeatedly, until the size no longer decreases.

So the compressibility of a string of bits is not really a function of the length of the string, but of its complexity in relation to the compression algorithm.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Welcome! Note that this only applies to lossless compression. Lossy compression can compress all strings (at least, as long as you accept the algorithm "Return empty string" as a lossy compression algorithm. ;-) ). $\endgroup$
    – David Richerby
    Commented Nov 29, 2015 at 22:29
  • $\begingroup$ @DavidRicherby That's true, of course. But I got the impression from the question that the OP was asking about lossless compression, because it doesn't make much sense to discuss the maximum compression of a lossy scheme; the idea that you can take it to unusable extremes is inherent in the concept of lossy compression. $\endgroup$
    – m69 ''snarky and unwelcoming''
    Commented Nov 29, 2015 at 22:33
  • $\begingroup$ Yes, I think that's a reasonable interpretation. $\endgroup$
    – David Richerby
    Commented Nov 29, 2015 at 22:33
-2
$\begingroup$

There is an interesting and completely different algorithm that is used by enterprise backup systems. The idea is that if you have a company with 10,000 computers, then many many of these computers will contain many identical files. For example an email sent to everyone in the company might end up as an identical file on every single hard drive.

So a backup system trying to backup a file should obviously try to compress the file to save space, but first the backup system checks if an absolutely identical file is already saved! So instead of backing up anything, all that the backup system does is for example remembering that you have file number 1,487,578 on the backup system on your hard drive.

This is especially efficient for example when 10,000 users all have identical operating system and applications installed. For single users it's not very useful at all.

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ That's interesting but I don't see how it answers the question. The question asks for limits on compression, not a general discussion of enterprise backups. $\endgroup$
    – David Richerby
    Commented Nov 29, 2015 at 22:43
  • $\begingroup$ This is called deduplication, and is done using hashes. It takes a lot of RAM to store a 128bit hash for every block on disk. ZFS can do this to opportunistically make some blocks share some copy-on-write storage space. But this kind of compression problem (where you are trying to compress a massive data set that you need random access to, and that's changing too quickly for normal stream compression, but has block-level redundancy) isn't relevant as an answer to this question. $\endgroup$
    – Peter Cordes
    Commented Dec 1, 2015 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.