Huffman Code Lengths

Build a Huffman code and return the length in bits of the codeword for each symbol.

Entropy is a lower bound on the average number of bits per symbol that any lossless code can reach. Huffman's greedy algorithm builds a prefix code whose average length is the best possible for codes made of whole bits, and it is always within 1 bit of the entropy.

The algorithm:

1. Make one node per symbol, with its frequency as the weight.
2. Take the two nodes with the smallest weights and merge them into a new node whose weight is their sum.
3. Repeat until one node is left.

The codeword length of a symbol is the number of merges above it, which is its depth in the final tree.

Function signature

def huffman_lengths(freqs):

Example

Input

huffman_lengths([0.5, 0.25, 0.125, 0.125])

Output

[1, 2, 3, 3]

Reasoning

First the two 0.125 symbols merge into a node of weight 0.25. That node merges with the 0.25 symbol into a node of weight 0.5, which then merges with the 0.5 symbol. The last two symbols sit three merges deep, the second two deep, and the first one deep. The average length is 1.75 bits, which here equals the entropy exactly.

Constraints and notes

• freqs is a list of positive numbers. They do not have to sum to 1.
• When weights tie, any choice gives an optimal code, and the tests accept any optimal answer. They check that the code is complete (the sum of 2^-length is 1) and that the average length is the optimum.
• A single symbol gets a length of 1.
• Return a list of ints in the same order as freqs.