Universal lossless compression of piecewise stationary slowly varying sources
Universal lossless compression of piecewise stationary slowly varying sources
复制标题
分段平稳缓慢变化源的通用无损压缩
DOI：
10.1109/dcc.2001.917168
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
D. Costello
中科院分区：
文献类型：
--
作者：
G. Shamir;D. Costello
研究了参数分段平稳信源在未知时间间隔内平稳段间统计量缓慢变化的通用无损压缩问题。在假设参数变化在变化区间内呈线性变化的前提下，推导出了该问题的两种不同设置下的最小描述长度原则。在第一设置中，假设所有改变具有相同的预先已知持续时间d，并且在第二设置中，所有统计改变具有未知持续时间。虽然在这两种情况下，每个段中每个未知统计参数的大多数信源的冗余度保持较低的下限，如在突然改变统计的情况下，额外码位0.5logm，其中m是平均段长度，在第一设置中，每个未知转换间隔所需的最小额外码长减少到logm-0.5logd，但令人惊讶的是，在第二设置中，如在突然改变统计的情况下，保持logm。演示了在这两种设置中达到下限的方案。
Universal lossless compression of parametric piecewise stationary sources with slow changes in the statistics between stationary segments that take place in unknown time intervals is investigated. The minimum description length (MDL) principle is derived for two different settings of this problem under the assumption that the parameter changes are linear over the change interval. In the first setting, it is assumed that all changes are of equal known in advance duration d, and in the second setting all statistics changes are of unknown durations. While in both cases the redundancy for most sources for each unknown statistical parameter in each segment remains lower bounded, as in the case of abruptly changing statistics, by 0.5 log m extra code bits, where m is the mean segment length, the minimum extra code-length required for each unknown transition interval decreases to log m-0.5 log d in the first setting, but surprisingly remains log m, as in the case of abruptly changing statistics, in the second. Schemes that achieve the lower bounds in both settings are demonstrated.