Low-complexity sequential lossless coding for piecewise-stationary memoryless sources

Three strongly sequential, lossless compression schemes, one with linearly growing per-letter computational complexity, and two with fixed per-letter complexity, are presented and analyzed for memoryless sources with abruptly changing statistics. The first method, which improves on Willems' weightin g approach, asymptotically achieves a lower bound on the redundancy, and he nce is optimal, The second scheme achieves redundancy of O(log N/N) when th e transitions in the statistics are large, and O (log log N/ log N) otherwi se. The third approach always achieves redundancy of O(root log N/N). Obvio usly, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the anal ytical bounds derived for all the coding schemes.