16-03-2012, 02:32 PM
Introduction to Data Compression
compression.pdf (Size: 376.64 KB / Downloads: 49)
Introduction
Compression is used just about everywhere. All the images you get on the web are compressed,
typically in the JPEG or GIF formats, most modems use compression, HDTV will be compressed
using MPEG-2, and several file systems automatically compress files when stored, and the rest
of us do it by hand. The neat thing about compression, as with the other topics we will cover in
this course, is that the algorithms used in the real world make heavy use of a wide set of algorithmic
tools, including sorting, hash tables, tries, and FFTs. Furthermore, algorithms with strong
theoretical foundations play a critical role in real-world applications.
Information Theory
2.1 Entropy
Shannon borrowed the definition of entropy from statistical physics to capture the notion of how
much information is contained in a and their probabilities. For a set of possible messages S,
Shannon defined entropy1 as,
The Entropy of the English Language
We might be interested in how much information the English Language contains. This could be
used as a bound on how much we can compress English, and could also allow us to compare the
density (information content) of different languages.
Conditional Entropy and Markov Chains
Often probabilities of events (messages) are dependent on the context in which they occur, and
by using the context it is often possible to improve our probabilities, and as we will see, reduce
the entropy. The context might be the previous characters in text (see PPM in Section 4.5), or the
neighboring pixels in an image (see JBIG in Section 4.3).
compression.pdf (Size: 376.64 KB / Downloads: 49)
Introduction
Compression is used just about everywhere. All the images you get on the web are compressed,
typically in the JPEG or GIF formats, most modems use compression, HDTV will be compressed
using MPEG-2, and several file systems automatically compress files when stored, and the rest
of us do it by hand. The neat thing about compression, as with the other topics we will cover in
this course, is that the algorithms used in the real world make heavy use of a wide set of algorithmic
tools, including sorting, hash tables, tries, and FFTs. Furthermore, algorithms with strong
theoretical foundations play a critical role in real-world applications.
Information Theory
2.1 Entropy
Shannon borrowed the definition of entropy from statistical physics to capture the notion of how
much information is contained in a and their probabilities. For a set of possible messages S,
Shannon defined entropy1 as,
The Entropy of the English Language
We might be interested in how much information the English Language contains. This could be
used as a bound on how much we can compress English, and could also allow us to compare the
density (information content) of different languages.
Conditional Entropy and Markov Chains
Often probabilities of events (messages) are dependent on the context in which they occur, and
by using the context it is often possible to improve our probabilities, and as we will see, reduce
the entropy. The context might be the previous characters in text (see PPM in Section 4.5), or the
neighboring pixels in an image (see JBIG in Section 4.3).