Entropy Bounds for Grammar-Based Tree Compressors

2019/01/10 by Hucke, Danny, Lohrey, Markus, Benkner, Louisa Seelbach · 1 citation
#68P30 #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1901.03155

Abstract

The definition of k^th-order empirical entropy of strings is extended to node labelled binary trees. A suitable binary encoding of tree straight-line programs (that have been used for grammar-based tree compression before) is shown to yield binary tree encodings of size bounded by the k^th-order empirical entropy plus some lower order terms. This generalizes recent results for grammar-based string compression to grammar-based tree compression.

Cited by

• Succinct Preferential Attachment Graphs

Related

• Entropy bounds for grammar compression
• A Universal Grammar-Based Code For Lossless Compression of Binary Trees
• Using statistical encoding to achieve tree succinctness never seen before
• Universal Tree Source Coding Using Grammar-Based Compression
• On Random Tree Structures, Their Entropy, and Compression