###
Efficient Construction of Minimum-Redundancy Codes
for Large Alphabets

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

IEEE Trans. Information Theory, 44(4):1650-1657, July 1998.

#### Abstract

We consider the problem of calculating minimum-redundancy codes for
alphabets in which there is significant repetition of symbol weights.
On a sorted-by-weight alphabet of $n$ symbols and $r$ distinct symbol
weights we show that a minimum-redundancy prefix code can be constructed in
$O(r+r\log(n/r))$ time, and that a minimum-redundancy $L$-bit length-limited
prefix code can be constructed in $O(Lr+Lr\log(n/r))$ time.
When $r$ is small relative to
$n$---which is necessarily the case for most practical
coding problems on large alphabets---these bounds represent a
substantial improvement upon the best previous algorithms for these two
problems, which consumed $O(n)$ time and $O(nL)$ time respectively.
The improved algorithms are also space-efficient.