Low-complexity sequential lossless coding for piecewise-stationary memoryless sources
Low-complexity sequential lossless coding for piecewise-stationary memoryless sources
复制标题
DOI：
10.1109/18.771150
复制
发表时间：
1998-08
期刊：
影响因子：
--
通讯作者：
G. Shamir;N. Merhav
中科院分区：
文献类型：
--
作者：
G. Shamir;N. Merhav
提出并分析了具有突然变化统计的无内存源的三种强顺序无损压缩方案，其中一种具有线性增长的每字母计算复杂度，另两种具有固定的每字母复杂度。第一种方法改进了Willems（1994）的加权方法，渐近地达到了冗余的下界，因此是最优的。第二种方案在统计迁移量较大时实现O（log N/N）冗余，在其他情况下实现O（log log N/log N）冗余。第三种方法总是达到0 （/spl径向/log N/N）的冗余。显然，这两种固定复杂度的方法可以很容易地结合起来，以实现两者之间更好的冗余。仿真结果支持所有编码方案的解析界。
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' (1994) 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 (/spl radic/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.