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.