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

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.

• I'm not sure if Theoretical Computer Science is the best site to ask this kind of questions. Feel free to vote on close or to migrate this question to a more suitable site, if necessary. – Auron Jun 17 '11 at 16:25
• This may be what you're looking for: en.wikipedia.org/wiki/Entropy_encoding. The key word is entropy. – Hsien-Chih Chang 張顯之 Jun 17 '11 at 16:33
• I don't know what would be a more suitable site, unfortunately. The quantization error is a source of entropy which would probably preclude large compression ratios. – Peter Shor Jun 17 '11 at 17:12
• Do you need lossless data compression for which kind of data? Images, music, speech, generic data, ... ? However, for a high level introduction see data-compression.com/theory.html (and resources at the bottom of the pages) – Marzio De Biasi Jun 17 '11 at 18:32
• @Vor Images. More specifically, medical images. I'll take a look to that page. Thanks. – Auron Jun 18 '11 at 8:30

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.

• cool! if the noise is gaussian, my feeling is that projecting on the first k singular vectors (or a similar more fancy technique) would remove a lot of the noise. a quick google scholar search revealed an article by M. Elad and M. Aharon, that uses the projection method + some Bayesian stats trickery: ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4011956. supposedly, in 2006 it was "state of the art". of course, it's not lossless, but Jukka's data shows that if you insist on small size you need to lose at least the noise. – Sasho Nikolov Jun 18 '11 at 23:37
• Your examples are only about lossless compression of images. I will reluctantly grant you their generalization to any data coming from physical sensors (sound, image, video, yet probably with a distinct factor) but there are (many?) other fields where compression is applied, with a much better ratio than 1:2 (natural language comes to mind), because there is less noise. – Jeremy Jun 19 '11 at 4:14
• @Jukka: +1: Beautiful experiment! @Sasho: for medical images, the conventional wisdom is that you can't lose anything, even if it's very likely just noise. – Peter Shor Jun 19 '11 at 14:18
• Very nice and clear explanation! – Marzio De Biasi Jun 19 '11 at 20:50
• One more comment: this is really unavoidable for medical images. If you don't use enough precision to have a substantial amount of this noise in medical images, then you're probably losing some actual relevant detail, which you would really want to keep. – Peter Shor Jun 22 '11 at 12:23

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.

• I didn't know about that theorem. I guess Wikipedia's claim is not exactly correct, as the achievable compression ratio depends on the entropy of the data to be compressed. – Auron Jun 18 '11 at 8:35
• I believe it's really quite hard to determine the intrinsic entropy of images -- it's much easier if the data is linear rather than 2-D. – Peter Shor Jun 18 '11 at 17:17
• So, what would be the maximum compression ratio for a randomly (uniform) generated text? – skan May 4 '17 at 19:16

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 :)

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.

(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. ...

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).