Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1998 Copyright 1998 Universität Bonn, Institut für Informatik, 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  English Universität Bonn -> Institut für Informatik -> Abteilung V