Huffman Intuition

The Idea

Frequent symbols deserve short codes, rare ones can afford long codes. Huffman builds that arrangement from the bottom up.

Put every symbol's count in a min-heap. Pull the two smallest, merge them under a new parent whose count is their sum, and push it back. Repeat until one node remains. Each merge pushes everything below it one level deeper, which is exactly one more bit per character — so the sum of the merges is the size of the encoded file.

Real-World Example

The letter frequencies of a chat log. Sending e as one bit and q as nine beats a fixed-width code every time, which is why this idea sits inside ZIP, JPEG and HTTP compression.

The Code

import heapq
freqs = [2, 3, 4, 7]             # counts for d, c, b, a
heapq.heapify(freqs)
bits = 0
while len(freqs) > 1:
    a = heapq.heappop(freqs)     # the two rarest symbols left
    b = heapq.heappop(freqs)
    bits += a + b                # merging adds one bit to everything below
    heapq.heappush(freqs, a + b)
print(bits)                      # fixed 2-bit codes would cost 32