# When is Huffman code the most unoptimal?

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?

• Do you mean "the most off from the entropy limit" (eg worst compared to ideal compression) or "the largest result" or something else? Aug 13 '20 at 22:05
• Shouldn't sum of frequencies equal $1$? Aug 14 '20 at 3:00

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.

• Then, there is uniformly distributed random source and worst case compared to arithmetic encoding - I think that happens with three symbols. Aug 14 '20 at 2:59

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

• But if the shape of the tree dont enable that? Aug 13 '20 at 21:34
• @daniTo, Huffman coding creates the tree from the frequencies, no "impossible" tree can come up. Aug 13 '20 at 21:36
• 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. Aug 13 '20 at 21:43
• In that case Huffman code is optimal. Aug 14 '20 at 8:06
• @gnasher729, it is always optimal. The question asks when it uses most bits. Aug 18 '20 at 13:15