Huffman coding with letter costs: A linear-time approximation scheme
- Author(s): Golin, MJ
- Mathieu, C
- Young, NE
- et al.
Published Web Locationhttps://doi.org/10.1137/100794092
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 +?)-approximate solution in time O(n+f(?) log3 n), where n is the input size. © 2012 Society for Industrial and Applied Mathematics.