Computer Science – Information Theory
Scientific paper
2006-02-25
Computer Science
Information Theory
12 pages, 4 figures, extended version of cs/0701012 (accepted to ISIT 2007), formerly "Twenty (or so) Questions: $D$-ary Bound
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, for 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 and with even smaller asymptotic complexity using a lesser-known algorithm. In this paper these algorithms are generalized without increasing complexity in order to introduce a minimum codeword length constraint $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 fast decompression and a modified version of the game ``Twenty Questions'' -- 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 linear-space algorithm requires only $O(n (l_{\max}- l_{\min})^2)$ time, or even less if $l_{\max}- l_{\min}$ is not $O(\log n)$.
No associations
LandOfFree
Twenty (or so) Questions: $D$-ary Length-Bounded Prefix 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 Twenty (or so) Questions: $D$-ary Length-Bounded Prefix Coding, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Twenty (or so) Questions: $D$-ary Length-Bounded Prefix Coding will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-730323