Huffman Coding a Small Alphabet

Build an optimal prefix code for four symbols with known frequencies and compute the average code length.

Problem

Huffman coding builds an optimal prefix-free binary code from symbol frequencies. Frequent symbols get short codes, rare ones get long codes, and no code is a prefix of another so the stream decodes unambiguously. It achieves the minimum average length among all prefix codes.

Construction

Repeatedly merge the two lowest-frequency nodes into a parent whose frequency is their sum. The tree that results assigns each symbol a code by the path from root (left=0, right=1). We use symbols A,B,C,D with frequencies 0.5, 0.2, 0.2, 0.1.

import heapq
freq={'A':0.5,'B':0.2,'C':0.2,'D':0.1}
pq=[[f,[s,'']] for s,f in freq.items()]; heapq.heapify(pq)
while len(pq)>1:
    lo=heapq.heappop(pq); hi=heapq.heappop(pq)
    for pair in lo[1:]: pair[1]='0'+pair[1]
    for pair in hi[1:]: pair[1]='1'+pair[1]
    heapq.heappush(pq,[lo[0]+hi[0]]+lo[1:]+hi[1:])
codes={s:c for s,c in pq[0][1:]}
avg=sum(freq[s]*len(c) for s,c in codes.items())
print(codes)
print('avg length',round(avg,3))

Result

The frequent symbol A gets a 1-bit code while the rarest D gets a 3-bit code, giving an average length near 1.8 bits per symbol. Compare this to the Shannon entropy of the source (about 1.76 bits), which Huffman approaches but cannot beat, and to a fixed 2-bit code, which it beats. The prefix property lets a decoder read bit by bit and emit a symbol the moment a leaf is reached.

• Huffman is provably optimal among symbol-by-symbol prefix codes for a known distribution.
• It cannot beat the source entropy; arithmetic and range coding close the remaining fractional-bit gap.
• Prefix-code ideas support lossless compression of Kronos diagnostic and log data streams.