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$
    – harold
    Aug 13 '20 at 22:05
  • $\begingroup$ Shouldn't sum of frequencies equal $1$? $\endgroup$
    – greybeard
    Aug 14 '20 at 3:00
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
    Aug 14 '20 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
    Aug 13 '20 at 21:34
  • $\begingroup$ @daniTo, Huffman coding creates the tree from the frequencies, no "impossible" tree can come up. $\endgroup$
    – vonbrand
    Aug 13 '20 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
    Aug 13 '20 at 21:43
  • $\begingroup$ In that case Huffman code is optimal. $\endgroup$
    – gnasher729
    Aug 14 '20 at 8:06
  • $\begingroup$ @gnasher729, it is always optimal. The question asks when it uses most bits. $\endgroup$
    – vonbrand
    Aug 18 '20 at 13:15

Your Answer

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

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