Cheap and Secure Web Hosting Provider : See Now

exercise on Huffman encode

, , No Comments
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:

enter image description here

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.

Asked By : four
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

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback