Universal lossless data compression with side information by using a conditional MPM grammar transform

A grammar transform is a transformation that converts any data sequence to be compressed into a grammar from which the original data sequence can be f ully reconstructed. In a grammar-based code, a data sequence is first conve rted into a grammar by a grammar transform and then losslessly encoded. Amo ng several recently proposed grammar transforms is the multilevel pattern m atching (MPM) grammar transform. In this paper, the MPM grammar transform i s first extended to the case of side information known to both the encoder and decoder, yielding a conditional MPM (CMPM) grammar transform. A new sim ple linear-time and space complexity algorithm is then proposed to implemen t the MPM and CMPM grammar transforms. Based on the CMPM grammar transform, a universal lossless data compression algorithm with side information is d eveloped, which can achieve asymptotically the conditional entropy rate of any stationary, ergodic source pair. It is shown that the algorithm's worst case redundancy/sample against the k-context conditional empirical entropy among all individual sequences of length n is upper-bounded by c (1/ log n ), where c is a constant. The proposed algorithm with side information is t he first in the coming family of conditional grammar-based codes, whose exp ected high efficiency is due to the efficiency of the corresponding uncondi tional codes.