Huffman Trees

Huffman trees

Each node may have a weight. For a binary tree with $n$ leaves of weights $w_k$, let $l_k$ be the path length from the root to leaf $k$. Its weighted path length is:

David Huffman developed Huffman trees in 1952. For a fixed set of leaves and weights, a Huffman tree minimizes weighted path length and is also called an optimal binary tree.

For example, leaves of weights $\{1,2,3,4,5\}$ can form several differently shaped binary trees.

WPL = 21

WPL = 45

WPL = 9

How can we ensure minimum weighted path length? In general, lower-weight leaves should be farther from the root and higher-weight leaves closer to it. The same leaves can admit more than one Huffman tree.

Constructing a Huffman tree

Repeatedly merge the two trees with the smallest weights.

Consider six leaves with weights 2, 3, 7, 9, 18 and 25.

First, treat every leaf as an independent single-node tree. Together they form a forest.

Next, remove the two minimum-weight roots, create a parent whose weight is their sum, and put the new tree back into the forest. Repeat until only one tree remains.

Huffman trees have these properties:

1. No node has degree 1.

2. Exchanging the left and right subtrees of any internal node still produces a Huffman tree.

3. The same weights may yield non-isomorphic Huffman trees.

Huffman coding

Huffman coding compresses information for storage and transmission. Understanding it starts with how information is represented.

Computers represent text, images, audio and video with binary digits: 0 and 1.

Converting information into a binary representation is called encoding. ASCII uses 7-bit codes, commonly stored in 8-bit bytes. For example, APPLE is represented in bytes as 01000001 01010000 01010000 01001100 01000101.

ASCII is a fixed-length code: every character uses the same number of bits. Fixed-length codes are easy to design and read, but storage and transmission bandwidth are limited, and long encodings consume resources.

Variable-length codes can reduce total length by assigning shorter codes to more frequent characters. They cannot be assigned arbitrarily: if one code is a prefix of another, decoding can become ambiguous.

Huffman coding is variable-length and prefix-free. No character code is the prefix of another, so decoding is unambiguous and the total length is minimal for the given symbol frequencies among binary prefix codes.

The code is not a fixed universal alphabet. It is generated from the character frequencies of a particular message using a Huffman tree.

Suppose A, B, C, D, E and F occur 2, 3, 7, 9, 18 and 25 times. Use them as leaves with those frequencies as weights. Label left branches 0 and right branches 1. Each root-to-leaf path becomes that character's binary code.

Every character occupies a leaf. No root-to-leaf path contains another such path, so their codes cannot be prefixes of each other.