Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/8013

HUFFMAN CODING WITH LETTER COSTS: A LINEAR-TIME APPROXIMATION SCHEME

Authors Golin, Mordecai J. View this author's profile
Mathieu, Claire
Young, Neal E.
Issue Date 2012
Source SIAM journal on computing , v. 41, (3), 2012, p. 670-713
Summary We give a polynomial-time approximation scheme for the generalization of Huffman coding in which codeword letters have nonuniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1 + epsilon)-approximate solution in time O(n + f(epsilon) log(3) n), where n is the input size.
Subjects
ISSN 0097-5397
Rights Copyright 2012 Society for Industrial and Applied Mathematics. The definitive published version is available at http://dx.doi.org/10.1137/100794092
Language English
Format Article
Access View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Find@HKUST
Files in this item:
File Description Size Format
100794092.pdf 562458 B Adobe PDF