Coding - Compression
7.9. The whole story!

The details of how several compression systems work have been glossed over in this chapter, as we have been more concerned about the file sizes and speed of the methods than how they work. A closely related system is Arithmetic coding (there's an explanation of it here). Also, video compression has been mentioned only briefly, even though compressing videos saves more space than most kinds of compression. Most video compression is based on the "MPEG" standard (Moving Pictures Experts Group). There is some information about how this works in the CS4FN article on "Movie Magic".

The Ziv-Lempel method shown is a variation of the so-called "LZ77" method. Many of the more popular lossless compression methods are based on this, although there are many variations, and one called "LZW" has also been used a lot. Another high-compression general-purpose compression method is bzip, based on a very clever method called the Burrows-Wheeler Transform.

Questions like "what is the most compression that can be achieved?" are addressed by the field of information theory. There is an activity on information theory on the CS Unplugged site, and there is a fun activity that illustrates information theory. Based on this theory, it seems that English text can't be compressed to less than about 12% of its original size at the very best. Images, sound and video can get much better compression because they can use lossy compression, and don't have to reproduce the original data exactly.