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.
Multiplicative approximations have the potential of yielding codes that can be represented within @math bits. Adler and Maggs @cite_34 showed it generally takes more than ((9 40) n^ 1 (20 c) n ) bits to store a prefix code with average codeword length at most (c H (P) ). Gagie @cite_0 @cite_43 @cite_7 showed that, for any constant (c 1 ), it takes @math bits to store a prefix code with average codeword length at most (c H (P) + 2 ). He also showed his upper bound is nearly optimal because, for any positive constant @math , we cannot always store a prefix code with average codeword length at most (c H (P) + o ( n) ) in @math bits. Note that our result does not have the additive term @math '' in addition to the multiplicative term, which is very relevant on low-entropy texts.
@cite_0 @cite_43 @cite_34 @cite_7
2080686589 2150359208 2066209652 2011648667
We briefly survey some concepts related to empirical entropy--normal numbers, de Bruijn sequences and Markov processes-- and investigate how well it approximates Kolmogorov complexity. Our results suggest lth-order empirical entropy stops being a reasonable complexity metric for almost all strings of length m over alphabets of size n about when nl surpasses m. In this paper we examine the problem of sending an n-bit data item from a client to a server across an asymmetric communication channel. We demonstrate that there are scenarios in which a high-speed link from the server to the client can be used to greatly reduce the number of bits sent from the client to the server across a slower link. In particular, we assume that the data item is drawn from a probability distribution D that is known to the server but not to the client. We present several protocols in which the expected number of bits transmitted by the server and client are O(n) and O(H(D)+1), respectively, where H(D) is the binary entropy of D (and can range from 0 to n). These protocols are within a small constant factor of optimal in terms of the number of bits sent by the client. The expected number of rounds of communication between the server and client in the simplest of our protocols is O(H(D)). We also give a protocol for which the expected number of rounds is only O(1), but which requires more computational effort on the part of the server. A third technique provides a tradeoff between the computational effort and the number of rounds. These protocols are complemented by several lower bounds and impossibility results. We prove that all of our protocols are existentially optimal in terms of the number of bits sent by the server, i.e., there are distributions for which the total number of bits exchanged has to be at least n. In addition, we show that there is no protocol that is optimal for every distribution (as opposed to just existentially optimal) in terms of bits sent by the server. We demonstrate this by proving that it is undecidable to compute (even approximately), for an arbitrary distribution D, the expected number of bits that must be exchanged by the server and client on the distribution D. We show how any dynamic instantaneous compression algorithm can be converted to an asymmetric communication protocol, with which a server with high bandwidth can help clients with low bandwidth send it messages. Unlike previous authors, we do not assume the server knows the messages' distribution, and our protocols are the first to use only one round of communication for each message.