CSFG
English Deutsch Beta Español Beta język polski (2.6.0)
Chapters Curriculum Guides Appendices

Coding - Compression
7.8. The whole story!

Coding - Compression

  • 7.1. What's the big picture?
  • 7.2. Run length encoding
  • 7.3. Huffman coding
  • 7.4. Lossy vs Lossless compression
  • 7.5. Image compression using JPEG
  • 7.6. General purpose compression
  • 7.7. Audio compression
  • 7.8. The whole story!
  • 7.9. Further reading

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.

Previous:
Audio compression
Next:
Further reading

Looking for something for primary schools? Check out CS Unplugged.

The Computer Science Field Guide is an online interactive resource for high school students learning about computer science.

Useful Links

  • About
  • Chapters
  • Interactives
  • Curriculum Guides

Community

  • Twitter
  • YouTube
  • GitHub

Help

  • Search
  • Glossary
  • Feedback

Switch to teacher mode

English | Deutsch | Español | język polski (2.6.0)

The Computer Science Field Guide material is open source on GitHub, and this website's content is shared under a Creative Commons Attribution-ShareAlike 4.0 International license. The Computer Science Field Guide is a project by the Computer Science Education Research Group at the University of Canterbury, New Zealand. Icons provided generously by icons8.

3.12.6

This definition is not available in English, sorry!