Huffman coding with unequal letter costs
|Authors||Golin, Mordecai J.
Young, Neal E.
|Summary||In the standard Huffman coding problem, one is given a set of words and for each word a positive frequency. The goal is to encode each word w as a codeword c(w) over a given alphabet. The encoding must be preﬁx free (no codeword is a preﬁx of any other) and should minimize the weighted average codeword size ∑<sub>w</sub> freq(w) \c(w)\. The problem has a well-known polynomial-time algorithm due to Huffman . Here we consider the generalization in which the letters of the encoding alphabet may have non-uniform lengths. The goal is to minimize the weighted average codeword length ∑<sub>w</sub>freq(w) cost(c(w)), where cost(s) is the sum of the (possibly non-uniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NP-hard, nor was it previously known to have a polynomial-time approximation algorithm. Here we describe a polynomial-time approximation scheme (PTAS) for the problem.|
Files in this item: