3
$\begingroup$

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the frequencies of the characters present in the input text, I believe the answer is also going to be related to that.

This is what I got from wiki.

The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^(−1) = 0.5, making the upper limit of inefficiency unbounded.

So if a character appears more in our input text, would it ensure good or bad compression? According to wiki, if the probability of symbol exceeds 0.5 (meaning that if a character appears more in our input text), it would be produce bad compression. But from what I understand, in Huffman coding, the more a character appears, the more better it is for us to get compression right?

Well anyway I just want to know in which type of files or text data, our Huffman coding would get bad compression. Maybe I am overthinking, but a little help would be great.

Thanks.

P.S: I don't think this question is subjective, I know that there is a specific answer to it. All I want is a worst case, I don't presume it's subjective?

$\endgroup$
3
$\begingroup$

According to NIST:

The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For this and other relations see Alex Vinokur's note on Fibonacci numbers, Lucas numbers and Huffman codes.

According to Alex Vinokur a sample Huffman encoding of a sample Fibonacci distribution was 2.3846 times longer than the original. See example 3.1.1.
As I understand it the inefficiency gets worse as the alphabet increases which is why wikipedia talks about unbounded inefficiency.

Note that is not the fact that a single character is prevalent that's the issue it is the distribution of the frequencies that's the problem.

A more useful description comes from your wikipedia quote:

The worst case for Huffman coding can happen when the probability of a symbol exceeds $2^{-1} = 0.5$, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding;

This happens when a few letters in the alphabet are much more prevalent then others; a skewed distribution as described in the NIST quote above.
This is common in uncompressed bitmap files.

The reason for this is that:

The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.

This is why run length coding or other forms of compression are usually applied prior to Huffman coding.
It eliminates many of the worst case scenario's for Huffman coding.
If it turns out the run length encoding is suboptimal it can simple be skipped.

Zip's deflate algorithm uses de-duplication + run length encoding followed by huffman encoding.

Huffman codes and binary trees
A Huffman code is closely related to a binary tree, however unlike a binary tree a Huffman code only stores its information in the leaf nodes.
The optimal input for Huffman compression is one where the output tree is fully balanced. I.e. where all letters of the Huffman alphabet are equally likely, but where more bits are used in the encoding than needed.
E.g. a text file where 8 bits per character are used even though only 64 different letters are in use. The distribution of letters in a typical language is much flatter than a Fibonacci sequence and thus well suited to Huffman.

Note that it is not necessary the case that all input letters for Huffman should be same size, they can very well be different sizes.
Usually this is not considered in order to simplify the implementation.

Strategies for avoid worst case behavior
Do a frequency analysis on your input data prior to Huffman encoding.

$\endgroup$

Your Answer

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