Which is the limit of lossless compression data? (if there exists such a limit)

Question

Lately I've been dealing with compression-related algorithms, and I was wondering which is the best compression ratio that can be achievable by lossless data compression.

So far, the only source I could find on this topic was the Wikipedia:

Lossless compression of digitized data such as video, digitized film, and audio preserves all the information, but can rarely do much better than 1:2 compression because of the intrinsic entropy of the data.

Unfortunately, Wikipedia's article doesn't contain a reference or citation to support this claim. I'm not a data-compression expert, so I'd appreciate any information you can provide on this subject, or if you could point me to a more reliable source than Wikipedia.

Answer 1

I am not sure if anyone has yet explained why the magical number seems to be exactly 1:2 and not, for example, 1:1.1 or 1:20.

One reason is that in many typical cases almost half of the digitised data is noise, and noise (by definition) cannot be compressed.

I did a very simple experiment:

• I took a grey card. To a human eye, it looks like a plain, neutral piece of grey cardboard. In particular, there is no information.

• And then I took a normal scanner – exactly the kind of device that people might use to digitise their photos.

• I scanned the grey card. (Actually, I scanned the grey card together with a postcard. The postcard was there for sanity-checking so that I could make sure the scanner software does not do anything strange, such as automatically add contrast when it sees the featureless grey card.)

• I cropped a 1000x1000 pixel part of the grey card, and converted it to greyscale (8 bits per pixel).

What we have now should be a fairly good example of what happens when you study a featureless part of a scanned black & white photo, for example, clear sky. In principle, there should be exactly nothing to see.

However, with a larger magnification, it actually looks like this:

There is no clearly visible pattern, but it does not have a uniform grey colour. Part of it is most likely caused by the imperfections of the grey card, but I would assume that most of it is simply noise produced by the scanner (thermal noise in the sensor cell, amplifier, A/D converter, etc.). Looks pretty much like Gaussian noise; here is the histogram (in logarithmic scale):

Now if we assume that each pixel has its shade picked i.i.d. from this distribution, how much entropy do we have? My Python script told me that we have as much as 3.3 bits of entropy per pixel. And that's a lot of noise.

If this really was the case, it would imply that no matter which compression algorithm we use, the 1000x1000 pixel bitmap would be compressed, in the best case, into a 412500-byte file. And what happens in practice: I got a 432018-byte PNG file, pretty close.

---

If we over-generalise slightly, it seems that no matter which black & white photos I scan with this scanner, I will get the sum of the following:

• "useful" information (if any),
• noise, approx. 3 bits per pixel.

Now even if your compression algorithm squeezes the useful information into << 1 bits per pixel, you will still have as much as 3 bits per pixel of incompressible noise. And the uncompressed version is 8 bits per pixel. So the compression ratio will be in the ballpark of 1:2, no matter what you do.

---

Another example, with an attempt to find over-idealised conditions:

• A modern DSLR camera, using the lowest sensitivity setting (least noise).
• An out-of-focus shot of a grey card (even if there was some visible information in the grey card, it would be blurred away).
• Conversion of the RAW file into a 8-bit greyscale image, without adding any contrast. I used typical settings in a commercial RAW converter. The converter tries to reduce noise by default. Moreover, we are saving the end result as an 8-bit file – we are, in essence, throwing away the lowest-order bits of the raw sensor readings!

And what was the end result? It looks much better than what I got from the scanner; the noise is less pronounced, and there is exactly nothing to be seen. Nevertheless, the Gaussian noise is there:

And the entropy? 2.7 bits per pixel. File size in practice? 344923 bytes for 1M pixels. In a truly best-case scenario, with some cheating, we pushed the compression ratio to 1:3.

---

Of course all of this has exactly nothing to do with TCS research, but I think it is good to keep in mind what really limits the compression of real-world digitised data. Advances in the design of fancier compression algorithms and raw CPU power is not going to help; if you want to save all the noise losslessly, you cannot do much better than 1:2.

Answer 2

Do you already know about Shannon's noiseless coding theorem? This theorem establistes theoretical limits on lossless compression. Some of the comments from the others seem to assume you know about this theorem, but from the question, I think it may be the answer you are looking for.

Answer 3

Think of a file as a string.

You can never do better than the Kolmogorov complexity of a string (this is by the definition of Komogorov complexity).

Fix a string length. So now we're only looking at strings of length n.

