Please use this identifier to cite or link to this item:

Optimal Prefix-free Codes for Unequal Letter Costs : Dynamic Programming with the Monge Property

Authors Bradford, Phillip G.
Golin, Mordecai J. View this author's profile
Larmore, Lawrence L.
Rytter, Wojciech
Issue Date 2000
Source Lecture Notes in Computer Science , v. 1461, 1998, p. 43-54
Summary In this paper we discuss the problem of finding optimal prefix-free codes for unequal letter costs, a variation of the classical Huffman coding problem. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths α and β. The most efficient algorithm known previously requires O(n2+max(α,β)) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(nmax(α,β)) time algorithm. Our improvement comes from the use of a more sophisticated modeling of the problem, combined with the observation that the problem possesses a "Monge property" and that the SMAWK algorithm on monotone matrices can therefore be applied.
Note 6th Annual European Symposium on Algorithms, ESA 1998, Venice, Italy, 24 August 1998 through 26 August 1998, Code 103179
ISSN 0302-9743
ISBN 3540648488
Language English
Format Technical report
Access View full-text via Scopus
Files in this item:
File Description Size Format
200005.pdf 357849 B Adobe PDF