0
$\begingroup$

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:

enter image description here

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

Do we maybe use the formula $\displaystyle\sum_{c\in C}f(c)d(c)$ ?

Then we have $$2\cdot 4+3\cdot 4+5\cdot 3+6\cdot 3+7\cdot 3+4\cdot 4+4\cdot 4+8\cdot 3+10\cdot 3+11\cdot 3=193$$ Is that correct?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ I have never heard of the "total weight" of a prefix code. Ask your professor. $\endgroup$
    – Yuval Filmus
    Commented Jun 5, 2020 at 19:30
  • 1
    $\begingroup$ Usually we are interested in the average length of a codeword, and sometimes also in the maximum length of a codeword. $\endgroup$
    – Yuval Filmus
    Commented Jun 5, 2020 at 19:31
  • $\begingroup$ Ahh ok! I will ask. The formula I wrote above what does it represent? @YuvalFilmus $\endgroup$
    – Mary Star
    Commented Jun 5, 2020 at 19:47
  • 1
    $\begingroup$ Formulas are not so important. The two parameters I mentioned are interesting on their own. The formula defining them is less important than their meaning. $\endgroup$
    – Yuval Filmus
    Commented Jun 5, 2020 at 19:49

1 Answer 1

Reset to default
0
$\begingroup$

Multiply the frequencies of each letter * the code length of that letter, then add the total of every single letter. You have that done. Now, you divide the total sum by the number of letters used in the string, also the sum of all the frequencies of the letter. So divide 193 / (2+4+7+6+4+5+8+10+3+11).

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That will give you the average length of code words as they are used. Which is very useful. Arguable the most important thing about a Huffman code after correctness. Whether it has anything to do with “total weight of the code”, heaven knows. $\endgroup$
    – gnasher729
    Commented Apr 15 at 18:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.