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