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.
展开▼
机译：针对具有突然变化的统计数据的无记忆源，提出并分析了三种强顺序无损压缩方案，一种具有线性增长的每个字母的计算复杂度，另一种具有固定的每个字母的复杂度。第一种方法改进了Willems（1994）的加权方法，渐近地实现了冗余的下限，因此是最优的。当统计数据的过渡较大时，第二种方案可实现O（log N / N）的冗余，否则实现O（log log N / log N）的冗余。第三种方法总是实现O的冗余（/ splidic / log N / N）。显然，可以轻松地将这两种固定复杂性方法组合在一起，以实现两者之间更好的冗余。仿真结果支持为所有编码方案得出的解析范围。
展开▼
