Skip to main content
eScholarship
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.
Abstract

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
For improved accessibility of PDF content, download the file to your device.
Current View