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.
aht@cs.mu.oz.au
Alistair Moffat
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
alistair / csse.unimelb.edu.au
Abstract
The original description of the package-merge algorithm
generates a
length-limited minimum-redundancy code in O(nL) time and O(n) space.
In the last year or so we have developed 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
O(min{Lr\log(n/r), (L-\log n)n})
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.
Conference Home Page