5
$\begingroup$

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, then $H\le L_1 \le H+1$ and $H\le L_2< H+2$, where $H$ is the (base-2 Shannon) entropy of the symbol distribution.

Is anything known about the average redundancy of Huffman and Hu-Tucker codes, that is, the expected value of $R_1 = L_1-H$ or $R_2 = L_2-H$, when the symbol weights are random?

Definition & Details:

Assume we have $n$ symbols $a_1,\ldots,a_n$ with weights $\vec P=(P_1,\ldots,P_n)$, where these weights are themselves random, e.g., they are uniformly drawn from all stochastic vectors (so that $P_i\ge0$ and $P_1+\cdots+P_n = 1$ a.s.); stated otherwise: $\vec P$ has a $\mathrm{Dirichlet}(1,\ldots,1)$ distribution).

Then $H = - \sum_{i=1}^n P_i \log_2(P_i)$ and $L_{1,2} = \sum P_i \operatorname{depth}(a_i)$, where $\mathrm{depth}(a_i)$ is the depth (number of edges on path from root) of leaf $a_i$ in an optimal binary tree on leaves $a_1,\ldots,a_n$ (Huffman tree) for $L_1$ and the depth in an optimal binary search tree with leaves $a_1\le a_2\le\cdots a_n$ (optimal alphabetic tree).

My Attempts:

I am seeking an analytic solution, in the best case as a closed formula in $n$. I can approximate the expectations with a Monte Carlo simulation, here are a few example values (from 10,000,000 repetitions each; up to the given digits several repetitions agreed; * only 10,000 repetitions)

n    E[R2]
3    0.297
4    0.284
5    0.268
6    0.253*
10   0.217*

Note that the upper bound of $2$ is far from tight here.

This question is probably related, but was posed unclearly and does not have an answer.

A somewhat similar problem, has been solved by Szpankowski. There, alphabet symbols are blocks of bits of length $n$, generated by a memoryless source with $p<0.5$ is the probability for $0$ in the block. The average redundancy of different codes, including Huffman's, are computed for large $n$. Here the symbol probabilities are fixed, and so is the redundancy; the average here means average redundancy over all symbols, not over random symbols weights.

This does not answer my question above thus.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.