Skip to main content
eScholarship
Open Access Publications from the University of California

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Huffman coding with letter costs: A linear-time approximation scheme

  • Author(s): Golin, MJ
  • Mathieu, C
  • Young, NE
  • et al.

Published Web Location

https://doi.org/10.1137/100794092
Abstract

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.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Main Content
Current View