Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/699
Huffman coding with unequal letter costs
Authors  Golin, Mordecai J.
Kenyon, Claire Young, Neal E. 


Issue Date  2002  
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 ∑_{w} freq(w) \c(w)\. The problem has a wellknown polynomialtime algorithm due to Huffman [15]. Here we consider the generalization in which the letters of the encoding alphabet may have nonuniform lengths. The goal is to minimize the weighted average codeword length ∑_{w}freq(w) cost(c(w)), where cost(s) is the sum of the (possibly nonuniform) lengths of the letters in s. Despite much previous work, the problem is not known to be NPhard, nor was it previously known to have a polynomialtime approximation algorithm. Here we describe a polynomialtime approximation scheme (PTAS) for the problem.  
Subjects  
Language  English 

Format  Technical report  
Access 
Files in this item:
