**Lossless data compression** refers to data compression algorithms which allow the original data to be reconstructed *exactly* from the compressed data. Contrast with lossy data compression.

Lossless data compression is used in software compression tools such as the highly popular Zip format, used by PKZIP and WinZip, and the Unix programs bzip2, gzip and compress. Lossless compression is used when it is important that the original and the decompressed data are exactly identical, or when no assumption can be made on whether certain deviation is uncritical. Typical examples are executable programs and source code. Some image file formats, notably PNG, use only lossless compression, while others like TIFF and MNG may use either lossless or lossy methods. GIF uses a technically lossless compression method, but most GIF implementations are incapable of representing full color, so they quantize the image (often with dithering) to 255 or fewer colors before encoding as GIF. Color quantization is a lossy process, but reconstructing the color image and then re-quantizing it produces no additional loss. (Some rare GIF implementations make multiple passes over an image, adding 255 new colors on each pass.)

## Lossless data compression makes some files longer

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*, as follows:

- Assume that each file is represented as a string of bits of some arbitrary length.
- Suppose that there is a compression algorithm that transforms every file into a distinct shorter file. (If the output files are not all distinct, the compression cannot be reversed without losing some data).
- Consider the set of all files of length at most
*N*bits. This set has*1 + 2 + 4 + ... + 2*members, if we include the zero-length file.^{N}= 2^{N+1}-1 - Now consider the set of all files of length at most
*N-1*bits. There are*1 + 2 + 4 + ... + 2*such files, if we include the zero-length file.^{N-1}= 2^{N}-1 - But this is smaller than
*2*. We cannot map all the members of the larger set uniquely into the members of the smaller set.^{N+1}-1 - This contradiction implies that our original hypothesis (that the compression function makes all files smaller) must be untrue.

*N*as the input set: it is still larger (

*2*members) than the desired output set.

^{N}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 set, and this argument still holds.

Thus any lossless compression algorithm that makes some files shorter must
necessarily make some files *longer*. Good compression algorithms are those that achieve shorter output on input distributions that occur in real-world data.

## Lossless compression techniques

Statistical modelling algorithms for text (or text-like binary data such as executables) include:

- Burrows-Wheeler transform (block sorting preprocessing that makes compression more efficient)
- DEFLATE
- LZW

Many of the lossless compression techniques used for text also work reasonably well for indexed images, but there are other techniques that do not work for typical text that are useful for some images (particularly simple bitmaps), and other techniques that take advantage of the specific characteristics of images (such as the common phenomenon of contiguous 2-D areas of similar tones, and the fact that colour images usually have a preponderance to a limited range of colours out of those representable in the colour space).

As mentioned previously, lossless sound compression is a somewhat specialised area. Lossless sound compression algorithms can take advantage of the repeating patterns shown by the wave-like nature of the data - essentially using models to predict the "next" value and encoding the (hopefully small) difference between the expected value and the actual data. If the difference between the predicted and the actual data (called the "error") tends to be small, then certain difference values (like 0, +1, -1 etc. on sample values) become very frequent, which can be exploited by encoding them in few output bits.

It is sometimes beneficial to compress only the differences between two versions of a file (or, in video compression, of an image). This is called delta compression (from the Greek letter &Delta which is commonly used in mathematics to denote a difference), but the term is typically only used if both versions are meaningful outside compression and decompression. For example, while the process of compressing the error in the above-mentioned lossless audio compression scheme could be described as delta compression from the approximated sound wave to the original sound wave, the approximated version of the sound wave is not meaningful in any other context.

*See also:* Lossy data compression, Lossless Transform Audio Compression (LTAC), audio compression, David A. Huffman.