wire / wire-format / huffman-coding
Optimal prefix code: assign shorter codes to more frequent symbols. Algorithm: build a binary tree by repeatedly merging the two least frequent nodes. The code for each symbol is the path from root to leaf (0=left, 1=right). Huffman codes are optimal (minimum expected length) among prefix codes. Average length ≤ H(X) + 1.
aka: Huffman coding
spec: Huffman (1952)
Optimal prefix code: assign shorter codes to more frequent symbols. Algorithm: build a binary tree by repeatedly merging the two least frequent nodes. The code for each symbol is the path from root to leaf (0=left, 1=right). Huffman codes are optimal (minimum expected length) among prefix codes. Average length ≤ H(X) + 1.
| field | size | meaning |
|---|---|---|
| Build tree | O(n log n) | Priority queue of symbols by frequency. Repeatedly extract two min, merge, insert back. Continue until one node. |
| Code assignment | O(n) | Traverse tree from root. Left edge = 0, right edge = 1. Code = path bits. |
| Expected length | bits/symbol | L = Σ p(x) * len(code(x)). H(X) ≤ L < H(X) + 1. |
| Canonical Huffman | variant | Sort codes by length, then assign lexicographically. Enables efficient decoding with a lookup table. |
| Adaptive Huffman | variant | Update tree dynamically as symbols are processed. No need to transmit the tree. |
example:
00 00
Huffman coding (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/huffman-coding
or /wire-format/huffman-coding.json