PREFIX CODES - EQUIPROBABLE WORDS, UNEQUAL LETTER COSTS

Authors
Citation
Mj. Golin et N. Young, PREFIX CODES - EQUIPROBABLE WORDS, UNEQUAL LETTER COSTS, SIAM journal on computing, 25(6), 1996, pp. 1281-1292
Citations number
8
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods",Mathematics
Journal title
ISSN journal
00975397
Volume
25
Issue
6
Year of publication
1996
Pages
1281 - 1292
Database
ISI
SICI code
0097-5397(1996)25:6<1281:PC-EWU>2.0.ZU;2-L
Abstract
We consider the following Variant of Huffman coding in which the costs of the letters, rather than the probabilities of the words, are nonun iform: ''Given an alphabet of r letters of nonuniform length, find a m inimum-average-length prefix-free set of n codewords over the alphabet ''; equivalently, ''Find an optimal r-ary search tree with n leaves, w here each leaf is accessed with equal probability but the cost to desc end from a parent to its ith child depends on i.'' We show new structu ral properties of such codes, leading to an O(nlog(2) r)-time algorith m for finding them, This new algorithm is simpler and faster than the best previously known O(nr min{logn, r})-time algorithm, due to Perl, Garey, and Even [J. Assoc, Comput. Mach., 22 (1975), pp. 202-214].