We give a representation for labeled ordered trees that supports labeled queries such as finding the i-th ancestor of a node with a given label. Our representation is succinct, namely the redundancy is small-o of the optimal space for storing the tree. This improves the representation of He et al. (ISAAC 2012) [8] which is succinct only when the entropy of the labels is omega(1). (C) 2014 Elsevier B.V. All rights reserved.
展开▼
