0
$\begingroup$

By giving an Huffman coding tree and the total frequency of the characters. how can I find the most unoptimal frequencies for each character such that the size of the code will require the most possible of bits?

$\endgroup$
2
  • $\begingroup$ Do you mean "the most off from the entropy limit" (eg worst compared to ideal compression) or "the largest result" or something else? $\endgroup$
    – user555045
    Commented Aug 13, 2020 at 22:05
  • $\begingroup$ Shouldn't sum of frequencies equal $1$? $\endgroup$
    – greybeard
    Commented Aug 14, 2020 at 3:00

2 Answers 2

1
$\begingroup$

There are several definitions of "unoptimal".

As vonbrand noted, Huffman coding falls back to binary encoding if all frequencies are equal.

For longest code length, this happens if the frequencies are Fibonacci numbers.

For worst compression rate compared to the entropy, this happens with an alphabet of two symbols where $p_0 = \varepsilon$ and $p_1 = 1-\varepsilon$. The Shannon entropy approaches $0$ bits per symbol as $\varepsilon \rightarrow 0$, but any Huffman code requires $1$ bit per symbol.

For size of the Huffman tree, there is no "worst case", because the size is the same no matter what the frequencies are. For an alphabet of $n$ symbols, the Huffman tree must have $n$ leaves and $n-1$ branches.

$\endgroup$
1
  • 1
    $\begingroup$ Then, there is uniformly distributed random source and worst case compared to arithmetic encoding - I think that happens with three symbols. $\endgroup$
    – greybeard
    Commented Aug 14, 2020 at 2:59
0
$\begingroup$

All frequencies the same. Thus there is no space for compression.

$\endgroup$
5
  • $\begingroup$ But if the shape of the tree dont enable that? $\endgroup$
    – OriFrid
    Commented Aug 13, 2020 at 21:34
  • $\begingroup$ @daniTo, Huffman coding creates the tree from the frequencies, no "impossible" tree can come up. $\endgroup$
    – vonbrand
    Commented Aug 13, 2020 at 21:36
  • $\begingroup$ I know the algorithm. But I may have a question such as drawing of a tree and I asked to decide true or false: if the total frequency of the characters is 1000 than the maximum size is 2300 bits. Than I need to find counter example or prove it. $\endgroup$
    – OriFrid
    Commented Aug 13, 2020 at 21:43
  • $\begingroup$ In that case Huffman code is optimal. $\endgroup$
    – gnasher729
    Commented Aug 14, 2020 at 8:06
  • $\begingroup$ @gnasher729, it is always optimal. The question asks when it uses most bits. $\endgroup$
    – vonbrand
    Commented Aug 18, 2020 at 13:15

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.