Abstract | ||
---|---|---|
The definition of kappa th-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 kappa th-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]. |
Year | DOI | Venue |
---|---|---|
2019 | 10.1109/ISIT.2019.8849372 | 2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT) |
Keywords | Field | DocType |
Grammar-based compression, binary trees, empirical entropy, lossless compression | Discrete mathematics,Combinatorics,Binary encoding,Empirical entropy,Binary tree,Grammar,Gas compressor,Tree compression,Mathematics,Bounded function | Journal |
Volume | Citations | PageRank |
abs/1901.03155 | 0 | 0.34 |
References | Authors | |
13 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Danny Hucke | 1 | 19 | 6.31 |
Markus Lohrey | 2 | 903 | 75.40 |
Louisa Seelbach Benkner | 3 | 0 | 1.69 |