کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
430098 687798 2012 13 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Ultra-succinct representation of ordered trees with applications
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Ultra-succinct representation of ordered trees with applications
چکیده انگلیسی

There exist two well-known succinct representations of ordered trees: BP (balanced parenthesis) (Munro and Raman, 2001) [20] and DFUDS (depth first unary degree sequence) (Benoit et al., 2005) [1]. Both have size 2n+o(n)2n+o(n) bits for n-node trees, which asymptotically matches the information-theoretic lower bound. Importantly, many fundamental operations on trees can be done in constant time on the word RAM when using BP or DFUDS, for example finding the parent, the first child, the next sibling, the number of descendants, etc. Although the space needed to store the BP or DFUDS representation of an ordered tree matches the lower bound, this is not optimal when we consider encodings for certain special classes of trees such as trees in which every internal node has exactly two children. In this paper, we introduce a new, conditional entropy for trees called the tree degree entropy, and give a succinct tree representation with matching size. We call such a representation an ultra-succinct data structure  . We show how to modify the DFUDS representation to obtain a “compressed DFUDS”, and as a consequence, a tree in which every internal node has exactly two children can be represented in n+o(n)n+o(n) bits. We also describe applications of the compressed DFUDS representation to ultra-succinct compressed suffix trees and labeled trees.


► We introduce a new, conditional entropy for trees called the tree degree entropy.
► We give a new succinct ordered tree representation.
► We propose auxiliary indexes for computing depths and level ancestors.
► A smaller representation of compressed suffix trees is proposed.
► An application of the new tree representation for labeled trees is given.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 78, Issue 2, March 2012, Pages 619–631
نویسندگان
, , ,