Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Entropy and Optimal Compression of Some General Plane Trees

Entropy and Optimal Compression of Some General Plane Trees We continue developing the information theory of structured data. In this article, we study models generating d-ary trees (d 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O(nd) elementary arithmetic operations (each corresponding to a number f(n, d) of bit operations), but our efficient algorithms run in O(n2) of these operations, where n is the number of nodes. It turns out that extending source coding (i.e., compression) from sequences to advanced data structures such as degree-unconstrained trees is mathematically quite challenging and leads to recurrences that find ample applications in the information theory of general structures (e.g., to analyze the information content of degree-unconstrained non-plane trees). http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Entropy and Optimal Compression of Some General Plane Trees

Download PDF
23 pages

Loading next page...
 
/lp/association-for-computing-machinery/entropy-and-optimal-compression-of-some-general-plane-trees-naJsZO85c9
Publisher
Association for Computing Machinery
Copyright
Copyright © 2018 ACM
ISSN
1549-6325
eISSN
1549-6333
DOI
10.1145/3275444
Publisher site
See Article on Publisher Site

Abstract

We continue developing the information theory of structured data. In this article, we study models generating d-ary trees (d 2) and trees with unrestricted degree. We first compute the entropy which gives us the fundamental lower bound on compression of such trees. Then we present efficient compression algorithms based on arithmetic encoding that achieve the entropy within a constant number of bits. A naïve implementation of these algorithms has a prohibitive time complexity of O(nd) elementary arithmetic operations (each corresponding to a number f(n, d) of bit operations), but our efficient algorithms run in O(n2) of these operations, where n is the number of nodes. It turns out that extending source coding (i.e., compression) from sequences to advanced data structures such as degree-unconstrained trees is mathematically quite challenging and leads to recurrences that find ample applications in the information theory of general structures (e.g., to analyze the information content of degree-unconstrained non-plane trees).

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Oct 1, 2018

Keywords: Arithmetic coding

References

  • Entropy of some models of sparse random graphs with vertex-names
    Aldous, David J.; Ross, Nathan
  • Varieties of Increasing Trees
    Bergeron, François; Flajolet, Philippe; Salvy, Bruno
  • Psi-series method for equality of random trees and quadratic convolution recurrences
    Chern, Hua-Huai; Fernández-Camacho, María-Inés; Hwang, Hsien-Kuei; Martínez, Conrado
  • Phase changes in random m-ary search trees and generalized quicksort
    Chern, Hua-Huai; Hwang, Hsien-Kuei
  • Compression of graphical structures: Fundamental limits, algorithms, and experiments
    Choi, Yongwook; Szpankowski, Wojciech
  • On Symmetries of Non-plane Trees in a Non-uniform Model
    Cichoń, Jacek; Magner, Abram; Szpankowski, Wojciech; Turowski, Krzysztof
  • Elements of Information Theory (2nd ed
    Cover, Thomas; Thomas, Joy
  • Shape measures of random increasing k-trees
    Darrasse, Alexis; Hwang, Hsien-Kuei; Soria, Michèle
  • The height of increasing trees
    Drmota, Michael
  • Random Trees: An Interplay Between Combinatorics and Probability (1st ed
    Drmota, Michael
  • CRC Standard Mathematical Tables and Formulae
    (Ed, Daniel Zwillinger
  • Transfer theorems and asymptotic distributional results for m-ary search trees
    Fill, James Allen; Kapur, Nevin
  • Patterns in random binary search trees
    Flajolet, Philippe; Gourdon, Xavier; Martínez, Conrado
  • Analytic Combinatorics (1st ed
    Flajolet, Philippe; Sedgewick, Robert
  • On structural entropy of uniform random intersection graphs
    Gołebiewski, Zbigniew; Kardas, Marcin; Lemiesz, Jakub; Majcher, Krzysztof
  • Entropy of some general plane trees
    Gołebiewski, Zbigniew; Magner, Abram; Szpankowski, Wojciech
  • Generalized Stirling permutations, families of increasing trees and urn models
    Janson, Svante; Kuba, Markus; Panholzer, Alois
  • Structural complexity of random binary trees
    Kieffer, John C.; Yang, En hui; Szpankowski, Wojciech
  • The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed
    Knuth, Donald E.
  • Structural information and compression of scale-free graphs
    Łuczak, Tomasz; Magner, Abram; Szpankowski, Wojciech
  • Lossless compression of binary trees with correlated vertex names
    Magner, Abram; Turowski, Krzysztof; Szpankowski, Wojciech
  • Automata and graph compression
    Mohri, Mehryar; Riley, Michael; Suresh, Ananda Theertha
  • Additive functionals of d-ary increasing trees
    Ralaivaosaona, Dimbinaina; Wagner, Stephan
  • Improved master theorems for divide-and-conquer recurrences
    Roura, Salvador
  • Central limit theorems for additive tree parameters with small toll functions
    Wagner, Stephan
  • A universal grammar-based code for lossless compression of binary trees
    Zhang, Jie; Yang, En hui; Kieffer, John C.