Reducing Variance in Huffman Trees

Method to reduce variance in Huffman Trees.

#Consider a Huffman tree to be constructed for the symbols : a_1,a_2,....,a_n.

Let their probabilities be p(1),p(2),....,p(n) and the length of their codes be

l(1),l(2),...,l(n).

Now, the average length of the codes is the weighted path length of the Huffman tree

constructed,which is :avg= p(1)l(1)+p(2)l(2)+......+p(n)l(n).

#Now,I shall define variance as:

V= p(1)[l(1)-avg]^2 + p(2)[l(2)-avg]^2+.....+p(n)[l(n)-avg]^2.

Variance thus gives an idea of how much the encoder has to keep varying the number of bits generated.If the encoder were to write the codes into a file then variance makes no difference. However,if the encoder were to transmit the codes,then less variance is prefered. In case of transmission of bits, the rate has to remain constant.However,if the rate keeps on changing then a buffer has to be maintained by the encoder. Larger the variance,less constant is the rate at which the bits enter the buffer.So,the buffer has to be large.

Now,I shall describe a method to reduce variance:

    When there are more than two smallest probability nodes,select the ones that are lowest and highest in the tree and combine them.

This will combine symbols of low probability and ones with high probability and reduce the total variance.

*For example, consider the set of probabilities: 1/20,1/20,2/20,2/20,4/20,10/20.

Consider only the numerators for ease: 1,1,2,2,4,10.

Now, we combine 1 and 1 to give "2".

So we have: "2" ,2,2,4,10.

Here, "2" stands for the 2 created by merging children nodes.

Select "2" and 4 and merge them. Select the other two 2s and merge them.So we have "4" and "6".

Then combine "4" and "6" to arrive at "10".

Then comnine "10" and 10 to give "20".

The average path length=2.1 bits/symbol.

The variance comes out to be: 1.290.

Now, we can try another way of building the same tree.

We can merge 1,1 to get "2".

"2" and 2 give "4".

2 and "4" give "6".

Then 4 and "6" give "10".

Finally, "10" and 10 give "20".

The average path length=2.1 bits/symbol.

The variance comes out to be: 1.890, which is more than the first case.

Hence, the idea lies in choosing the better tree among the possible ones in terms of variance.

 

Share this article!

Follow us!

Find more helpful articles: