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? 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. So someone should insert a well written proof here.

see also: lossy data compression