1
$\begingroup$

I have a question regarding the methodology of Huffman coding. So, is there a Huffman coding methodology that approximates the minimum average number of bits per decimal character when the odds of information symbols are not powers of 2? I can't understand or find anything relevant

$\endgroup$
3
  • 1
    $\begingroup$ Question 1: What is a “Huffman coding methodology”? $\endgroup$ – gnasher729 Mar 21 at 13:21
  • 2
    $\begingroup$ Question 2: The Huffman algorithm as I know it, is not restricted to powers of 2. Why do you think it is? $\endgroup$ – Hendrik Jan Mar 21 at 14:07
  • $\begingroup$ I can't make any sense of what you are saying. Please try to answer my question to clarify what you are talking about. $\endgroup$ – gnasher729 Mar 21 at 21:37
0
$\begingroup$

Huffman's algorithm solves the following problem. Given a distribution $P=(p_1,\ldots,p_n)$, find a prefix code $w_1,\ldots,w_n$ which minimizes the expected codeword length $$ \sum_{i=1}^n p_i |w_i|. $$ If $p_i = 2^{-\ell_i}$ then the optimal solution has $|w_i| = \ell_i$, and the resulting expected codeword length is exactly the entropy of $P$, but Huffman's algorithm works for any distribution.

If we call a distribution in which $p_i = 2^{-\ell_i}$ dyadic (there is no common term in the literature), then Huffman's algorithm "rounds" an arbitrary distribution $P$ into a dyadic distribution $Q$ which minimizes the Kullback–Leibler divergence $D(P\|Q)$.

We can get closer to the entropy of $P$ by encoding together groups of symbols. If you encode $m$-tuples of symbols together, then the expected codeword length per symbol (i.e., dividing the expression above by $m$) is at most $H(P) + 1/m$, and in particular, it tends to the entropy as $m \to \infty$. Shannon's source coding theorem shows that you cannot go below the entropy using any encoding scheme, so using Huffman coding in blocks is asymptotically optimal as the block size goes to infinity.

$\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.