HUFFMAN CODING WITH LETTER COSTS: A LINEAR-TIME APPROXIMATION SCHEME
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.
huffman coding with letter costs polynomial-time approximation scheme