Efficient construction of minimum-redundancy codes for large alphabets
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 + rlog(n/r)) time, and that a minimum-redundancy L-bit length-limited 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 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.
minimum-redundancy code adaptive algorithm huffman code length-limited code package-merge algorithm prefix-free code text compression