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$.