Skip to main content

How Huffman code reduces file size

Short answer

Huffman coding assigns short codes to frequent symbols and long codes to rare ones, reducing total bits. For 100 characters with frequencies A45, B20, C15, D10, E10, fixed 3-bit coding needs 300 bits, while Huffman needs 210 bits, saving 30%.

Explain with example how Huffman code reduces the file size.

Huffman coding reduces file size by replacing fixed-length codes (for example 8-bit ASCII or 3-bit codes) with variable-length codes: common symbols get very short codes and rare symbols get longer ones. Since common symbols occur most, the total number of bits falls.

Example

A file has 100 characters made of A, B, C, D, E with frequencies A = 45, B = 20, C = 15, D = 10, E = 10.

Fixed-length coding: 5 symbols need 3 bits each. Total = 100 x 3 = 300 bits.

Huffman tree:

  1. D (10) + E (10) = DE (20)
  2. C (15) + B (20) = CB (35)
  3. DE (20) + CB (35) = DECB (55)
  4. A (45) + DECB (55) = root (100)

Codes: A = 0, D = 100, E = 101, C = 110, B = 111.

SymbolFrequencyCodeLengthBits used
A450145
B20111360
C15110345
D10100330
E10101330
Total100210

Average length = 210/100 = 2.1 bits per symbol.

Saving = (300 - 210)/300 = 90/300 = 30%.

Against 8-bit ASCII (800 bits), the Huffman file is 210 bits, a reduction of about 73.8%.

The decoder needs the code table (or frequencies), which is stored as a small header. Because the codes are prefix-free, the bit stream is decoded without separators. The more skewed the symbol frequencies, the greater the saving.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Multimedia System chapter 5 questions →