Please use this identifier to cite or link to this item: https://doi.org/10.1016/j.jcss.2011.09.002
DC FieldValue
dc.titleUltra-succinct representation of ordered trees with applications
dc.contributor.authorJansson, J.
dc.contributor.authorSadakane, K.
dc.contributor.authorSung, W.-K.
dc.date.accessioned2013-07-04T07:41:52Z
dc.date.available2013-07-04T07:41:52Z
dc.date.issued2012
dc.identifier.citationJansson, J., Sadakane, K., Sung, W.-K. (2012). Ultra-succinct representation of ordered trees with applications. Journal of Computer and System Sciences 78 (2) : 619-631. ScholarBank@NUS Repository. https://doi.org/10.1016/j.jcss.2011.09.002
dc.identifier.issn00220000
dc.identifier.urihttp://scholarbank.nus.edu.sg/handle/10635/39449
dc.description.abstractThere 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) 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) bits. We also describe applications of the compressed DFUDS representation to ultra-succinct compressed suffix trees and labeled trees. © 2011 Elsevier Inc. All Rights Reserved.
dc.description.urihttp://libproxy1.nus.edu.sg/login?url=http://dx.doi.org/10.1016/j.jcss.2011.09.002
dc.sourceScopus
dc.subjectCompressed suffix tree
dc.subjectOrdered tree
dc.subjectSuccinct data structure
dc.subjectTree degree entropy
dc.subjectXbw
dc.typeArticle
dc.contributor.departmentCOMPUTER SCIENCE
dc.description.doi10.1016/j.jcss.2011.09.002
dc.description.sourcetitleJournal of Computer and System Sciences
dc.description.volume78
dc.description.issue2
dc.description.page619-631
dc.description.codenJCSSB
dc.identifier.isiut000299719100015
Appears in Collections:Staff Publications

Show simple item record
Files in This Item:
There are no files associated with this item.

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.