Twenty (or so) Questions: $D$-ary Length-Bounded Prefix Coding
| dc.creator | Baer, Michael B. | |
| dc.date | 2006-02-25 | |
| dc.date | 2007-06-20 | |
| dc.date.accessioned | 2026-07-07T08:16:23Z | |
| dc.date.available | 2026-07-07T08:16:23Z | |
| dc.description | 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)$. | |
| dc.description | 12 pages, 4 figures, extended version of cs/0701012 (accepted to ISIT 2007), formerly "Twenty (or so) Questions: $D$-ary Bounded-Length Huffman Coding" | |
| dc.identifier | https://arxiv.org/abs/cs/0602085 | |
| dc.identifier | http://arxiv.org/abs/cs/0602085 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/133759 | |
| dc.subject | Information Theory | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | G.2.2; F.2; E.4; H.1.1 | |
| dc.title | Twenty (or so) Questions: $D$-ary Length-Bounded Prefix Coding | |
| dc.type | text |