English
Menu

What is Huffman coding?

A method of building, from the probabilities of the symbols, a prefix code whose average code length is as small as possible. A tree is built by repeatedly merging the two symbols (or nodes) with the smallest probabilities into one, and 0 and 1 are assigned at each branch to form the codewords. The more frequent a symbol, the shorter its codeword. It is optimal among prefix codes that code one symbol at a time, and its average code length is at least the entropy and less than the entropy + 1 bit. It is used in combination with other methods in Deflate (ZIP, gzip), JPEG and elsewhere. Huffman published it in 1952.

Japanese name: ハフマン符号

Huffman coding appears in 5 practice questions across 1 topic, including Information Theory and Coding Basics.

Field: Information Theory and Coding Basics

How to build one

For symbols with probabilities 1/2, 1/4, 1/8 and 1/8, first the two 1/8s are merged into 1/4, then that and the 1/4 into 1/2, and finally that and the remaining 1/2. Labeling the branches from the root to each symbol with 0 and 1 gives the codewords 0, 10, 110 and 111, with an average code length of 1.75 bits, equal to the entropy. When every probability is the reciprocal of a power of 2, the average code length matches the entropy like this.

The codewords are not unique

The codewords change depending on how 0 and 1 are assigned and on which of two equal probabilities is merged first. For example, with probabilities 0.4, 0.2, 0.2, 0.1 and 0.1 the code lengths can be 1, 2, 3, 4, 4 or 1, 3, 3, 3, 3 or 2, 2, 2, 3, 3, but the average code length is 2.2 bits in every case. This is why examinations tend to ask for the average code length rather than the codewords themselves.

Limits and improvements

Code lengths are limited to whole numbers of bits, so for a source with a symbol whose probability is close to 1, the gap from the entropy becomes large. Coding binary symbols one at a time needs 1 bit per symbol however skewed they are. Coding symbols together, or using a method not bound to whole bits such as arithmetic coding, brings the length closer to the entropy.

Try it: questions about Huffman coding

A source emits the symbols A, B, C and D independently with probabilities 0.4, 0.3, 0.2 and 0.1, and it is encoded with a Huffman code. Which of the following is the average code length per symbol?

  1. AAbout 1.85 bits
  2. B1.9 bits
  3. C2 bits
Show answer and explanation

Answer: B. 1.9 bits

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.

A source emits the symbols A to E independently with probabilities 0.3, 0.25, 0.2, 0.15 and 0.1, and it is encoded with a Huffman code. The codewords may change depending on which of two equal probabilities is chosen first, but the average code length does not. Which of the following is the average code length per symbol?

  1. A2.25 bits
  2. B2.4 bits
  3. C3 bits
Show answer and explanation

Answer: A. 2.25 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.

FAQ

What is needed to restore data compressed with a Huffman code?

Restoring the data requires knowing which codeword was assigned to which symbol (a code table, or the code length of each symbol). Compressed data therefore carry the code table with them or use a table agreed in advance. Deflate sends only the code lengths, and the receiver rebuilds the codewords by the same rule (canonical Huffman codes).

Can a Huffman code make any data smaller?

No. If the symbol probabilities are not skewed, the data hardly shrink. For example, in data where all 256 byte values are equally likely, every codeword is 8 bits long, and the code table makes the result slightly larger.

Huffman coding in the explanations

Questions that mention Huffman coding (5)

  1. A source emits the symbols A, B, C and D independently with probabilities 0.4, 0.3, 0.2 and 0.1, and it is encoded with a Huffman code. Which of the following is the average code length per symbol?
  2. A source emits the symbols A to E independently with probabilities 0.3, 0.25, 0.2, 0.15 and 0.1, and it is encoded with a Huffman code. The codewords may change depending on which of two equal probabilities is chosen first, but the average code length does not. Which of the following is the average code length per symbol?
  3. A source emits the symbols A, B and C independently with probabilities 0.6, 0.3 and 0.1, and its entropy is about 1.30 bits. Which of the following is closest to the efficiency (entropy ÷ average code length) when this source is encoded with a Huffman code?
  4. A binary source emits 0 with probability 0.8 and 1 with probability 0.2, independently. Symbols are taken two at a time, each of the four pairs 00, 01, 10 and 11 is treated as one symbol, and they are encoded with a Huffman code. Which of the following is the average code length per original symbol?
  5. Which of the following correctly describes the idea of the LZ77 method used in ZIP, gzip and similar tools?

Books on Information Theory and Coding Basics Ad

As an Amazon Associate I earn from qualifying purchases.

Related terms

Average code length Information entropy Lossless compression Binary symmetric channel Forward error correction (FEC) Hamming code Hamming distance Kraft inequality Lossy compression Mutual information

Back to the glossary