Incremental Calculation of Minimum-Redundancy Length-Restricted Codes
Mike Liddell
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Alistair Moffat
Department of Computer Science and Software Engineering,
The University of Melbourne,
Victoria 3010, Australia.
Status
IEEE Trans. Communications, 55(3):427-435.
This paper was presented in preliminary form at the
2002 IEEE Data Compression Conference.
Abstract
The length-restricted code construction problem arises when
using prefix codes for large messages and also for search-tree
depth minimization. A problem instance comprises an ordered set
of input frequencies, {f_1,f_2,...,f_n} and a maximum codeword
length L bits. The package-merge algorithm of Larmore and Hirschberg
constructs a minimum-redundancy length-restricted code in O(nL) time.
Here we present an algorithm which computes a minimum-redundancy
length-restricted code in O((H-L+1)n) time, by starting with a
minimum-redundancy (Huffman) code, and then refining it to meet the
length limit. The new algorithm is suited to problems where H-L
is small; and when H-L>L-logn, the new algorithm outperforms all
previous methods. Experimental results confirm the behavior of the
new algorithm.
Full text
http://dx.doi.org/10.1109/TCOMM.2007.892446.