Half of all such strings can be compressed by at most 1 bit. 1/4 of all strings can be compressed by at most 2 bits. 1/8 of all such strings can be compressed by at most 3 bits.

So what fraction of strings (images, files, etc.) can be compressed at the ratio of 2:1 -- very, very few. So why does compression ever work? Because almost all data that real people are actually trying to compress is highly structured -- it doesn't look like a random file. The more random looking the data, the harder to compress. They go hand in hand. Most strings look random.

To see this in action, generate a random file using some random process. I mean a really, really random file. Now try to compress it using your favorite compression algorithm. It will either stay the same size or get bigger, almost all of the time.

On the flip side, there are highly compressible strings. Take the following string: 100000..000 (1 followed by a million zeros). The description of it fits in the previous sentence, and a computer could reconstruct it from that description (or one very much like it). Yet that description is nowhere near a million digits long.

The fact is that strings with that property (of being highly compressible) are extremely rare among all possible strings. The secondary fact is that almost all human-generated data is super, super compressible because it is so structured.

Answer 4

Compression is just an opportunistic way of encoding things, and when asking for "the best compression ratio that can be achievable by lossless data compression", you need to be more specific about the context of the compression: the compression ratio is the ratio between the size of the compression and the size of a "raw" encoding, but the size of the "raw" encoding depends of the hypothesis on your object (i.e. the size of its domain, or the "size of the bag from which it comes"). As a simplistic example, consider the task of encoding a positive integer $n>0$:

1. You might use only one bit, if $n$ is the only integer you will ever encode, and you need only to remember that you encoded it.

2. The common practical solution is to use 8 bits, if the only integers you will ever encode are all between 1 and 256 (generalize to 16, 32 and 64 bits if you want).

3. If you do not have any hypothesis about the range in which falls the integer you will have to encode, a naive solution is to use $n+1$ bits ($n$ zeros followed by a one) to encode it in unary. This might not look yet as a compression, but it has the opportunistic aspect of compression: the smaller the value of $n$, the smaller the size of its unary encoding.

4. A more serious, general purpose, encoding scheme of integers is the gamma code: encode the value of $\lceil\log_2 n\rceil$ in unary using $\lceil\log_2 n\rceil+1$ bits, followed by $n$ in binary, using $\lceil\log_2 n\rceil-1$ (you do not need the leftmost bit, which is always one, since you already know the value of $\lceil\log_2 n\rceil$). This encoding uses in total $2\lceil\log_2 n\rceil-1$ bits, and is a useful compression of $n$, often use in practice. (Note that in the litterature you will find those results noted $\lg n=\max(1,\lceil\log_2 n\rceil)$ to make notations shorter.)

5. The gamma code is not optimal, in the sense that there are other codes which use less space for arbitrarily many integers, and more for only a finite amount. A very good reading on the topic is "An almost optimal algorithm for unbounded searching" by Jon Louis Bentley and Andrew Chi-Chih Yao from 1976 (I like in particularly their link between the complexity of search algorithms and the size of integer encodings: I find it one of the most simple and beautiful TCS results I know). The bottom line is that $2\lceil\log_2 n\rceil-1$ bits is within a factor of two of the optimal, which most agree is enough in practice given the complexity of better solutions.

6. Yet, taking the "opportunistic" approach to its limit, there is an infinite number of compression schemes taking advantage of various hypotheses. One way to deal with this infinity of opportunistic encodings (i.e. compression scheme) is to require the encoding of the hypothesis itself, and to take into account the size of the encoding of the hypothesis in the total compression size. Formally, this corresponds to encode both the compressed data and the decoder, or more generally to encode a program which, when executed, outputs the uncompressed object: the smallest size of such a program is called the Kolmogorov's complexity $K$. This is a very theoretical construct in the sense that, without a bound on the execution time of the program, $K$ is not computable. An easy workaround around this notion is given by Levin's self-delimiting programs, where you consider only programs with a bounded execution time (for instance, within a constant factor of the length of the original instance, which is a lower bound on the complexity of the algorithm which needs to write each symbol).

There is a whole community working about Kolmogorov's complexity and its variants, and another community working on loss-less compression (the example on integers that I used has equivalent on many other data types), I barely scratched the surface, and others might add precisions (Kolmogorov is really not my specialty), but I hope that this might help you clarify your question, if not necessarily give you the answer you were hoping for :)

