Two space-economical algorithms for calculating minimum redundancy prefix codes

The minimum redundancy prefix code problem is to determine, for a given list W=[w₁,...,w_n] of n positive symbol weights, a list L=[l₁,...,l_n] of n corresponding integer codeword lengths such that Σ_i=1ⁿ2 ^-li⩽1 and Σ_i=1ⁿw_il _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₁,...,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₁)),n}), where p₁ is the smallest symbol probability, given by w₁/Σ_i=1ⁿ w_i. We present the F-LazyHuff and the E-LazyHuff algorithms. F-LazyHuff runs in O(n) time but requires O(min{H²,n}) additional space. On the other hand, E-LazyHuff runs in O(nlog(n/H)) time, requiring only O(H) additional space. Finally, since our two algorithms have the advantage of not writing at the input buffer during the code calculation, we discuss some applications where this feature is very useful