Huffman coding is a lossless compression method that gives shorter codes to more frequent symbols, minimizing the average code length. Build the code table from symbol probabilities and compare it with the entropy, the theoretical lower bound.
Favorites and recently used calculators are stored only in this browser (localStorage).
Results
Entropy H (per symbol)
–
Average code length L (per symbol)
–
Efficiency (H ÷ L)
–
Fixed-length code length
–
Length relative to fixed-length
–
Total bits for the text
–
Merging steps
When nodes have equal probabilities, the one entered first is taken first. Which one is merged first can change the codes but never the average code length. If the probabilities do not add up to 1, they are divided by their sum.
See it as a graph
Other inputs stay at their current values while the chosen input varies from 1/4 to 4 times its current value. The red dot is the current value.
How a Huffman code is built
Each symbol becomes a leaf weighted by its probability. Take the two nodes with the smallest probabilities and merge them into a new node whose probability is their sum, and repeat until one node remains. The result is a tree; reading the 0s and 1s on the branches from the root to a leaf gives that symbol's code. In the "Three symbols" example, 0.1 and 0.3 merge into 0.4, then 0.4 and 0.6 merge, so A gets 1 bit and B and C get 2 bits each.
Entropy and average code length
The entropy of a source, H = −Σ p log2 p, is the theoretical lower bound on bits per symbol. A Huffman code's average length L is known to satisfy H ≤ L < H + 1. In the "Three symbols" example, H ≈ 1.296 bits and L = 0.6 × 1 + 0.3 × 2 + 0.1 × 2 = 1.4 bits, an efficiency of about 92.5%. When every probability is a negative power of two (1/2, 1/4, …), L = H.
Prefix codes and unique decoding
A Huffman code is a prefix (instantaneous) code: no codeword is the beginning of another, so a bit string can be decoded uniquely just by reading from the start, with no separators. By the Kraft inequality, the sum of 2^(−l) over the codeword lengths l is at most 1, and for a Huffman code it is exactly 1.
Where it is used
Huffman coding is used together with other methods in Deflate (used by ZIP and PNG) and in JPEG's entropy coding, among others. Because each symbol gets a whole number of bits, the gap from the entropy grows for very skewed probabilities (such as 0.9). Arithmetic coding, or coding several symbols together as one, is used in such cases.
A Huffman code repeatedly merges the two smallest probabilities. 0.1 and 0.2 are merged into 0.3, then 0.3 and 0.3 into 0.6, and finally 0.6 and 0.4, so the code lengths are 1 bit for A, 2 bits for B and 3 bits for C and D. The average code length is 0.4 × 1 + 0.3 × 2 + 0.2 × 3 + 0.1 × 3 = 1.9 bits.
First 0.1 and 0.15 are merged into 0.25, then 0.2 and 0.25 into 0.45, the remaining 0.25 and 0.3 into 0.55, and finally 0.45 and 0.55. The code lengths are 2 bits for A, B and C and 3 bits for D and E, and the average code length is (0.3 + 0.25 + 0.2) × 2 + (0.15 + 0.1) × 3 = 1.5 + 0.75 = 2.25 bits. For a source whose probabilities are not strongly skewed, a code with nearly equal lengths is shorter than one with stepped lengths such as 1, 2, 3, 4, 4.
The Huffman code merges 0.1 and 0.3 into 0.4 and then 0.4 and 0.6, so the code lengths are 1 bit for A and 2 bits for B and C. The average code length is 0.6 × 1 + 0.3 × 2 + 0.1 × 2 = 1.4 bits, and the efficiency is 1.30 ÷ 1.4 ≈ 0.93, that is, about 93%. The remaining 7% or so is waste that arises because code lengths are limited to whole numbers of bits.
The four pairs have probabilities 0.64 for 00, 0.16 for 01 and 10, and 0.04 for 11. 0.04 and 0.16 are merged into 0.2, 0.2 and 0.16 into 0.36, and finally that with 0.64, so the code lengths are 1, 2, 3 and 3 bits and the average per pair is 0.64 × 1 + 0.16 × 2 + 0.16 × 3 + 0.04 × 3 = 1.56 bits. Per original symbol this is 1.56 ÷ 2 = 0.78 bits. Coding one symbol at a time can only give 0 and 1 one bit each, but coding symbols together brings the length closer to the entropy of about 0.72 bits.
FAQ
Do equal probabilities change the answer?
The order of merging can change the 0/1 patterns and even individual code lengths, but every valid choice gives the same minimum average code length. Exams therefore usually ask for the average length or for code lengths under stated conditions.
How much shorter is it than a fixed-length code?
With n symbols, a fixed-length code needs ⌈log2 n⌉ bits. The more skewed the probabilities, the shorter the Huffman code; with no skew at all, as in "Four equally likely symbols", it is the same 2 bits as a fixed-length code.
What do you need to decode?
The same code table (or tree) as the sender. If a table is built for each piece of data, it is either sent along or rebuilt from the symbol counts. Deflate sends only the code lengths and rebuilds the table by a fixed rule.