Gavalakis Lampros, Kontoyiannis Ioannis
Department of Engineering, University of Cambridge, Trumpington Street, Cambridge CB2 1PZ, UK.
Entropy (Basel). 2020 Jun 25;22(6):705. doi: 10.3390/e22060705.
The problem of determining the best achievable performance of arbitrary lossless compression algorithms is examined, when correlated side information is available at both the encoder and decoder. For arbitrary source-side information pairs, the conditional information density is shown to provide a sharp asymptotic lower bound for the description lengths achieved by an arbitrary sequence of compressors. This implies that for ergodic source-side information pairs, the conditional entropy rate is the best achievable asymptotic lower bound to the rate, not just in expectation but with probability one. Under appropriate mixing conditions, a central limit theorem and a law of the iterated logarithm are proved, describing the inevitable fluctuations of the second-order asymptotically best possible rate. An idealised version of Lempel-Ziv coding with side information is shown to be universally first- and second-order asymptotically optimal, under the same conditions. These results are in part based on a new almost-sure invariance principle for the conditional information density, which may be of independent interest.
当编码器和解码器都有相关辅助信息时，研究了确定任意无损压缩算法可达到的最佳性能这一问题。对于任意的源 - 辅助信息对，条件信息密度被证明为任意一系列压缩器所实现的描述长度提供了一个严格的渐近下界。这意味着对于遍历的源 - 辅助信息对，条件熵率是速率可达到的最佳渐近下界，不仅在期望意义下，而且以概率1成立。在适当的混合条件下，证明了一个中心极限定理和一个重对数律，描述了二阶渐近最优速率不可避免的波动。结果表明，在相同条件下，带有辅助信息的理想化莱姆佩尔 - 齐夫编码在一阶和二阶渐近意义下都是通用最优的。这些结果部分基于一个关于条件信息密度的新的几乎必然不变原理，该原理可能具有独立的研究价值。
