Huffman Coding

Introduction: the problem with fixed-length codes

Digital information, including text, is represented as sequences of bits. A simple way to represent text is a fixed-length code. The ASCII standard defines unique 7-bit codes for characters, digits, and punctuation marks. Systems often store each ASCII character in an 8-bit byte with a leading zero. The character 'A' is 65 (01000001), 'B' is 66 (01000010), and so on.

A fixed-length code assigns the same number of bits to symbols with different frequencies. A common letter such as 'e' receives as much space as a rare character such as 'Z' or a symbol such as '{'. Claude Shannon's work showed that language has an uneven frequency distribution. This distribution contains redundancy that can be used for more efficient text coding. Huffman coding assigns shorter codes to frequent symbols.

The core idea: variable-length coding

David A. Huffman described the method in 1952 as a student. Huffman coding is a statistical lossless compression method.

The central rule is:

As a result, the average number of bits per symbol can be lower than with a fixed-length code. An implementation needs a method for generating the codes and a decoder that can identify them without ambiguity.

Unambiguous decoding and prefix codes

Variable-length codes require a rule that identifies where one code ends and the next one begins.

For example, suppose we have the codes A=0, B=1, C=01. If the decompressor reads the bitstream '01', does that mean "A" followed by "B", or does it mean "C"? This ambiguity makes the code useless.

Huffman coding solves this by creating a prefix code. In a prefix code, no codeword is the beginning of another codeword. If 'A' has code '0', no other code can start with '0'. If 'B' has code '10', no other code can start with '10'. This property removes ambiguity. Once the decoder matches a valid codeword, it has identified a complete symbol without a separator or extra lookahead. Huffman's algorithm generates an optimal prefix code for a given frequency distribution.

The Huffman algorithm

Let us build a Huffman code using the string THIS IS AN EXAMPLE OF A HUFFMAN TREE. The process has four stages: analyzing symbol frequencies, building a binary tree, assigning codes, and encoding the message.

Step 1: frequency analysis

First, count every unique character in the source string. The space character is also a data symbol and must be included.

Step 2: constructing the Huffman tree

This stage builds a binary tree from the bottom up using the frequencies. The greedy algorithm selects the two nodes with the smallest combined frequency at each step.

1. Begin with a list of "free" nodes, where each node is a leaf representing a character and its frequency.
2. Select the two nodes with the lowest frequencies from the list.
3. Create a new internal node that is the parent of these two selected nodes.
4. The frequency of this new parent node is the sum of the frequencies of its two children.
5. Remove the two child nodes from the free list and add the new parent node to it.
6. Repeat steps 2-5 until there is only one node left in the list. This final node is the root of the Huffman tree.

Iterative merging places low-frequency symbols farther from the root, so they receive longer codes. Frequent symbols remain closer to the root and receive shorter codes.

Step 3: assigning the codes

With the completed tree, traverse from the root to each leaf. By convention, label each left branch '0' and each right branch '1'. The bit sequence on the path to a leaf is that symbol's Huffman code.

One valid construction of the tree for this example gives the following code table:

The most frequent characters (space, A, and E) have 3-bit codes. Characters that occur once have 5-bit codes. This distribution reduces the average code length.

Step 4: encoding and measuring the results

The final step is to encode the message. Replace each character in the original string with its Huffman code and concatenate the codes into one bitstream.

The string "THIS IS AN EXAMPLE OF A HUFFMAN TREE" has 36 characters. For comparison, assume 8 storage bits per character. The original size is:

The compressed size is the sum of the Huffman code lengths for all characters:$(7 \times 3) + (4 \times 3) + (4 \times 3) + (3 \times 4) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (2 \times 4) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) + (1 \times 5) = 135 \text{ bits}$

The compression ratio is:

In this example, the code stream is less than half the length of the 8-bit representation. The result also depends on the frequency table overhead.

The value of 135 bits covers the code stream itself. A file also needs a description of the code table or tree, and the final byte may require padding. Equal frequencies can produce different Huffman trees; when their code lengths are the same, the bit total remains the same.

The decoder must receive the same coding model. For short inputs, metadata can therefore reduce or reverse the saving from a shorter code stream.

The bit order follows the character order in the message, while the code table lets the decoder recover symbol boundaries. Swapping the left and right branch labels changes the codewords but not their lengths or the total for the tree.

Strengths, weaknesses, and the role of Huffman coding

Huffman coding has specific strengths and limitations. Its behavior depends on the symbol frequencies and on the format in which it is used.

Strengths

• Optimal prefix code: For a fixed set of frequencies, Huffman's algorithm generates a binary prefix code with the shortest average length among codes of this type.
• Simplicity and speed: The algorithm has a simple implementation, and encoding and decoding can use a tree or a code table.
• Public method description: The basic method was described in a 1952 publication. Licensing terms for a particular format can be separate.

Weaknesses and limitations

• Two-pass requirement: The static version requires the frequencies before encoding. This usually means one read to build the frequency table and a second read to encode the data. Adaptive Huffman variants update the table while processing the stream.
• Overhead of Storing the Tree: To decompress the data, the receiver must have the exact same Huffman tree (or frequency table) that was used for compression. This information must be sent along with the compressed data, adding overhead which can diminish the compression gains, especially for small files.
• Integer code lengths: Entropy can be fractional, but Huffman assigns an integer number of bits to each symbol. The result can therefore remain above the entropy bound. Arithmetic coding can approach that bound more closely.
• No context model: The basic algorithm treats symbols independently of their neighbors. It does not use higher-order dependencies, such as the high likelihood of 'u' after 'q' in English.

Applications

Huffman coding can operate as a standalone method, but it is often one stage of a larger compression system. Its role is to encode a symbol stream according to a frequency model. Examples include:

• In JPEG profiles that use Huffman coding, it compresses quantized DCT coefficients.
• In the Deflate algorithm (used by ZIP, gzip, and PNG), Huffman coding is used to compress the stream of literals and length/distance pointers produced by the LZ77 dictionary stage.

In these applications, Huffman coding remains an entropy-coding method with a simple structure and a defined optimality result for prefix codes.