Welcome to our community

Be a part of something great, join today!

Total weight of Huffman Code

mathmari

Well-known member
MHB Site Helper
Apr 14, 2013
4,008
Hey!! 😊

We are given the following letters with the respective frequencies:
\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{matrix}\end{equation*}

For that I have applied the Huffman code and I got the following tree:

Huffman.JPG


Now it is asked for the total weight of the code. How do we calculate that? :unsure:
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
8,687
We are given the following letters with the respective frequencies:
\begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{matrix}\end{equation*}

For that I have applied the Huffman code and I got the following tree:

Now it is asked for the total weight of the code. How do we calculate that?
Hey mathmari !!

The total weight would be the weighted path length from the root.
The objective of the algorithm is to minimize the total weight, implying that compression is optimal. 🧐

Put differently, it is the length of the resulting code for each symbol multiplied by its frequency and then summed together.
So the contribution of $a$ is $4\times 2=8$, since $a$ is encoded by $0000$, which has length $4$ and it occurs $2$ times. 🤔

I think your tree is not optimal though. I found a different tree with a slightly lower total weight. (Sweating)