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