Canonical Huffman Trees in ATRAC3+
Canonical huffman trees are uniquely defined just by the number of bits for each symbol. The codes of one bit length are ordered alphabetically by their corresponding symbols. In ATRAC3+, they are allocated with the shortest symbols at low codes (the alphabetically first shortest symbol consists only of zeroes) and the longest symbols at high codes (the alphabetically last longest symbol consists only of ones).
As an example:
- A 3 bits
- B 2 bits
- C 3 bits
- D 1 bit
Allocation of codes starts with the shortest code, so D gets 0, all later codes need to start with 1. Then codes of length 2 are allocated, this is only B, so B gets the first 2-bit code starting with 1, namely 10. All later codes need to start with 11. Last are the two 3-bit codes for A and C. As A lexicographically preceedes C, A gets the code 110 and C gets 111.