In-Place Calculation of Minimum-Redundancy Codes
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.
Status
Submitted.
Preliminary version
presented at the 1995 Workshop on Algorithms and Data
Structures, Kingston, Ontario, August 1995
(LNCS volume 955), pages 393-402.
Abstract
The {\em minimum-redundancy prefix-free code problem\/} is to
determine, for a given array $f = [f_i\mid i \in
\{1,\ldots, n\}]$ of $n$ frequencies, an array
$c = [c_i\mid i \in \{1,\ldots, n\}]$ of $n$ integer codeword lengths
such that $\sum_{i=1}^n 2^{-c_i} \leq 1$ and $\sum_{i=1}^n f_i c_i$
is minimized.
Huffman's famous greedy algorithm solves this problem in $O(n \log
n)$ time if $f$ is unsorted; and can be implemented to run in
$O(n)$ time if the input array $f$ is sorted.
In this paper the space usage of the greedy method is considered.
It is shown that if $f$ is sorted then the
array $c$ can be calculated in-place, with $c_i$ overwriting $f_i$, in $O(n)$
time by
using $O(1)$ additional space.
The new implementation leads directly to an $O(n \log n)$ time and
$n+O(1)$ words of extra space implementation for the case when $f$ is
not sorted.
The proposed method is simple to implement and executes quickly.
Source code
Source code for the algorithm described in the paper is available
here.