Answer 5

(just an extension of my comment)

(As pointed out by Joe in his answer) Shannon - in his 1948 paper, "A Mathematical Theory of Communication" formulated the theory of data compression and established that there is a fundamental limit to lossless data compression. This limit, called the entropy rate, is denoted by H. The exact value of H depends on the information source --- more specifically, the statistical nature of the source. It is possible to compress the source, in a lossless manner, with compression rate close to H. It is mathematically impossible to do better than H.

However some class of images (for example medical grayscale images) without high-contrast edges and with smooth level transitions can be compressed (not so efficiently).

JPEG-LS and JPEG2000 seem to be the standards for lossless storage of medical images. See this table for a comparison of compression ratios (the JPEG-LS achieves a slightly better compression).

Using "lossless medical image compression" I found the following articles that may help you:

A recent (2011) survey on medical image compression techniques: Two Dimensional Medical Image Compression Techniques - A Survey

... This paper presents overview of various compression techniques based on DCT, DWT, ROI and Neural Networks for two dimensional (2D) still medical images.

A detailed presentation of two standard lossless compression algorithms: JPEG-LS and JPG2000 in lossless mode: Lossless Compression of Grayscale Medical Images - Effectiveness of Traditional and State of the Art Approaches

... Three thousand, six hundred and seventy-nine (3,679) single frame grayscale images from multiple anatomical regions,modalities and vendors, were tested. ...

Another survey: A Survey of Contemporary Medical Image Compression Techniques

EDIT

Perhaps you are still wondering "What the hell is the entropy of an image?" ... OK, it's the amount of information contained in the image ... but to better understand it, you should read something about the 3 phases usually used in image compression:

• transformation (for example Discrete Wavelet Transformation)
• quantization
• entropy encoding

You can use Google to search for a tutorial or book on Image compression (for example a quick tutorial), or try to watch an online technical video (for example Lecture 16 - Introduction to Image and Video coding).

Answer 6

Compression limit of an individual sequence

What is the compression limit of a sequence?

Two answers can be given to this question:

1. The compression limit of a sequence is an unsolved problem. Furthermore, it has been shown that this limit cannot be calculated.

2. Shannon defined a subproblem of great practical relevance, in which it is possible to define a theoretical limit (source coding theorem). This subproblem is purely probabilistic and is called source coding.

Definition of the information transfer problem in its most general form

To understand these two answers it is essential to introduce the problem of information transmission in its most general form. For the transmission of information to take place between two points, it is essential that the two subjects share a communication language. This requirement is necessary, without a language of communication, the transmitted message is not understood and therefore does not carry any information. Consequently, the information transmission problem, in its most general form, studies the transfer of information in any form between two points that share a language of communication.

The problem with this definition is that the concept of "information in any form" is difficult to formalize mathematically. For this reason, it is essential to introduce a first simplification of the problem, in which the information is defined as a numerical sequence. In this way, a subproblem is obtained, in which the concept of information is well-defined and can be formalized from the mathematical point of view.

Consequently, the two elements necessary for the transfer of information are: a compressed sequence which carries the information and a communication language known by both the encoder and the decoder.

Compressed sequence: represents any information derived from the sequence to be transmitted. From a practical point of view, any information obtained from the sequence that is useful for the decoder to go back to the original message must be considered part of the compressed message.

Communication language: represents a set of rules that allows communication and therefore the transfer of information between two subjects. From a practical point of view, any information present before the generation of the message can be considered part of the communication language.

Source coding

Shannon in his famous article “A Mathematical Theory of Communication” introduces a further modification to the information transfer problem, which allows him to obtain a subproblem in which it is possible to define the theoretical compression limit. For this purpose, Shannon introduces the source that generates the message. Furthermore, the coding scheme which converts the symbols into codewords is generated on the information of the source and not on the information obtained from the message. Therefore, the coding scheme being defined before the generation of the message can be considered as an integral part of the communication language. Then, Shannon formalizes the concept of information, for this purpose he develops a variable that uniquely defines the message transmitted in the presence of an encoding scheme. The solution developed by Shannon is to consider information as a measure of a variation. The function generated that performs this measurement is called entropy H. The following sentence, taken from the article "A Mathematical Theory of Communication”, makes us understand Shannon's idea of entropy.

“In the limiting case where one probability is unity (certainty) and all the others zero (impossibility), then H is zero (no uncertainty at all- no freedom of choice - no information).”

