...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Discrete Applied Mathematics >On the linear description of the Huffman trees polytope?
【24h】

On the linear description of the Huffman trees polytope?

机译：关于霍夫曼树多面体的线性描述？

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

摘要

The Huffman tree is a well known concept in data compression discovered by David Huffman in 1952 [7]. A Huffman tree is a binary tree and represents the most efficient binary code for a given alphabet with respect to a distribution of frequency of its characters. In this paper, we associate any Huffman tree of n leaves with the point in Qn having as coordinates the length of the paths from the root to every leaf from the left to right. We then study the convex hull, that we call Huffmanhedron, of those points associated with all the possible Huffman trees of n leaves. First, we present some basic properties of Huffmanhedron, especially, about its dimensions and its extreme vertices. Next we give a partial linear description of Huffmanhedron which includes in particular a complete characterization of the facet defining inequalities with nonnegative coefficients that are tight at a vertex corresponding to some maximum height Huffman tree (i.e. a Huffman tree of depth n ? 1). The latter contains a family of facet defining inequalities in which coefficients follow in some way the law of the Fibonacci sequence. This result shows that the number of facets of Huffmanhedron is at least a factorial of n and consequently shows that the facial structure of Huffmanhedron is rather complex. This is quite in contrast with the fact that using the algorithm of Huffman described in [7], one can minimize any linear objective function over the Huffmanhedron in O(n log n) time.Wealso give two procedures for lifting and facet composition allowing us to derive facet-defining inequalities from the ones in lower dimensions.
机译：霍夫曼树是David Huffman在1952年发现的数据压缩中的一个众所周知的概念[7]。霍夫曼树是一种二叉树，相对于其字符的频率分布，它代表了给定字母的最有效的二进制代码。在本文中，我们将n个叶子的任何霍夫曼树与Qn中的点相关联，该点具有从根到每个叶子从左到右的路径长度作为坐标。然后，我们研究与所有n个叶子的霍夫曼树相关的点的凸包，我们称其为霍夫曼面体。首先，我们介绍了Huffmanhedron的一些基本属性，尤其是有关其尺寸和极端顶点的信息。接下来，我们给出霍夫曼面体的部分线性描述，该描述特别包括刻面定义不等式的完整特征，该不等式的非负系数在对应于某个最大高度霍夫曼树（即深度n≤1的霍夫曼树）的顶点处紧密。后者包含定义不等式的一系列方面，其中系数以某种方式遵循斐波那契数列定律。该结果表明，Huffmanhedron的面数至少为n的阶乘，因此表明Huffmanhedron的面部结构相当复杂。这与使用[7]中所述的霍夫曼​​算法可以在O（n log n）时间内最小化霍夫曼面体上的任何线性目标函数的事实形成了鲜明的对比。从较低维的面定义不等式得出。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号