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

UC Riverside

UC Riverside Previously Published Works bannerUC Riverside

Prefix codes: Equiprobable words, unequal letter costs

  • Author(s): Golin, MJ
  • Young, N
  • et al.

We consider the following variant of Huffman coding in which the costs of the letters rather than the probabilities of the words, are nonuniform: "Given an alphabet of r letters of nonuniform 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 ith child depends on i." We show new structural properties of such codes, leading to an O(n log2 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].

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