Skip to main content
Open Access Publications from the University of California
Notice: eScholarship will undergo scheduled maintenance from Tuesday, January 21 to Wednesday, January 22. Some functionality may not be available during this time. Learn more at eScholarship Support.
Download PDF
- Main
Huffman Coding with Letter Costs: A Linear-Time Approximation Scheme
Published Web Location
https://doi.org/10.1137/100794092Abstract
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
For improved accessibility of PDF content, download the file to your device.
Enter the password to open this PDF file:
File name:
-
File size:
-
Title:
-
Author:
-
Subject:
-
Keywords:
-
Creation Date:
-
Modification Date:
-
Creator:
-
PDF Producer:
-
PDF Version:
-
Page Count:
-
Page Size:
-
Fast Web View:
-
Preparing document for printing…
0%