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).
• The first code of a length is the smallest binary value with that length.
• Codes are stored in the lowest Len bits.

Example

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

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