1
$\begingroup$

I read the following post. Now i encountered this question, what is codeword length of a character with frequency more than $\frac{2}{5}$ huffman coding? I think it can 2bit or 1bit, but i can't prove it. Any help for proving that appreciated.

$\endgroup$
1
$\begingroup$

Consider the classical algorithm that constructs the Huffman code and focus on the moment in which the singleton vertex $v$ corresponding to the character with frequency larger than $\frac{2}{5}$ was first merged with another tree $T$. At this point in time, either the frequency of $T$ was at least $\frac{2}{5}$ (which means that all trees had frequency at least $\frac{2}{5}$), or $T$ was the only tree with frequency smaller than $\frac{2}{5}$ (otherwise $T$ would have been merged with some other tree).

This means that there can be at most one additional tree in the forest other than $v$ and $T$.

The maximum depth of $v$ that can be obtained by combining (up to) $3$ trees is $2$.

Clearly both $1$ and $2$ are possible lengths of a codeword, as shown by symbol $a$ in the following two examples (frequencies are in blue).

examples

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy