### 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