In-Place Calculation of Minimum-Redundancy Codes
Alistair Moffat
Department of Computer Science,
The University of Melbourne,
Parkville 3052, Australia.
Jyrki Katajainen
Department of Computer Science,
University of Copenhagen,
Universitetsparken 1,
DK-2100 Copenhagen East,
Denmark.
Status
Presented at the 1995 Workshop on Algorithms and Data
Structures, Kingston, Ontario, August 1995
(LNCS volume 955), 393-402.
Abstract
The {\em optimal prefix-free code problem\/} is to determine, for a
given array $p = [p_i\,|\,i \in \{1\ldots n\}]$ of $n$ weights, an
integer array $l = [l_i\,|\,i \in \{1\ldots n\}]$ of $n$ codeword
lengths such that $\sum_{i=1}^n 2^{-l_i} \leq 1$ and $\sum_{i=1}^n p_i
l_i$ is minimized. Huffman's famous greedy algorithm solves this
problem in $O(n \log n)$ time, if $p$ is unsorted; and can be
implemented to execute in $O(n)$ time, if the input array $p$ is
sorted. Here we consider the space requirements of the greedy method.
We show that if $p$ is sorted then it is possible to calculate the
array $l$ in-place, with $l_i$ overwriting $p_i$, in $O(n)$ time and
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 $p$ is not sorted. The proposed method is simple to
implement and executes quickly.
Published paper
http://dx.doi.org/10.1007/3-540-60220-8_79
Source code
Source code for the algorithm described in the paper is available
here.