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
Proc. IEEE Data Compression Conference,
Snowbird, Utah, April 2002, pages 182-191.
Abstract
The prefix-free coding problem is to take an input message of $m$
symbols, of which $n$ are distinct, and produce a binary output
string which can be uniquely deciphered.
The length-restricted prefix-free coding problem is to create a
prefix-free code in which no codeword has length greater than $L$.
In this paper we present a variant of the package-merge algorithm
for calculating length-restricted codes
which operates in time $O(n(H-L+1))$, where $H$ is the length of a
longest codeword in the corresponding unrestricted code.
Unlike other package-merge variants, the new mechanism is fastest
when $L$ is close to $H$.