How to find weights given a Huffman tree

user_2428487 0
Viewed 143

Huffman's algorithm derives a tree given the weights of the symbols. I want the reverse: given a tree, figure out a set of symbol weights that would generate that tree a tree with the same bit lengths for each symbol.

I'm aware that there are multiple sets of weights that generate the same tree, so I imagine that the weights can be given as powers of two, and the longest code could be assigned weight 1.

(Not relevant to the question, but the purpose is to fine-tune the fixed tree used internally by an LZ77-type compression algorithm to code the offsets and lengths, checking whether the current bitlengths are reasonable or adjusting them if not).

huffman-code compression
1 Answers

You imagine correctly. However the powers of two will result in many ties when executing the Huffman algorithm. The tree you get back may have a different topology than the tree you started with, depending on how the ties are decided. But the bit lengths will all be the same.

Here is an example:

I used these frequencies for the alphabet:

817     A
145     B
248     C
431     D
1232    E
209     F
182     G
668     H
689     I
10      J
80      K
397     L
277     M
662     N
781     O
156     P
9       Q
572     R
628     S
905     T
304     U
102     V
264     W
15      X
211     Y
5       Z

That gave me this tree:

original Huffman tree

Then I assigned powers-of-two frequencies to the symbols per their depths in the tree:

64      A
16      B
32      C
32      D
128     E
16      F
16      G
64      H
64      I
2       J
8       K
32      L
32      M
64      N
64      O
16      P
1       Q
64      R
64      S
128     T
32      U
16      V
32      W
4       X
32      Y
1       Z

Applying Huffman to that, I get a very different tree, but one where all of the symbols have the same depth as before:

new boring, imbalanced Huffman tree

I'm pretty sure that there's a way to assign frequencies working up from the bottom, making the next thing to add just big enough to assure the right choice. That will also result in lower weights overall than the powers of two, coming closer to a Fibonacci sequence. This is an interesting problem, so now I am tempted to play with it.

user_11806200
Related