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.


Presented at the 1995 Workshop on Algorithms and Data Structures, Kingston, Ontario, August 1995 (LNCS volume 955), 393-402.


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

Source code

Source code for the algorithm described in the paper is available here.