Huffman Coding
DSA · Classic Algorithms
Theory
Huffman coding is a greedy algorithm for lossless data compression. Instead of giving every character the same number of bits (8 in ASCII), it gives frequent characters short codes and rare characters long codes. It counts how often each character appears, puts each character in a min-heap by frequency, and repeatedly removes the two least frequent nodes, merging them into a new node whose frequency is their sum. When one node remains, it is the root of a binary tree: walking left adds 0 and walking right adds 1, and each leaf's path is its code. Because no code is a prefix of another, the encoded bits can be decoded without separators. Huffman coding is used inside ZIP (DEFLATE), JPEG and MP3.
Why we use it
It produces the optimal prefix code for given symbol frequencies, reducing file sizes without losing information. It is also a standard example of a greedy algorithm combined with a heap.
When to use it
Use it when symbol frequencies are uneven, such as text or image data. If all symbols are equally likely, fixed-length codes are just as good.
How it works
- Count character frequencies
- Push each character into a min-heap
- Heap has more than 1 node? Yes: Pop two smallest, merge, push sum. No: Root of tree is ready.
- Left edge = 0, right edge = 1
- Leaf paths are the codes
Syntax
heap of (freq, node)
while len(heap) > 1:
a, b = two smallest
push (a.freq + b.freq, Node(a, b))
Time O(k log k) for k distinct symbolsExample
import heapq
from collections import Counter
text = "techtown teaches data"
freq = Counter(text)
heap = [[f, i, ch] for i, (ch, f) in enumerate(freq.items())]
heapq.heapify(heap)
counter = len(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
heapq.heappush(heap, [lo[0] + hi[0], counter, (lo, hi)])
counter += 1
codes = {}
def assign(node, code=""):
item = node[2]
if isinstance(item, str):
codes[item] = code or "0"
else:
assign(item[0], code + "0")
assign(item[1], code + "1")
assign(heap[0])
for ch, code in sorted(codes.items(), key=lambda kv: (len(kv[1]), kv[0])):
print(repr(ch), freq[ch], code)
encoded = "".join(codes[c] for c in text)
print("Original bits:", len(text) * 8, "| Huffman bits:", len(encoded))
decode = {v: k for k, v in codes.items()}
out, buf = [], ""
for bit in encoded:
buf += bit
if buf in decode:
out.append(decode[buf]); buf = ""
print("Decoded:", "".join(out))Key points
- Frequent symbols get shorter codes
- Greedy merging of the two smallest frequencies with a min-heap
- Prefix-free codes decode without separators
- Used in ZIP, JPEG and MP3