EFFICIENT CONSTRUCTION OF MINIMUM-REDUNDANCY CODES FOR LARGE ALPHABETS

We consider the problem of calculating minimum-redundancy codes for al phabets in which there is significant repetition of symbol weights. On a sorted-by-weight alphabet of n symbols and r distinct symbol weight s we show that a minimum-redundancy prefix code can be constructed in O (r + rlog(n/r)) time, and that a minimum-redundancy L-bit length-lim ited prefix code can be constructed in O(Lr + Lrlog(n/r)) time. When I is small relative to n-which is necessarily the case for most practic al coding problems on large alphabets-these bounds represent a substan tial improvement upon the best previous algorithms for these two probl ems, which consumed O(n) time and O(nL) time, respectively. The improv ed algorithms are also space-efficient.