Using Statistical Encoding to Achieve Tree Succinctness Never Seen Before

摘要

We propose new entropy measures for trees, the known ones are H_k(e?'ˉ), the k-th order (tree label) entropy (Ferragina at al. 2005), and tree entropy H(e?'ˉ) (Jansson et al. 2006), the former considers only the tree labels and the latter only tree shape. The proposed entropy measures, H_k(e?'ˉ L) and H_k(L e?'ˉ), exploit the relation between the labels and the tree shape. We prove that they lower bound label entropy and tree entropy, respectively, i.e. H_k(e?'ˉ L) a?¤ H(e?'ˉ) and H_k(L e?'ˉ) a?¤ H_k(L). Besides being theoretically superior, the new measures are significantly smaller in practice. We also propose a new succinct representation of labeled trees which represents a tree T using one of the following bounds: T (H(e?'ˉ) + H_k(L e?'ˉ)) or T (H_k(e?'ˉ L) + H_k(L)). The representation is based on a new, simple method of partitioning the tree, which preserves both tree shape and node degrees. The previous state-of-the-art method of compressing the tree achieved T (H(e?'ˉ) + H_k(L)) bits, by combining the results of Ferragina at al. 2005 and Jansson et al. 2006; so proposed representation is not worse and often superior. Moreover, our representation supports standard tree navigation in constant time as well as more complex queries. Such a structure achieving this space bounds was not known before: aforementioned solution only worked for compression alone, our structure is the first which achieves H_k(e?'ˉ) for k0 and supports such queries. Lastly, our data structure is fairly simple, both conceptually and in terms of the implementation, moreover it uses known tools, which is a counter-argument to the claim that methods based on tree-partitioning are impractical.