Efficient construction of minimum-redundancy codes for large alphabets

Abstract

We consider the problem of calculating minimumredundancy 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 + rlog(ra/r)) time, and that a minimum-redundancy L-bit length-limited prefix code can be constructed in O (Lr + Lrlog(ra/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 imp..