A Dynamic Programming Approach to Length-Limited Huffman Coding: Space Reduction With the Monge Property
Mordecai J. Golin, Yan Zhang · IEEE Transactions on Information Theory · 2010
The “state-of-the-art” in length-limited Huffman coding (LLHC) algorithms is theΘ(nD)-time,Θ(n)-space one of Hirschberg and Larmore, wherenis the size of the code andD≤nis 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 theMongeproperty (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 thetechniquedeveloped 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.