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.