The problem of variable-rate lossless data compression is considered, for codes with and without prefix constraints. Sharp bounds are derived for the best achievable compression rate of memoryless sources, when the excess-rate probability is required to be exponentially small in the blocklength. Accurate nonasymptotic expansions with explicit constants are obtained for the optimal rate, using 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 of sequences with small empirical entropy, which might be of independent interest. Examples are shown indicating that, in the small excess-rate-probability regime, the approximation to the fundamental limit of the compression rate suggested by these bounds is significantly more accurate than the approximations provided by either normal approximation or error exponents. The new bounds reinforce the crucial operational conclusion that, in applications where the blocklength is 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, determined via the inverse error exponent function and the blocklength.

翻译：本文研究了可变速率无损数据压缩问题，涵盖具有前缀约束和无前缀约束的编码方案。针对无记忆信源，当要求超速率概率随块长呈指数级衰减时，推导了最佳可达压缩率的精确界。利用大偏差理论与高斯逼近工具，获得了包含显式常数的精确非渐近展开式以描述最优速率。在信源分布未知的情况下，通过引入显式的'普适性代价'项，得到了普适可达性结果。该结果基于对经验熵较小序列数量的精细组合估计，这一估计本身可能具有独立的研究价值。示例表明，在超速率概率较小的区域，由这些界所提示的压缩率基本极限近似，相较于正态近似或误差指数所提供的近似，其精确度显著更高。新界强化了一个关键的操作性结论：在块长相对较短且对速率有严格保证的应用场景中，最佳可达速率不再接近熵值，而是由逆误差指数函数与块长共同决定的、更切合实际的适当速率。