{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:30:59Z","timestamp":1750221059993,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T00:00:00Z","timestamp":1538352000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2013\/09\/B\/ST6\/02258"],"award-info":[{"award-number":["2013\/09\/B\/ST6\/02258"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1524312, CCF-0939370"],"award-info":[{"award-number":["CCF-1524312, CCF-0939370"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000098","name":"National Institutes of Health","doi-asserted-by":"publisher","award":["1U01CA198941-01"],"award-info":[{"award-number":["1U01CA198941-01"]}],"id":[{"id":"10.13039\/100000098","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2019,1,31]]},"abstract":"<jats:p>\n            We continue developing the information theory of structured data. In this article, we study models generating\n            <jats:italic>d<\/jats:italic>\n            -ary trees (\n            <jats:italic>d<\/jats:italic>\n            \u2265 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\u00efve implementation of these algorithms has a prohibitive time complexity of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            ) elementary arithmetic operations (each corresponding to a number\n            <jats:italic>f<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ,\n            <jats:italic>d<\/jats:italic>\n            ) of bit operations), but our efficient algorithms run in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>2<\/jats:italic>\n            <\/jats:sup>\n            ) of these operations, where\n            <jats:italic>n<\/jats:italic>\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).\n          <\/jats:p>","DOI":"10.1145\/3275444","type":"journal-article","created":{"date-parts":[[2018,10,1]],"date-time":"2018-10-01T12:15:55Z","timestamp":1538396155000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Entropy and Optimal Compression of Some General Plane Trees"],"prefix":"10.1145","volume":"15","author":[{"given":"Zbigniew","family":"Go\u0142\u0119biewski","sequence":"first","affiliation":[{"name":"Wroc\u0142aw University of Science and Technology, Wroc\u0142aw, Poland"}]},{"given":"Abram","family":"Magner","sequence":"additional","affiliation":[{"name":"Center for the Science of Information, IN, USA"}]},{"given":"Wojciech","family":"Szpankowski","sequence":"additional","affiliation":[{"name":"Purdue University, IN, USA"}]}],"member":"320","published-online":{"date-parts":[[2018,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0269964813000399"},{"volume-title":"Varieties of Increasing Trees","author":"Bergeron Fran\u00e7ois","key":"e_1_2_1_2_1","unstructured":"Fran\u00e7ois Bergeron , Philippe Flajolet , and Bruno Salvy . 1992. Varieties of Increasing Trees . Springer , Berlin , 24--48. Fran\u00e7ois Bergeron, Philippe Flajolet, and Bruno Salvy. 1992. Varieties of Increasing Trees. Springer, Berlin, 24--48."},{"key":"e_1_2_1_3_1","volume-title":"Psi-series method for equality of random trees and quadratic convolution recurrences. Random Structures 8 Algorithms 44, 1","author":"Chern Hua-Huai","year":"2014","unstructured":"Hua-Huai Chern , Mar\u00eda-In\u00e9s Fern\u00e1ndez-Camacho , Hsien-Kuei Hwang , and Conrado Mart\u00ednez . 2014. Psi-series method for equality of random trees and quadratic convolution recurrences. Random Structures 8 Algorithms 44, 1 ( 2014 ), 67--108. Hua-Huai Chern, Mar\u00eda-In\u00e9s Fern\u00e1ndez-Camacho, Hsien-Kuei Hwang, and Conrado Mart\u00ednez. 2014. Psi-series method for equality of random trees and quadratic convolution recurrences. Random Structures 8 Algorithms 44, 1 (2014), 67--108."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10005"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2173710"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974775.16"},{"key":"e_1_2_1_7_1","volume-title":"Elements of Information Theory","author":"Cover Thomas","unstructured":"Thomas Cover and Joy Thomas . 2006. Elements of Information Theory ( 2 nd ed.). John Wiley 8 Sons. Thomas Cover and Joy Thomas. 2006. Elements of Information Theory (2nd ed.). John Wiley 8 Sons.","edition":"2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548316000018"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-009-0009-x"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-211-75357-6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Daniel Zwillinger (Ed.). 2011. CRC Standard Mathematical Tables and Formulae. CRC Press Boca Raton FL.  Daniel Zwillinger (Ed.). 2011. CRC Standard Mathematical Tables and Formulae. CRC Press Boca Raton FL.","DOI":"10.1201\/b10980"},{"key":"e_1_2_1_12_1","volume-title":"Transfer theorems and asymptotic distributional results for m-ary search trees. Random Structures 8 Algorithms 26, 4 (July","author":"Fill James Allen","year":"2005","unstructured":"James Allen Fill and Nevin Kapur . 2005. Transfer theorems and asymptotic distributional results for m-ary search trees. Random Structures 8 Algorithms 26, 4 (July 2005 ), 359--391. James Allen Fill and Nevin Kapur. 2005. Transfer theorems and asymptotic distributional results for m-ary search trees. Random Structures 8 Algorithms 26, 4 (July 2005), 359--391."},{"key":"e_1_2_1_13_1","volume-title":"Patterns in random binary search trees. Random Structures 8 Algorithms 11, 3","author":"Flajolet Philippe","year":"1997","unstructured":"Philippe Flajolet , Xavier Gourdon , and Conrado Mart\u00ednez . 1997. Patterns in random binary search trees. Random Structures 8 Algorithms 11, 3 ( 1997 ), 223--244. Philippe Flajolet, Xavier Gourdon, and Conrado Mart\u00ednez. 1997. Patterns in random binary search trees. Random Structures 8 Algorithms 11, 3 (1997), 223--244."},{"key":"e_1_2_1_14_1","volume-title":"Analytic Combinatorics","author":"Flajolet Philippe","unstructured":"Philippe Flajolet and Robert Sedgewick . 2009. Analytic Combinatorics ( 1 st ed.). Cambridge University Press , New York, NY . Philippe Flajolet and Robert Sedgewick. 2009. Analytic Combinatorics (1st ed.). Cambridge University Press, New York, NY.","edition":"1"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006773"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2017.8006538"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2009.11.006"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1701495.1701625"},{"key":"e_1_2_1_19_1","volume-title":"The Art of Computer Programming, Volume 3: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1998. The Art of Computer Programming, Volume 3: Sorting and Searching ( 2 nd ed.). Addison Wesley Longman Publishing Co., Inc. , Redwood City, CA . Donald E. Knuth. 1998. The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.). Addison Wesley Longman Publishing Co., Inc., Redwood City, CA.","edition":"2"},{"key":"e_1_2_1_20_1","unstructured":"Tomasz \u0141uczak Abram Magner and Wojciech Szpankowski. 2017. Structural information and compression of scale-free graphs. Preprint.  Tomasz \u0141uczak Abram Magner and Wojciech Szpankowski. 2017. Structural information and compression of scale-free graphs. Preprint."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2016.7541492"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2015.7283005"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. 297--308","author":"Ralaivaosaona Dimbinaina","year":"2016","unstructured":"Dimbinaina Ralaivaosaona and Stephan Wagner . 2016 . Additive functionals of d-ary increasing trees . In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. 297--308 . Dimbinaina Ralaivaosaona and Stephan Wagner. 2016. Additive functionals of d-ary increasing trees. In Proceedings of the 27th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms. 297--308."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375837"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548314000443"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2013.2295392"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3275444","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3275444","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3275444","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:39Z","timestamp":1750207479000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3275444"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1,31]]}},"alternative-id":["10.1145\/3275444"],"URL":"https:\/\/doi.org\/10.1145\/3275444","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2018,10]]},"assertion":[{"value":"2017-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}