Canonical Huffman Codes

Given code lengths, build canonical Huffman codes.

Types

type Code struct {
    Bits uint32 // code bits stored in the low bits
    Len  uint8
}

func CanonicalCodes(lengths []int) []Code

Behavior

• lengths[i] is the code length for symbol i.
• Length 0 means the symbol is unused (Len=0, Bits=0).
• Codes are assigned in order of (length, symbol id).
• Start the first used symbol at code 0. After assigning a code, increment it; before the next assignment, left-shift by the increase in length. Shorter codes reserve prefixes, so a later length group does not restart at zero.
• Codes are stored in the lowest Len bits.

Inputs contain lengths in 0..32 satisfying Kraft's inequality. Incomplete prefix trees are allowed; invalid tables are outside this function's contract.

Example

Lengths: [2,3,3,3] Canonical codes:

• 0 -> 00
• 1 -> 010
• 2 -> 011
• 3 -> 100