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

被引：0

作者：

IEEE ^{[1
]}

不详 ^{[2
]}

不详 ^{[3
]}

机构：

来源：

IEEE Trans. Inf. Theory | / 5卷 / 1498-1519期

基金：

以色列科学基金会;

关键词：

Algorithms - Block codes - Computational complexity - Computer simulation - Image compression - Image segmentation - Probability - Redundancy;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

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' weighting approach, asymptotically achieves a lower bound on the redundancy, and hence is optimal. The second scheme achieves redundancy of O(log N/N) when the transitions in the statistics are large, and O(log log N/log N) otherwise. The third approach always achieves redundancy of O(√log N/N). Obviously, the two fixed complexity approaches can be easily combined to achieve the better redundancy between the two. Simulation results support the analytical bounds derived for all the coding schemes.

引用