<p>We consider the problem of lossless data compression for codes with and without prefix constraints, when strict performance constraints are placed on the excess-rate probability. Sharp nonasymptotic bounds are derived for the best achievable compression rate when the excess-rate probability is required to be exponentially small in the blocklength. These are obtained via tools from large deviations and Gaussian approximation. When the source distribution is unknown, a universal achievability result is obtained with an explicit “price for universality” term. This is based on a fine combinatorial estimate on the number </p><p>of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that the approximation to the fundamental performance limits suggested </p><p>by these bounds is significantly more accurate than previous approaches. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is </p><p>relatively short and where stringent guarantees are required on the rate, the best achievable rate is no longer close to the entropy. Rather, it is an appropriate, more pragmatic rate, </p><p>determined by the inverse error exponent function and the blocklength. This is joint work with Andreas Theocharous and Lampros Gavalakis.</p><p><br></p>
