Computer Science – Information Theory
Scientific paper
2007-01-03
Computer Science
Information Theory
5 pages, 2 figures, accepted to ISIT 2007
Scientific paper
Efficient optimal prefix coding has long been accomplished via the Huffman algorithm. However, there is still room for improvement and exploration regarding variants of the Huffman problem. Length-limited Huffman coding, useful for many practical applications, is one such variant, in which codes are restricted to the set of codes in which none of the $n$ codewords is longer than a given length, $l_{\max}$. Binary length-limited coding can be done in $O(n l_{\max})$ time and O(n) space via the widely used Package-Merge algorithm. In this paper the Package-Merge approach is generalized without increasing complexity in order to introduce a minimum codeword length, $l_{\min}$, to allow for objective functions other than the minimization of expected codeword length, and to be applicable to both binary and nonbinary codes; nonbinary codes were previously addressed using a slower dynamic programming approach. These extensions have various applications -- including faster decompression -- and can be used to solve the problem of finding an optimal code with limited fringe, that is, finding the best code among codes with a maximum difference between the longest and shortest codewords. The previously proposed method for solving this problem was nonpolynomial time, whereas solving this using the novel algorithm requires only $O(n (l_{\max}- l_{\min})^2)$ time and O(n) space.
No associations
LandOfFree
$D$-ary Bounded-Length 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 $D$-ary Bounded-Length Huffman Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $D$-ary Bounded-Length Huffman Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-563644