A fast and space-economical algorithm 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. With the optimal list of codeword lengths, an optimal canonical code can be easily obtained. If W is already sorted, then this optimal code can also be represented by the list M=[m₁ ,...,m_H], where m_l, for l=1,...,H, denotes the number of codewords with length l and H is the length of the longest 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. The E-LazyHuff algorithm uses a lazy approach to calculate optimal codes in O(nlog(n/H)) time, requiring only O(H) additional space. In addition, the input weights are not destroyed during the code calculation. We propose a new technique, which we call homogenization, that can be used to improve the time efficiency of algorithms for constructing optimal prefix codes. Next, we introduce the Best LazyHuff algorithm (B-LazyHuff) as an application of this technique. B-LazyHuff is an O(n)-time variation of the E-LazyHuff algorithm. It also requires O(H) additional space and does not destroy the input data