Prefix Codes: Equiprobable Words, Unequal Letter Costs
Mordecai J. Golin, Neal E. Young · 1994
We consider the following variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are non-uniform: Given an alphabet of unequal.length letters, find a minimum-average-length prefix-free set of n codewords over the alphabet. We show new structural properties of such codes, leading to an O(n log 2 r) time algorithm for finding them. This new algorithm is simpler and faster than the previously best known O(nr min{log n, r}) one due to Perl, Garey, and Even [5].