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
2013021781 2021302562 1843157236 2009279347
An algorithm is given for constructing a binary tree of minimum weighted path length for n nonnegative weights under the constraint that no path length exceed a given bound L. The number of operations required is proportional to @math . Such problems, which impose an additional constraint on the usual Huffman tree, arise in many applications, including computer file searching and the construction of optimal prefix codes under certain practical conditions. 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. We introduce and study a problem that we refer to as the optimal split tree problem. The problem generalizes a number of problems including two classical tree construction problems including the Huffman tree problem and the optimal alphabetic tree. We show that the general split tree problem is NP-complete and analyze a greedy algorithm for its solution. We show that a simple modification of the greedy algorithm guarantees O(log n) approximation ratio. We construct an example for which this algorithm achieves Ω(log n log log n) approximation ratio. We show that if all weights are equal and the optimal split tree is of depth O(log n). then the greedy algorithm guarantees O(log n log log n) approximation ratio. We also extend our approximation algorithm to the construction of a search tree for partially ordered sets. We give a 7.18-approximation algorithm for the minimum latency problem that uses only @math calls to the prize-collecting Steiner tree (PCST) subroutine of Goemans and Williamson. This improves the previous best algorithms in both performance guarantee and running time. A previous algorithm of Goemans and Kleinberg for the minimum latency problem requires an approximation algorithm for the @math -minimum spanning tree ( @math -MST) problem which is called as a black box for each value of @math . Their algorithm can achieve an approximation factor of 10.77 while making @math PCST calls, a factor of 8.98 using @math PCST calls, or a factor of @math using @math PCST calls, via the @math -MST algorithms of Garg, Arya and Ramesh, and Arora and Karakostas, respectively. Here @math denotes the number of nodes in the instance, and @math is the largest edge cost in the input. In all cases, the running time is dominated by the PCST calls. Since the PCST subroutine can be implemented to run in @math time, the overall running time of our algorithm is @math . We also give a faster randomized version of our algorithm that achieves the same approximation guarantee in expectation, but uses only @math PCST calls, and derandomize it to obtain a deterministic algorithm with factor @math , using @math PCST calls. The basic idea for our improvement is that we do not treat the @math -MST algorithm as a black box. This allows us to take advantage of some special situations in which the PCST subroutine delivers a 2-approximate @math -MST. We are able to obtain the same approximation ratio that would be given by Goemans and Kleinberg if we had access to 2-approximate @math -MSTs for all values of @math , even though we have them only for some values of @math that we are not able to specify in advance. We also extend our algorithm to a weighted version of the minimum latency problem.