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.