World's most popular travel blog for travel bloggers.

# exercise on Huffman encode

, ,
Problem Detail:

I have these 4 symbols with their probabilities:

`` x   P(x)  --------  1   0.3  2   0.3  3   0.2  4   0.2 ``

I built the Huffman tree in this way: and I obtainded:

`` x   P(x)   C(x)  ----------------  1   0.3     0  2   0.3     10  3   0.2     110  4   0.2     111 ``

it's correct? Because according to the solution the results should be:

`` x   P(x)   C(x)  ----------------  1   0.3     00  2   0.3     01  3   0.2     10  4   0.2     11 ``

Why? Yet I followed the steps shown here.

###### Answered By : Denis Pankratov

A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of \$2.1\$, which is greater than using a code of fixed length \$2\$, so it can't be correct.

If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 and 4 you get one supernode of priority 0.4. Now your queue would have three elements of priorities \$0.3, 0.3,\$ and \$0.4\$. Thus, you would next merge elements corresponding to priorities \$0.3\$ and \$0.3\$ (the algorithm works by merging two nodes with lowest priorities), which happen to be nodes 1 and 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/57960

3200 people like this