Is there a way to restore frequency array from Huffman tree?

312 Views Asked by At

Most people, when they implement study Huffman algorithm, prefer to store frequency array, not Huffman tree. But sometimes I would like to store Huffman tree. For example, It allows immediately decode data.

huffman tree

Unfortunately, I do not know, how to restore frequency array from Huffman tree. Furthermore, I do not know, it is possible or not.

2

There are 2 best solutions below

0
On BEST ANSWER

It is not clear why you want to restore the frequency array. As you said, the tree is all you need to decode. (You don't even need to send the tree — you can just send the number of bits for each symbol, and generate a canonical Huffman code from that.)

You do not have enough information to recover the original frequency array. However you can easily construct a frequency array that would reproduce that tree. Make the longest codes frequency 1, codes with one bit less frequency 2, two bits less frequency 4, and so on.

0
On

IMO when you have the frequency you can simply reconstruct the tree with the same function, for example greater or less.