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