Efficient Implementation of the Package-Merge Paradigm for Generating Length-Limited Codes


Andrew Turpin
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.

Alistair Moffat
Department of Computer Science, The University of Melbourne, Parkville 3052, Australia.


Status

Proceedings of CATS'96 (Computing: The Australasian Theory Symposium), Melbourne, Australia, January 29-30, 1996, pages 187-195.

Abstract

Until recently the most useful algorithm for generating length-limited minimum-redundancy codes was that of Larmore and Hirschberg. Their recursive package-merge algorithm generates a minimum-cost $L$-limited prefix-free code for a list of $n$ symbol weights in $O(n)$ space and $O(nL)$ time. In the last year or so we have developed a number of refinements to the package-merge method, some of which reduce the time required, and some of which reduce the space consumed. In this paper we show how the most desirable features of these various methods can be combined to form a single composite algorithm. The new implementation requires \runtime time and $O(r+L^2)$ auxiliary space, where $r$ is the number of distinct symbol weights in the input. Experiments with the composite algorithm demonstrate that $L$-limited codes can be generated in time and space directly comparable to that of traditional unrestricted minimum-redundancy (Huffman) codes.