The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 25 NO.6 / (1996))
Prefix Codes: Equiprobable Words, Unequal Letter Costs
Mordecai J. Golin, Neal Young,
Pages. 1281-1292
Abstract 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 $r$ letters of non-uniform length, find a minimum-average-length prefix-free set of $n$ codewords over the alphabet"; equivalently, "Find an optimal $r$-ary search tree with $n$, leaves, where each leaf is accessed with equal probability but the cost to descend from a parent to its $i$th child depends on $i$." We show new structural properties of such codes, leading to an $O(nlog^2 r)$-time algorithm for finding them. This new algorithm is simpler and faster than the best previously known $O(nr min{log n,r})$-time algorithm, due to Perl, Garey, and Even [J. Assoc. Comput. Mach., 22 (1975), pp.202-214].
Contents 1. Introduction
2. Shallow trees
2.1. Defining the trees
2.2. Relation of successive trees
3. Computing the trees
3.1. Only $O(n\log r)$ replacements total
3.2. Limiting the relevant terminals
3.3. The algorithm in detail
Key words lgorithms, Huffman codes, prefix codes, trees.
Mathmatical Subject Classification 68Q25