Asymptotically optimal low-complexity sequential lossless coding for piecewise-stationary memoryless sources - Part I: The regular case

The lower bound on the redundancy for lossless universal coding of regular memoryless sources with a bounded number of abrupt changes in the statistic s is shown to be asymptotically achievable using a fixed per-letter computa tional complexity sequential compression scheme with fixed storage complexi ty. The scheme which outperforms any other known fixed-complexity scheme wh en regularity conditions hold is presented, and its redundancy is upper-bou nded. Although the upper bounds are merely asymptotic, simulation results s how that even for relatively short sequences, the redundancy obtained by as ymptotically optimal schemes of higher complexity can still be achieved wit h fixed per-letter complexity. Furthermore, in practice, a fixed-complexity scheme based on the proposed scheme can in most cases achieve optimal redu ndancy even when the regularity conditions do not hold.