HKUST Library Institutional Repository Banner

HKUST Institutional Repository >
Computer Science and Engineering >
CSE TCSC Research Reports >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/699
Title: Huffman coding with unequal letter costs
Authors: Golin, Mordecai J.
Kenyon, Claire
Young, Neal E.
Keywords: Huffman-coding
Polynomial-time approximation scheme
Issue Date: 2002
Series/Report no.: HKUST Theoretical Computer Science Center Research Report ; HKUST-TCSC-2002-02
Abstract: 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 prefix free (no codeword is a prefix of any other) and should minimize the weighted average codeword size ∑w freq(w) |c(w)|. The problem has a well-known polynomial-time algorithm due to Huffman [15]. 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 ∑wfreq(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.
URI: http://hdl.handle.net/1783.1/699
Appears in Collections:CSE TCSC Research Reports

Files in This Item:

File Description SizeFormat
200202.pdf124KbAdobe PDFView/Open

All items in this Repository are protected by copyright, with all rights reserved.