On Universal Compression with Constant Random Access

In new applications of data compression, it is desired to have random access to any block of the compressed dataset (without the need to decompress the entire compressed sequence and thus accessing all the stored bits in memory). In this work, we analyze the problem of universal data compression with random access. Building on the work of Mazumdar, Chandar, and Wornell (2015), we discuss a systematic scheme to achieve close to optimal compression with finite random access. We first analyze the performance of the scheme for i.i.d sources. Using the gained intuition, for the more general class of Markov sources, we show the existence of finite random access compression schemes. Finally, we discuss a generic scheme which can be used to convert any universal compressor (e.g., Lempel-Ziv based schemes) into a finite random access universal compressor.