Optimal Prefix-free Codes for Unequal Letter Costs : Dynamic Programming with the Monge Property
Bradford, Phillip G.
Golin, Mordecai J.
Larmore, Lawrence L.
|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|
View full-text via Scopus
Files in this item: