数据序列的经验无损压缩

科学领域:

• 信息理论
• 数据压缩
• 统计推理

背景情况:

• 科尔莫戈罗夫复杂性为无损数据压缩提供了一个不可计算的理论边界.
• 香农的源代码定理确定了平均压缩的约束为nH,其中n是序列长度,H是.
• 最大概率估计 (MLE) 通常低估了真正的压缩边界.

研究的目的:

• 导出和分析单个数据序列的无损压缩.
• 调查数据压缩的正常化最大概率分布 (NML) 的最佳性.
• 将压缩绑定计算扩展到离散和连续数据,并用于生物信息学.

主要方法:

• 使用正常化最大概率 (NML) 分布,在最小意义上被证明是最佳的.
• 应用局部非对称的正常性来导出NML的非对称代码长度.
• 开发贝叶斯方法来预测最佳代码长度,从而产生混合代码.
• 使用不同的解析模型计算编码蛋白质DNA序列的压缩边界.

主要成果:

• NML代码的长度是通过分析推导出来的 nH{\displaystyle \mathrm {θ} n) + (d/2) log{\displaystyle \mathrm {n} 2π) + log{\displaystyle \mathrm {I} \mathrm {θ} 1/2) dθ + o{\displaystyle \mathrm {o} 1} .
• 一个通过贝叶斯预测得到的混合码的长度为nH{\displaystyle \mathrm {n} } + (d/2) log{\displaystyle \mathrm {n} }/2π + log{\displaystyle \mathrm {n} } \mathrm {n} } } 1/2) w{\displaystyle \mathrm {n} } + o{\displaystyle \mathrm {n} } 1).
• 当解析与氨基酸编码子对齐时,DNA序列的压缩是最大的,这表明了实际应用.
• 经验压缩边界随着字典大小的增加而改善.

结论:

• NML 分布为数据压缩界限提供了一个最佳的,可计算的方法.
• 衍生出来的非对称公式为离散和连续数据压缩提供了准确的估计.
• 解析策略显著影响压缩效率,特别是对于生物序列.
• 这项研究为了解和计算各种数据类型的理论压缩极限提供了强大的框架.