Computer Science – Data Structures and Algorithms
Scientific paper
2008-06-30
Computer Science
Data Structures and Algorithms
Scientific paper
The ``state-of-the-art'' in Length Limited Huffman Coding algorithms is the $\Theta(ND)$-time, $\Theta(N)$-space one of Hirschberg and Larmore, where $D\le N$ is the length restriction on the code. This is a very clever, very problem specific, technique. In this note we show that there is a simple Dynamic-Programming (DP) method that solves the problem with the same time and space bounds. The fact that there was an $\Theta(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 $\Theta(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. We illustrate this with examples from web-proxy design and wireless mobile paging.
Golin Mordecai
Zhang Yan
No associations
LandOfFree
A Dynamic Programming Approach To Length-Limited Huffman Coding does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Dynamic Programming Approach To Length-Limited Huffman Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Dynamic Programming Approach To Length-Limited Huffman Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-155117