0
$\begingroup$

Consider the weights: 10, 12, 13, 16, 17, 17.

(a) Construct an optimal coding scheme for the weights given by using a tree.

(b) What is the total weight of the tree you found in part (a)?

  • 2
    This is an easy question about [Huffman coding](http://en.wikipedia.org/wiki/Huffman_coding); can you at least take the first step?2012-12-06
  • 1
    would you just have all of the numbers at the bottom of the tree and keep adding up the two smallest ones so you would have 10+12, 13+16, 17+17, and then 22+29, and then lastly 34+51 to get a total weight of 85?2012-12-07
  • 0
    That’s the right start. Now just organize that into tree form and use the tree to specify the codes for the six weights, and you’re done.2012-12-07
  • 0
    i dont know how to specify the codes for the six weights2012-12-07
  • 0
    On this site, it's considered good manners to click on the checkmark below an answer you find acceptable, since that gives a reputation boost to both you and the answerer. @Brian and I have provided good answers; why not be generous and check his?2012-12-11
  • 0
    @Rick: You just reminded me that I’d not upvoted your answer; fixed.2012-12-11

2 Answers 2

1

I presume that you can construct the tree, given the hints you've been offered. Once that's done, at each non-leaf node, arbitrarily assign a $0$ and a $1$ to each branch, Then the code for each leaf node is just the sequence of these branch values, reading from the top to the bottom. For example, if the leaf nodes contain 10, 12, 13, 16, 17, 17, reading from left to right, then assigning $0$ to each left branch and $1$ to each right branch gives you the codes $$ \begin{align} 10 &: 000 \\ 12 &: 001 \\ 13 &: 010 \\ 16 &: 011 \\ 17 &: 10 \\ 17 &: 11 \\ \end{align} $$ along with 31 other equally good codes.

1

This is the tree that Rick Decker used in his answer. Each node of the tree that isn’t a leaf has two edges leading down from it; the one to the left is labelled with a red $0$ and the one to the right with a red $1$. Think of the tree as a road map; a string of red numbers can be used to describe how to get from the root ($85$) to one of the leaves. To get from the root to the leaf $13$, for instance, you must go left ($0$), then right ($1$), then left ($0$) again, so the route is $010$, and that’s the code assigned to the weight $13$ leaf.

Notice that the most heavily weighted leaves $-$ the two $17$’s $-$ are closest to the root and so have the shortest codes; this is what makes the Huffman encoding efficient.

enter image description here