Why some Huffman codes have efficiency better than others?
-
05-11-2019 - |
Pergunta
Consider the alphabet $\mathcal{A}=\{a_0,a_1,a_2,a_3\}$ with the the following corresponding probabilities:
- $\, p_{A,1}=\{0.5,0.3,0.15,0.05\}$
- $\, p_{A,2}=\{0.5,0.25,0.125,0.125\}$
The entropy for the first case is $H(A,1)= 1.65$, and for the second is $H(A,2)=1.75$. The Huffman code for both can be $\{0, 10, 110, 111 \}$ or $\{1, 01, 001, 000 \}$. The average lengths are $\bar{L_{A,1}}=1.7$ and $\bar{L_{A,2}}=1.75$. The efficiencies are $97.14 \%$ and $100 \%$ for case $1$ and $2$ respectively. Why is that? The only reasonable explanation is the probabilities themselves. In the second case, it is somehow equally divided. Can anyone explain?
Nenhuma solução correta
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange