2007/01/03 by Michael B. Baer, Baer, Michael B.
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Natural Language Processing Techniques #RNA and protein synthesis mechanisms #cs.DS #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.cs/0701012
5 pages, 2 figures, accepted to ISIT 2007
arxiv created 2007/04/17 · arxiv updated 2009/12/01
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, lmax. Binary length-limited coding can be done in O(n lmax) 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, lmin, 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 (lmax- lmin)2) time and O(n) space.