Prefix Codes: Equiprobable Words, Unequal Letter Costs
In: SIAM Journal on Computing, Jg. 25 (1996-12-31), Heft 6, S. 1281-1292
serialPeriodical
Zugriff:
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 rletters of nonuniform length, find a minimum-average-length prefix free set of ncodewords over the alphabet”; equivalently, “Find an optimal r-ary search tree with nleaves, 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\log ^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].
Titel: |
Prefix Codes: Equiprobable Words, Unequal Letter Costs
|
---|---|
Zeitschrift: | SIAM Journal on Computing, Jg. 25 (1996-12-31), Heft 6, S. 1281-1292 |
Veröffentlichung: | 1996 |
Medientyp: | serialPeriodical |
ISSN: | 0097-5397 (print) ; 1095-7111 (print) |
DOI: | 10.1137/S0097539794268388 |
Sonstiges: |
|