History of Lossless data compression

HomePage | Recent Changes | Preferences

	Revision 12 . . December 8, 2001 2:28 pm by (logged).112.129.xxx [Lossless truecolor GIF exists]
	Revision 11 . . December 7, 2001 11:34 pm by The Anome [reformat]
	Revision 10 . . December 7, 2001 10:37 pm by The Anome [put maths into italics]
	Revision 9 . . (edit) December 7, 2001 10:18 pm by Magnus Manske [cleanup, mention huffman]
	Revision 8 . . (edit) November 28, 2001 5:15 pm by The Anome
	Revision 7 . . (edit) November 28, 2001 5:14 pm by The Anome [oops fixed + copyedit]
	Revision 6 . . November 28, 2001 5:11 pm by The Anome [simplified counting argument]
	Revision 5 . . (edit) November 28, 2001 5:06 pm by The Anome [added mention of dithering]
	Revision 4 . . November 28, 2001 5:00 pm by The Anome [wrote informal counting argument proof]
	Revision 3 . . (edit) October 30, 2001 10:31 pm by (logged).148.1.xxx

Difference (from prior major revision) (no other diffs)

Changed: 1c1,8

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. One of the most used algorithms is Huffman coding. 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 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 is a type of data compression algorithm structured in such a way that the original data may be reconstructed exactly from the compressed data.
One of the most used algorithms is Huffman coding.
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 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? 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.)

Changed: 14c21

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.