HUFFMAN CODING WITH LETTER COSTS: A LINEAR-TIME APPROXIMATION SCHEME
Golin, Mordecai J.
Young, Neal E.
|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.|
|Rights||Copyright 2012 Society for Industrial and Applied Mathematics. The definitive published version is available at http://dx.doi.org/10.1137/100794092|
View full-text via DOI
View full-text via Web of Science
View full-text via Scopus
Files in this item: