Universal lossless data compression with side information by using a conditional MPM grammar transform
Universal lossless data compression with side information by using a conditional MPM grammar transform
复制标题
使用条件 MPM 语法变换进行带有辅助信息的通用无损数据压缩
DOI：
10.1109/isit.2000.866596
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
J. Kieffer
中科院分区：
文献类型：
--
作者：
E. Yang;A. Kaltchenko;J. Kieffer
MPM（多级模式匹配）语法变换是由Kieffer、Yang、纳尔逊和Cosman开发的无损数据压缩算法的基础（参见IEEE Trans. on Inform.理论，2000年。在本文中，我们扩展的MPM语法变换的情况下，边信息已知的编码器和解码器，产生一个有条件的MPM语法变换被称为CMPM（r，I）变换。基于CMPM（r，I）变换，我们提出了一种带边信息的通用无损数据压缩算法CMPM算法，该算法具有线性的时间和存储复杂度，并且渐近地达到任意平稳、遍历信源对的条件熵率。使用辅助信息（如果有的话）进行数据压缩的优点是明显的;如果辅助信息与要压缩的序列高度相关，则可以显著降低压缩率。
The MPM (multilevel pattern matching) grammar transform underlies a lossless data compression algorithm developed by Kieffer, Yang, Nelson and Cosman (see IEEE Trans. on Inform. Theory, 2000. In this paper, we extend the MPM grammar transform to the case of side information known to both the encoder and decoder, yielding a conditional MPM grammar transform which is referred to as the CMPM (r,I) transform. Based on the CMPM (r,I) transform, we develop a universal lossless data compression algorithm with side information called the CMPM algorithm, which has linear time and storage complexity and asymptotically achieves the conditional entropy rate of any stationary, ergodic source pair. The advantage of using side information, if any, for data compression is obvious; one can considerably reduce the compression rate if the side information is highly correlated with a sequence to be compressed.