1
$\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$
2
$\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$

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.