Course contentsShow
← Computer Science
Lesson 890 of 2,87221. Greedy AlgorithmsFree lesson

Huffman Coding for Data Compression

Build optimal prefix-free binary codes by repeatedly merging two least-frequent symbols into a tree.

Huffman Coding for Data Compression

You'll learn how to build optimal prefix-free binary codes by repeatedly merging the least-frequent symbols into a tree.

The Core Idea

Huffman Coding is a greedy algorithm that compresses data by assigning shorter binary codes to more frequent characters and longer codes to rare ones. Instead of using the same number of bits for every character (like ASCII's 8 bits), Huffman coding saves space by being smart about frequency.

The algorithm works by building a binary tree from the bottom up:

  1. Count how often each character appears
  2. Create a leaf node for each character with its frequency
  3. Greedy step: repeatedly take the two nodes with the smallest frequencies and merge them into a parent node (frequency = sum of children)
  4. Repeat until one tree remains
  5. Read codes by tracing paths from root to leaves (left = 0, right = 1)

Why It's Optimal

The greedy choice—always merging the two least-frequent nodes—ensures rare characters end up deeper in the tree (longer codes) while common ones stay near the root (shorter codes). This minimizes the total encoding length.

Analogy: Imagine organizing your closet by putting frequently-worn clothes at eye level and rarely-used items on high shelves. Huffman does the same with bits!

Prefix-Free Property

No code is a prefix of another (e.g., if 'a' = 01, no other character starts with 01). This lets you decode unambiguously without separators.

Key Takeaway: Huffman Coding uses a greedy bottom-up tree-building approach, always merging the two least-frequent elements, to create optimal variable-length codes that compress data efficiently.