Three space-economical algorithms for calculating minimum-redundancy prefix codes
The minimum-redundancy prefix code problem is to determine, for a given list W [w(1),...,w(n)] of n positive symbol weights, a list L = (l(1)...,l(n)] of n corresponding integer codeword lengths such that Sigma (n)(i=1) 2(-li) less than or equal to1 and Sigma (n)(i=1) w(i)l(i) is minimized. Let us consider the case where W is already sorted. In this case, the output list L can be represented by a list M = [m(1),...,m(H)], where m(l), for l = 1,..., H, denotes the multiplicity of the codeword length l in L and H is the length of the greatest codeword. Fortunately, H is proved to be O(min{log(1/p(1)), n}, where p(1) is the smallest symbol probability, given by w(1) / Sigma (n)(i=1) w(i). In this paper, we present the Fast LazyHuff (F-LazyHuff), the Economical LazyHuff (E-LazyHuff), and the Best LazyHuff (B-LazyHuff) algorithms. F-LazyHuff runs in O(n) time but requires O(min{H-2, n}) additional space. On the other hand, E-LazyHuff runs in O(n + n log(n/H)) time, requiring only O(H) additional space. Finally, B-LazyHuff asymptotically overcomes the previous algorithms, requiring only O(n) time and O(H) additional space. Moreover, our three algorithms have the advantage of not writing over the input buffer during code calculation, a feature that is very useful in some applications.
algorithms prefix codes data compression huffman codes large alphabets lazy approach minimum redundancy space economical