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

A dynamic programming approach to length-limited huffman coding: Space reduction with the monge property

Authors Golin, Mordecai J. View this author's profile
Zhang, Yan
Issue Date 2010
Source IEEE Transactions on Information Theory , v. 56, (8), 2010, p. 3918-3929
Summary The state-of-the-art in length-limited Huffman coding (LLHC) algorithms is the Θ (nD)-time, Θ (n)-space one of Hirschberg and Larmore, where n is the size of the code and D ≤ n is the length restriction on the codewords. This is a very clever, very problem specific, technique. This paper presents a simple dynamic-programming (DP) method that solves the problem with the same time and space bounds. The fact that there was an Θ (nD) time DP algorithm was previously known; it is a straightforward DP with the Monge property (which permits an order of magnitude speedup). It was not interesting, though, because it also required Θ (nD) space. The main result of this paper is the technique developed for reducing the space. It is quite simple and applicable to many other problems modeled by DPs with the Monge property. This is illustrated with examples from web-proxy design and wireless mobile paging. © 2006 IEEE.
ISSN 0018-9448
Language English
Format Article
Access View full-text via DOI
View full-text via Scopus
View full-text via Web of Science