###
A Fast and Space-Economical Algorithm for Length-Limited Coding

Jyrki Katajainen

Department of Computer Science,
University of Copenhagen,
Universitetsparken 1,
DK-2100 Copenhagen East, Denmark.

Alistair Moffat

Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.

Andrew Turpin

Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.

#### Status

Presented at the 1995 International Symposium
on Algorithms and Computation, Cairns, Australia, December 1995.
(LNCS volume 1004, pages 12-21).

#### Abstract

The {\em minimum-redundancy prefix code problem\/} is to determine a list
of integer codeword lengths $l = [l_i \,|\, \ioneton]$, given a
list of $n$ symbol weights $p = [p_i \,|\, \ioneton ]$, such that
$\sum_{i=1}^n 2^{-l_i} \le 1$, and $\sum_{i=1}^n l_i p_i$ is
minimised.
An extension is the {\em minimum-redundancy length-limited
prefix code problem\/}, in which the further constraint $l_i \le L$
is imposed, for all $\ioneton$ and some integer $L \ge \lceil
\log_2 n \rceil$.
The package-merge algorithm of Larmore and Hirschberg generates
length-limited codes in $O(nL)$ time
using $O(n)$ words of auxiliary
space.
In this paper we show how the size of this work space
can be reduced to $O(L^2)$.
This represents a substantial improvement, since for practical
purposes $L$ is $\Theta(\log n)$.

#### Published paper

http://dx.doi.org/10.1007/BFb0015404