Coding on Countably Infinite Alphabets
Coding on Countably Infinite Alphabets
复制标题
DOI：
10.1109/tit.2008.2008150
复制
发表时间：
2009-01-01
影响因子：
2.5
通讯作者：
Gassiat, Elisabeth
中科院分区：
文献类型：
--
作者：
Boucheron, Stephane;Garivier, Aurelien;Gassiat, Elisabeth
本文描述了在可数无限字母上压缩源的通用无损编码策略。由边缘分布上的包络条件定义的无记忆源类为源自有限字母通用编码理论的编码技术提供了基准。我们证明了这类源类的最小最大冗余的上界和最小最大冗余的下界。一般上界强调了在无限字母表上下文中，相对于极大极小遗憾，规范化最大似然（NML）码的作用。下界是通过剪裁克雷切夫斯基-特罗菲莫夫编码器在有限字母上的冗余来推导的。最高可达对数。，常数)因子的边界与由代数递减（resp.）定义的源类匹配。（指数级消失）信封。描述了由代数消失包络定义的源类集合的有效和（几乎）自适应编码技术。这些结果将我们关于通用编码的知识扩展到已知参数推理的关键工具失败的上下文。
This paper describes universal lossless coding strategies for compressing sources on countably infinite alphabets. Classes of memoryless sources defined by an envellope condition on the marginal distribution provide benchmarks for coding techniques originating from the theory of universal coding over finite alphabets. We prove general upper bounds on minimax regret and lower bounds on minimax redundancy for such source classes. The general upper bounds emphasize the role of the normalized maximum likelihood (NML) codes with respect to minimax regret in the infinite alphabet context. Lower bounds are derived by tailoring sharp bounds on the redundancy of Krichevsky-Trofimov coders for sources over finite alphabets. Up to logarithmic (resp., constant) factors the bounds are matching for source classes defined by algebraically declining (resp., exponentially vanishing) envelopes. Effective and (almost) adaptive coding techniques are described for the collection of source classes defined by algebraically vanishing envelopes. Those results extend our knowledge concerning universal coding to contexts where the key tools from parametric inference are known to fail.