Please use this identifier to cite or link to this item: http://hdl.handle.net/1783.1/702

Optimal prefix-free codes for unequal letter costs : dynamic programming with the Monge property

Authors Bradford, Phil
Golin, Mordecai J.
Larmore, Lawrence L.
Rytter, Wojciech
Issue Date 2000
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(n<sup>2+max(α,β)</sup>) time to construct such a minimal-cost set of n codewords, provided α and β are integers. In this paper we provide an O(n<sup>max(α,β)</sup>) 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.
Subjects
Language English
Format Technical report
Access
Files in this item:
File Description Size Format
200005.pdf 357849 B Adobe PDF