Math
Huffman coding
A sorted queue of frequencies becomes a prefix-code tree. Select a symbol to trace its bits; step through each merge.
What happens
Each step combines the two smallest weights. Branches labelled 0 and 1 define the code from the root to a symbol. Selecting a letter highlights that entire path. Change frequencies and compare the result. L is the mean code length; H is entropy. Huffman minimizes L among binary prefix codes for these individual symbols, even when L is greater than H. Equality holds for probabilities of the form 2^(-k). The displayed bit count excludes the code table and file headers.
Equations used in the module
Equations build: merge the two lightest nodes, n−1 times; the code of a symbol is its path from the root, left 0, right 1 L = Σ p(i)·l(i) (bits per symbol); H = −Σ p(i)·log₂ p(i); the code length l(i) is the depth of the leaf Kraft: any prefix code has Σ 2^(−l(i)) ≤ 1, and any such vector is a tree; Huffman's tree is full, so the sum is exactly 1 H ≤ L < H + 1 always; L = H exactly when every p(i) is a power of two optimality is checked against a search over ALL Kraft-admissible length vectors - the search knows nothing of the algorithm equal frequencies: 2(n − 2^k) symbols get the long code, where 2^k is the largest power of two below n Fibonacci frequencies 1, 1, 2, 3, 5, … give the most lopsided tree: lengths n−1, n−1, n−2, …, 1
