Most of the attention in statistical compression is given to the space used by the compressed sequence, a problem completely solved with optimal prefix codes. However, in many applications, the storage space used to represent the prefix code itself can be an issue. In this paper we introduce and compare several techniques to store prefix codes. Let @math be the sequence length and @math be the alphabet size. Then a naive storage of an optimal prefix code uses @math bits. Our first technique shows how to use @math bits to store the optimal prefix code. Then we introduce an approximate technique that, for any @math , @math bits to store a prefix code with average codeword length at most @math times the minimum. In all cases, our data structures allow encoding and decoding of any symbol in @math time. We experimentally compare our new techniques with the state of the art, showing that we achieve 6--8-fold space reductions, at the price of a slower encoding (2.5--8 times slower) and decoding (12--24 times slower). The approximations further reduce this space and improve the time significantly, up to recovering the speed of classical implementations, for a moderate penalty in the average code length. As a byproduct, we compare various heuristic, approximate, and optimal algorithms to generate length-restricted codes, showing that the optimal ones are clearly superior and practical enough to be implemented.
All these approximations require @math time plus the time to build the Huffman tree. A technique to obtain the optimal length-restricted prefix code, by Larmore and Hirshberg @cite_24 , performs in @math time by reducing the construction to a binary version of the coin-collector's problem.
@cite_24
2021302562
An O ( nL )-time algorithm is introduced for constructing an optimal Huffman code for a weighted alphabet of size n , where each code string must have length no greater than L . The algorithm uses O ( n ) space.