Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1998 Copyright 1998 University of Bonn, Department of Computer Science, Abt. V
85197

Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
Phil Bradford, Mordecai J. Golin, Lawrence L. Larmore, Wojciech Rytter
[Download PostScript] [Download PDF]

In this paper we discuss a variation of the classical {\em Huffman coding problem\/}: finding optimal prefix-free codes for unequal letter costs. Our problem consists of finding a minimal cost prefix-free code in which the encoding alphabet consists of unequal cost (length) letters, with lengths $\alpha$ and $\beta$. The most efficient algorithm known previously required $O(n^{2+\max(\alpha,\beta)})$ time to construct such a minimal-cost set of $n$ codewords. In this paper we provide an $O(n^{\max(\alpha,\beta)})$ 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.

Last Change: 08/18/99 at 13:00:38
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V