2
$\begingroup$

I am interested in the following question:

Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords.

I'm thinking of a worst case when the full binary tree (generated by Huffman's algorithm) has height $n-2$, but I still have to take the letter frequency into account, and I am stuck.

(Also I observed that the letter frequency shrinks by a factor of two when traversing down the tree.)

$\endgroup$
6
$\begingroup$

Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution).

Let us notice now that there is a code in which each codeword has length $\lceil \log n \rceil$, and in particular the average codeword length is $\lceil \log n \rceil$ (with respect to any distribution). Hence Huffman's algorithm produces a code in which the average codeword length (with respect to the input distribution) is at most $\lceil \log n \rceil$.

Here are two comments. First, we cannot replace $\lceil \log n \rceil$ with $\log n$. For example, if $n = 3$ and you consider the uniform input distribution, then the optimal average codeword length is $5/3 > \log 3$.

Second, the average codeword length is only guaranteed to be small with respect to the input distribution. For example, if the input distribution is $1/2, 1/4, 1/8, \ldots, 1/2^{n-1}, 1/2^{n-1}$ then the optimal code has codeword lengths $1,2,3,\ldots,n-1,n-1$, and so the average codeword length with respect to the uniform distribution is roughly $n/2$. The average codeword length with respect to the input distribution, however, is constant (tends to 2).

$\endgroup$
9
  • 1
    $\begingroup$ The average length of an optimal code is always at most $\lceil\log n\rceil$. $\endgroup$ Dec 23 '20 at 21:18
  • $\begingroup$ I’m sorry, I don’t understand your question. The average codeword length of an optimal code is always $O(n)$, as well as $O(n!)$, or $O(2^{2^n})$. Big O is just an upper bound. $\endgroup$ Dec 23 '20 at 21:32
  • $\begingroup$ You can construct prefix codes where the codewords are arbitrarily long. But that’s not so interesting. My example is more subtle, though - the average codeword length is constant. $\endgroup$ Dec 23 '20 at 21:39
  • $\begingroup$ A bit confused here, your example in last paragraph indicates "average length is at most log(n)" statement is false when input distribution is uniform, because as you mentioned, it is n/2 > log(n) $\endgroup$
    – lennon310
    Jan 5 at 16:42
  • $\begingroup$ When the input distribution is uniform and $n = 2^k$, a Huffman code simply consists of all $2^k$ binary strings of length $k$. In particular, the average length is exactly $\log n$. $\endgroup$ Jan 5 at 16:48

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.