9.14* Case study: Huffman coding

One can often gain an improvement in space requirements in exchange for a penalty in running time. There are many situations where this is a desirable tradeoff. A typical example is storing files on disk. If the files are not actively used, the owner might wish to compress them to save space. Later, they can be uncompressed for use, which costs some time, but only once.

We often represent a set of items in a computer program by assigning a unique code to each item. For example, the standard Latin-1 scheme (the formal name is ISO 8859-1) assigns a unique eight-bit value to each character. It takes a certain minimum number of bits to provide enough unique codes so that we have a different one for each character. For example, it takes \left\lceil \log\ 256\right\rceil or eight bits to provide the 256 unique codes needed to represent the 256 symbols of the Latin-1 character set.

The requirement for \left \lceil \log\ n \right\rceil bits to represent n unique code values assumes that all codes will be the same length, as are Latin-1 codes. These are called fixed-length codes. If all characters were used equally often, then a fixed-length coding scheme is the most space efficient method. However, you are probably aware that not all characters are used equally often in many applications. For example, the various letters in an English language document have greatly different frequencies of use.

Table 9.1 below shows the relative frequencies of the letters of the alphabet. From this table we can see that the letter ‘E’ appears about 60 times more often than the letter ‘Z’. In normal Latin-1, the words “DEED” and “MUCK” require the same amount of space (four bytes). It would seem that words such as “DEED”, which are composed of relatively common letters, should be storable in less space than words such as “MUCK”, which are composed of relatively uncommon letters.

If some letters are used more frequently than others, is it possible to take advantage of this fact and somehow assign them shorter codes? The price could be that other letters require longer codes, but this might be worthwhile if such letters appear rarely enough. This concept is at the heart of file compression techniques in common use today. In this section we present one such approach to assigning variable-length codes, called Huffman coding.

While it is not commonly used in its simplest form for file compression (there are better methods), Huffman coding gives the flavor of such coding schemes. One motivation for studying Huffman coding is because it provides our first opportunity to see a type of tree structure referred to as a search trie.

To keep things simple, the following examples for building Huffman trees uses a sorted list to keep the partial Huffman trees ordered by frequency. But a real implementation would use a priority queue keyed by the frequencies.

datatype HuffmanTree:
    weight: Int
    value: T
    left: HuffmanTree
    right: HuffmanTree

buildHuffmanTree(frequencies):
    // Initialise a min-heap with Huffman leaves.
    huffmanHeap = new MinHeap()
    for each pair (char, freq) in frequencies:
        huffmanHeap.add(new HuffmanTree(freq, char, null, null))

    // Iterate until there is only one tree left on the heap.
    while huffmanHeap.size > 1:
        // Remove the two minimum trees from the heap.
        t1 = huffmanHeap.removeMin()
        t2 = huffmanHeap.removeMin()
        weight = t1.weight + t2.weight
        // Combine the trees and add the new tree to the heap.
        t3 = new HuffmanTree(weight, null, t1, t2)
        huffmanHeap.add(t3)

    // Return the final Huffman tree.
    return huffmanHeap.removeMin()

9.14.5 How efficient is Huffman coding?

In theory, Huffman coding is an optimal coding method whenever the true frequencies are known, and the frequency of a letter is independent of the context of that letter in the message. In practice, the frequencies of letters in an English text document do change depending on context. For example, while E is the most commonly used letter of the alphabet in English documents, T is more common as the first letter of a word. This is why most commercial compression utilities do not use Huffman coding as their primary coding method, but instead use techniques that take advantage of the context for the letters.

Another factor that affects the compression efficiency of Huffman coding is the relative frequencies of the letters. Some frequency patterns will save no space as compared to fixed-length codes; others can result in great compression. In general, Huffman coding does better when there is large variation in the frequencies of letters.

The average expected cost per letter, c, is the sum of the cost for each letter (c_i) times the probability of its occurring (p_i), or c_1 p_1 + c_2 p_2 + \cdots + c_n p_n. Usually we measure the cost as the number of bits that is needed to encode one letter. The formula can be reorganised as follows, where f_i is the (relative) frequency of letter i and f_T is the total for all letter frequencies:

\frac{c_1 f_1 + c_2 f_2 + \cdots + c_n f_n}{f_T}

Huffman coding for all Latin-1 symbols should do better than the 8-letter example. The letter frequencies are atypical in that there are too many common letters compared to the number of rare letters.

Huffman coding of a normal English text usually yields an expected cost of around 4.5 bits per character, compared to the standard way of encoding each letter in 8 bits. So, Huffman coding of a typical English text file will save at least 40% over Latin-1 coding. Huffman coding for a binary file (such as a compiled executable, an image or a video) would have a very different set of distribution frequencies and so would have a different space savings. Most state-of-the-art compression programs use two or three coding schemes to adjust to different types of files.

In decoding example, “DEED” was coded in 8 bits, a saving of 33% over the twelve bits required from a fixed-length coding. However, “MUCK” would require 18 bits, more space than required by the corresponding fixed-length coding. The problem is that “MUCK” is composed of letters that are not expected to occur often. If the message does not match the expected frequencies of the letters, than the length of the encoding will not be as expected either.

9.14.6 Proof of optimality for Huffman coding

Huffman tree building is an example of a greedy algorithm. At each step, the algorithm makes a “greedy” decision to merge the two subtrees with least weight. This makes the algorithm simple, but does it give the desired result? This concludes with a proof that the Huffman tree indeed gives the most efficient arrangement for the set of letters. The proof requires the following lemma.

Using this lemma we can prove the following theorem: