...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>IEEE Transactions on Information Theory >Universal Enumerative Coding for Tree Models
【24h】

Universal Enumerative Coding for Tree Models

机译：树模型的通用枚举编码

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Efficient enumerative coding for tree sources is, in general, surprisingly intricate—a simple uniform encoding of type classes, which is asymptotically optimal in expectation for many classical models, such as FSMs, turns out not to be so in this case. We describe an efficiently computable enumerative code that is universal in the family of tree models in the sense that, for a string emitted by an unknown source whose model is supported on a known tree, the expected normalized code length of the encoding approaches the entropy rate of the source with a convergence rate $(K/2)(log n)$, where $K$ is the number of free parameters of the model family. Based on recent results characterizing type classes of context trees, the code consists of the index of the sequence in the tree type class, and an efficient description of the class itself using a nonuniform encoding of selected string counts. The results are extended to a twice-universal setting, where the tree underlying the source model is unknown.
机译：通常，对树源的有效枚举编码令人惊讶地错综复杂-类型类的简单统一编码，对于许多经典模型（例如FSM），在期望上渐近最优，事实证明并非如此。我们描述了一种有效的可计算枚举代码，该代码在树模型家族中是通用的，在某种意义上，对于由未知源发出的字符串（其模型在已知树上得到支持），编码的预期归一化代码长度接近熵率源的收敛速度为（$ K / 2）（log n）/ n $，其中$ K $是模型族的自由参数的数量。基于表征上下文树类型类的最新结果，该代码包括树类型类中序列的索引，以及使用选定字符串计数的非均匀编码对类本身的有效描述。结果扩展到两次通用设置，其中源模型基础的树是未知的。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号