wire / wire-format / huffman-coding

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.

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: Huffman coding

wire format

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.

fieldsizemeaning
Build treeO(n log n)Priority queue of symbols by frequency. Repeatedly extract two min, merge, insert back. Continue until one node.
Code assignmentO(n)Traverse tree from root. Left edge = 0, right edge = 1. Code = path bits.
Expected lengthbits/symbolL = Σ p(x) * len(code(x)). H(X) ≤ L < H(X) + 1.
Canonical HuffmanvariantSort codes by length, then assign lexicographically. Enables efficient decoding with a lookup table.
Adaptive HuffmanvariantUpdate tree dynamically as symbols are processed. No need to transmit the tree.

example:

00 00

Huffman coding (placeholder)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/huffman-coding or /wire-format/huffman-coding.json