Data Compression

Application Areas

Data compression is used in a wide variety of applications. WinZip and Gzip are commonly used file compression utilities on computers. Images on the Internet and in many cameras are compressed using the JPEG algorithm. Video conferencing is conducted using compressed video. Cell phones use compression techniques to provide service under limitation of bandwidth. Digital television broadcasts would not be feasible without compression. In fact, compression is the enabling technology for the multimedia revolution.

Compression Approaches

Compression can be viewed, and compression techniques classified, in terms of the models used in the compression process and how those models are obtained. We can focus on the data, examining the different kinds of structures that exist in the data without reference to the source of the data. We will call these approaches data modeling approaches. We can try to understand how the data are generated and exploit the source model for the development of data compression algorithms. Finally, we can examine the properties of the data user because these properties will impose certain constraints on the data. We begin by looking at techniques based on properties gleaned from the data.

Data Modeling Approaches

With different applications, we get different kinds of structure in the data that can be used by the compression algorithm. The simplest form of structure occurs when there is no symbol-to-symbol dependence; however, the data symbols take on different values with differing probabilities. Compression schemes that make use of this statistical skew include Huffman coding and arithmetic coding.

Huffman coding, developed as a class project by David Huffman, assigns short codewords to symbols occurring more often and long codewords to symbols that occur less often. Let's look at the example in Table 1. There are five symbols in the original file. If we were to represent them using a fixed-length code, we would need three binary digits to represent each symbol. However, if we assign codewords of different lengths to each symbol according to their probability, as shown in Table 1, the average length (l) of binary bits needed to represent a symbol will be

...