$D$-ary Bounded-Length Huffman Coding

Simple item page
dc.creatorBaer, Michael B.
dc.date2007-01-03
dc.date2007-04-17
dc.date.accessioned2026-07-07T08:16:54Z
dc.date.available2026-07-07T08:16:54Z
dc.descriptionEfficient 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.
dc.description5 pages, 2 figures, accepted to ISIT 2007
dc.identifierhttps://arxiv.org/abs/cs/0701012
dc.identifierhttp://arxiv.org/abs/cs/0701012
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/133947
dc.subjectInformation Theory
dc.subjectData Structures and Algorithms
dc.subjectG.2.2; F.2; E.4; H.1.1
dc.title$D$-ary Bounded-Length Huffman Coding
dc.typetext

Files

Collections

arXiv