Entropy Bounds for Grammar-Based Tree Compressors
Danny Hucke, Markus Lohrey, Louisa Seelbach Benkner · IEEE Transactions on Information Theory · 2019
The definition of kth-order empirical entropy of strings is extended to node-labeled 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 kth-order empirical entropy plus some lower order terms. This generalizes recent results for grammar-based string compression to grammar-based tree compression. A long version of this paper can be found in [11].