Lossless data compression

Lossless data compression is a type of data compression algorithm structured in such a way that the original data may be reconstructed exactly from the compressed data. It is used in software compression tools such as the highly popular zip format, used by PKZIP and Winzip, and the Unix programs gzip and compress. Lossless compression is used when every byte of the data is important, such as executable programs and source code. Some image file formats, notably PNG, use only lossless compression, while others like TIFF? may use either lossless or lossy methods. GIF uses a technically lossless compression method, but it is incapable of representing full color, so images must be quantized? (often with dithering?) to a small number of colors (a very lossy process) before encoding as GIF.

Lossless data compression algorithms cannot guarantee to compress (that is make smaller) all input data sets. In other words for any (lossless) data compression algorithm there will be an input data set that does not get smaller when processed by the algorithm. This is easily proven with elementary mathematics using a counting argument.

Assume that files can have lengths that are arbitary numbers of bits. Consider the set of all binary files of length N bits, which has 2^N members. Assume, for the sake of argument, that a given compression function maps every one of these to a distinct shorter file of at most N-1 bits. (If the output files are not all distinct, the compression cannot be reversed without losing some data).

Now consider the set of all files of length at most N-1 bits. How many members are there in this set?

There are 1 + 2 + 4 + ... + 2^N-1 = 2^N-1 such files, if we include the zero-length file in the set. But this is smaller than 2^N. So we cannot map all the members of the larger set into the members of the smaller set. This contradiction implies that our original hypothesis (that the compression function makes all files smaller) must be untrue.

If we make all the files a multiple of 8 bits long (as in standard computer files) there are even fewer files in the smaller subset, and this argument still holds.

see also: lossy data compression