Huffman Coding - Introduction to Data Compression - page 84

T A B L E 3 . 35 Huffman coding of differences of 16-bit CD-quality audio.

Original Entropy Estimated Compressed Compression

File Name File Size (bytes) of Differences (bits) File Size (bytes) Ratio

Mozart 939,862 09.7 569,792 1.65

Cohn 402,442 10.4 261,590 1.54

Mir 884,020 10.9 602,240 1.47

Note that there is a further reduction in the file size: the compressed file sizes are about
60% of the original files. Further reductions can be obtained by using more sophisticated
models.
Many of the lossless audio compression schemes, including FLAC (Free Lossless Audio
Codec), Apple's ALAC or ALE, Shorten [ 32 ], Monkey's Audio , and the MPEG-4 ALS [ 33 ]
algorithms, use a linear predictive model to remove some of the structure from the audio
sequence and then use Rice coding to encode the residuals. Most others, such as AudioPak
[ 34 ] and OggSquish , use Huffman coding to encode the residuals.

3.9 Summary

In this chapter we began our exploration of data compression techniques with a description
of the Huffman coding technique and several other related techniques. The Huffman coding
technique and its variants are some of the most commonly used coding approaches. We will
encounter modified versions of Huffman codes when we look at compression techniques for
text, image, and video. In this chapter we described how to designHuffman codes and discussed
some of the issues related to Huffman codes. We also described how adaptive Huffman codes
work and looked briefly at some of the places where Huffman codes are used. We will see
more of these in future chapters.
To explore further applications of Huffman coding, you can use the programs huff_enc ,
huff_dec , and adap_huff to generate your own Huffman codes for your favorite
applications.

Further Reading

1. A detailed and very accessible overview of Huffman codes is provided in “Huffman
Coding,” by S. Pigeon [ 35 ], in Lossless Compression Handbook .

2. Details about nonbinary Huffman codes and a much more theoretical and rigorous de-
scription of variable-length codes can be found in The Theory of Information and Coding ,
Vo l um e 3 o f Encyclopedia of Mathematics and Its Application , by R.J. McEliece [ 9 ].

3. The tutorial article “Data Compression” in the September 1987 issue of ACMComputing
Surveys , by D.A. Lelewer and D.S. Hirschberg [36], along with other material, provides
a very nice brief coverage of the material in this chapter.