On strongly sequential compression of sources with abrupt changes in statistics
Gil I. Shamir · 2004
An asymptotically optimal low-complexity strongly sequential compression scheme is proposed for universal lossless coding of memoryless sources with piecewise stationary abruptly changing statistics. The scheme is shown to achieve the lower bound for this universal coding problem even in a strongly sequential regime, where the horizon (i.e., the length of the data sequence to be encoded) is unknown when the algorithm starts to compress the data. Simulation results support the analytical results.