With regard to the subproblem he defined, Shannon manages to define a theoretical compression limit by developing the source coding theorem. This theorem proves that entropy defines the minimum average length of the codewords that replace the symbols in the compressed message. Thus, given a source X of random variables i.i.d. which generates a message of length N the compressed message cannot be longer than NH(X). The encoding scheme being defined before message generation is not part of the compressed message.

Application of the theory developed by Shannon when the source is not known When the source is not known, it is possible to calculate the zero order empirical entropy H0(m), in which the frequencies are obtained from the message m to be transmitted. In this case, using the frequencies of the symbols in the sequence the coding scheme is developed after the message has been generated therefore it must be part of the compressed message. Consequently, the compressed message is defined by NH0(M)+encoding scheme. Being the value of H0(m) very close to the value of H(X) the coding scheme represents a redundancy, which is also called inefficiency of the entropy coding. In practice, the non-knowledge of the source that generates the message determines the presence of a redundancy in the compressed message. Furthermore, the length of the coding scheme depends on the language used, therefore, it is not possible to define it precisely. Consequently, it’s not possible to define a limit on the length of the compressed message. Therefore, using the formalism introduced by Shannon, we have shown that the compression limit of a sequence whose source is unknown is not computable.

Difference between the source entropy H(X) and the zero order empirical entropy H0(m)

The value of NH(X) represents the compressed message. So entropy, in this case, defines message information in a more general sense, not just Shannon information. Unfortunately, this method does not represent the general case of information transmission, but represents a subproblem in which both the encoder and the decoder know the source that generates the message.

The value of NH0(m) does not represent the compressed message. Therefore, the zero-order empirical entropy represents only the average value of the Shannon information of the single symbol. Consequently, the zero-order empirical entropy has a less general meaning than the entropy of the source. However, in this case, the problem of information transmission is being addressed in a much more general way than in the case of source coding.

To demonstrate what has just been said, the following example is given: let us take a uniform source X of random variables i.i.d. which generates a message of length N. Of course, this sequence cannot be compressed. Thus, on average the compressed message must have a length greater than or equal to N. In the first case, the encoder and the decoder know the source and therefore we can apply the source encoding. The result obtained is that all the messages have length NH(X) and since H(X)=1 (we use the dimension of the alphabet as the base of the entropy) the compressed message has a length N. So, in this case , we reach the theoretical compression limit. In the second case,both the encoder and the decoder do not know the source. Consequently, the encoder must use the value of the frequencies of the symbols in the message to calculate the entropy. In this way, the zero order empirical entropy H0(m) is obtained. The source is uniform but only a small amount of the generated messages have uniform symbol distribution. Therefore, the average value of the zero-order empirical entropy H0(m) of the messages will be less than H(X). Consequently, if we do not consider the coding scheme as part of the compressed message, we obtain an illogical result, in fact, we have NH0(m)<N. In practice, we managed to compress a random sequence. The error depends on the fact that, in this second case, we obtained the coding scheme after the message was generated therefore, it must be part of the compressed message. In conclusion, to obtain a correct result, the compressed string must be defined by NH0(m)+coding scheme whose length is greater than N. Therefore, we have a redundancy due to non-knowledge of the source.

Modern approach to information theory

One of the most important aspects covered is to understand that source coding is a subproblem with respect to the problem of information transmission in its most general form. Consequently, when the source is not known, only the zero order empirical entropy can be calculated, a parameter that has a much more limited value than the entropy of the source. Indeed, the value obtained by multiplying the zero-order empirical entropy by the message length NH0(m) does not represent the compressed message. In this case, the coding scheme must also be part of the compressed message, having been defined after the generation of the message and therefore cannot be included in the communication language. This approach represents an important change of point of view. In fact, it was absolutely normal, even when the source was not known, to consider the compressed message only as NH0(m) without considering the coding scheme as is done with source coding.

This change of point of view was necessary with the arrival of a new theory that makes it possible to reduce the redundancy that is generated when the source is not known. This theory can only be applied when the alphabet is greater than or equal to 3. The purpose of this theory is to make the encoded sequence NH0(m) and the coding scheme interact with each other more efficiently.

