A Uniform Approach Towards Succinct Representation of Trees
A Uniform Approach Towards Succinct Representation of Trees
复制标题
树的简洁表示的统一方法
DOI：
10.1007/978-3-540-69903-3_17
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. I. Munro
中科院分区：
文献类型：
--
作者：
Arash Farzan;J. I. Munro
我们提出了一种统一的方法来简洁地表示各种树族。该方法基于树的两次递归分解为子树。将结构递归分解为子结构是简洁数据结构中的一种常见技术，在有序树[7，10]和动态二叉树[16，21]的简洁表示方面已显示出丰硕的成果。我们采取了一种方法，简化了现有序号树的表示，同时允许完整的导航操作集。应用于基数(即k元)树的方法产生空间最优的简洁表示，允许基数类型的运算(例如，确定标记为i的子代)以及完整的序数类型运算集(例如，报告节点左侧的兄弟姐妹的数量)。现有的空间优化简明表示法不能支持这两种类型的操作[2，19]。
我们演示了如何应用这种方法来获得自由树族的空间最优的简洁表示，其中子代的顺序是不重要的。此外，我们还证明了我们的方法可以用来获得基于熵的简洁表示。我们表明，我们的方法与Jansson等人提出的度分布熵相匹配。[13]。我们讨论了我们的方法可以使其适应于各种其他的熵度量。
We propose a uniform approach for succinct representation of various families of trees. The method is based on two recursive decomposition of trees into subtrees. Recursive decomposition of a structure into substructures is a common technique in succinct data structures and has been shown fruitful in succinct representation of ordinal trees [7,10] and dynamic binary trees [16,21]. We take an approach that simplifies the existing representation of ordinal trees while allowing the full set of navigational operations. The approach applied to cardinal (i.e. k-ary) trees yields a space-optimal succinct representation allowing cardinal-type operations (e.g. determining child labeled i) as well as the full set of ordinal-type operations (e.g. reporting the number of siblings to the left of a node). Existing space-optimal succinct representations had not been able to support both types of operations [2,19].
We demonstrate how the approach can be applied to obtain a space-optimal succinct representation for the family of free trees where the order of children is insignificant. Furthermore, we show that our approach can be used to obtain entropy-based succinct representations. We show that our approach matches the degree-distribution entropy suggested by Jansson etal. [13]. We discuss that our approach can be made adaptive to various other entropy measures.