Now, I will explain the basis of this theory. If we have to perform entropy coding on a sequence of length N and alphabet A, whose source we do not know, the only information we have is that the sequence will be part of one of |A|^N possible sequences. Thus, the only possible way for a transform, to improve on average the length of the compressed sequence (encoded sequence+coding scheme), using an entropic coding, is to transform the set of all possible sequences into a new set of the same size composed of sequences that on average can be compressed in less space. In this way, even if we don't know the source that generates the sequence, we know that if we apply this transform, we can, on average, obtain a compressed message of smaller length than the compressed message of the untransformed sequence.

The set having these characteristics is the set of dimension |A|^N composed of sequences of length N+K. Increasing the length of the sequence also increases the size of the set that includes all possible sequences, which becomes |A|^N+K. Therefore, from this set it is possible to select a subset of size |A|^N composed of sequences having the smallest value of the zero order empirical entropy .

In this way, we obtain the following result: given a message m of length N generated by a source X (unknown) of random variables i.i.d., applying the described transform f(m), we obtain on average:

NH(X)< Avg(NtH0(f(m)+ coding scheme)< Avg(NH0(m)+coding scheme)

With Nt>N

Avg(NH0(m)+coding scheme)=mean value of the encoded sequence m+coding scheme

Avg(NtH0(f(m)+ coding scheme)=mean value of the encoded transformed sequence f(m)+coding scheme

NH(X) is the compression limit that is not known, in fact, we have set the condition that the source is not known. As mentioned at the beginning, when the source is not known, in the current state of knowledge, it is not possible to define a compression limit.

Now, we prove the obtained result experimentally. Let's take a sequence of length 3 and alphabet 3, the possible sequences are 27. If we increase the length to 4 and keep the alphabet at 3, the possible sequences become 81. Of these 81, we select the 27 with the smallest value of H0(m). In this way, the two sets have the same number of elements. Thus, we can define a one-to-one relationship between the sequences of the two sets. The following table shows the 27 elements of the two sets. In the first column, we have message m, in the second column, we have NH0(m), in the third column, we have the transformed message f(m) and in the fourth column, we have NtH0(f(m)) of the transformed message f(m).

The average value of zero order empirical entropy multiplied by the string length N=3 of the messages m is: Avg(NH0(m))=2.893 with N=3. The average value of zero order empirical entropy multiplied by the length of the string Nt=4 of the transformed messages f(m) is: Avg(NtH0(f(m))=2.884 con Nt=4 Thus, you can see that although the transformed messages are longer, the average value of zero-order empirical entropy multiplied by the message length is, on average, smaller when the transform is applied. Consequently, even if we do not know the source, we know that by applying the transform, we obtain, on average, a reduction in the value of zero-order empirical entropy multiplied by the length of the message. Therefore, the length of the encoded message (symbols replaced by codewords) decreases.

Now, let's look at the encoding scheme, in this case making an evaluation is more difficult because the length of the encoding scheme depends on the compression method used. But, we know that, from a theoretical point of view, the parameter that most influences the length of the encoding scheme is the size of the alphabet. Therefore, we calculate the average size of the alphabet A in the two sets. The mean value of the alphabet size |A|, in the case of messages in the first column of the table, is: Avg(|A|)=2.1 The mean value of the alphabet size |A|, in the case of transformed messages f(m) in the third column of the table, is: Avg(|A|)=1.89 The result obtained is not valid only for the reported case. Indeed, whatever the size of the alphabet, the transformed set being composed of longer sequences always has a greater number of type classes with a number of symbols less than |A|. With type class, we mean a set of strings that all have the same symbol frequency, for example, string 113 and string 131 belong to the same type class in fact, both have symbol frequency 1=2/3 and 3=1/ 4.

Therefore, being on average NH0(f(m))<NH0(m) and coding scheme f(m) < coding scheme m, we have experimentally demonstrated the following inequality:

NH(X)< Avg(NH0(f(m)+ coding scheme)< Avg(NtH0(m)+coding scheme)

In this way, the set of transformed messages has an average compressed message length, using entropy encoding, less than the set of untransformed messages. Consequently, when the source is not known, if the described transform is applied, a reduction of the compressed message is obtained on average. Therefore, we are able to reduce the inefficiency caused by not knowing the source.

In conclusion, the question we posed at the beginning, about the existence of a minimum compression length of a sequence, represents a problem that has not yet been solved. However, new developments regarding the theory of information, managing to reduce the inefficiency that is created when we don’t know the source, have made it possible to take a significant step forward on this topic.