A Universal Grammar-Based Code for Lossless Compression of Binary Trees

We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is tra...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on information theory 2014-03, Vol.60 (3), p.1373-1386
Main Authors: Jie Zhang, En-Hui Yang, Kieffer, John C.
Format: Article
Language:English
Subjects:
Applied sciences
Binary system
binary tree
Binary trees
Codes
Coding, codes
context-free grammar
Decoding
Encoding
Exact sciences and technology
Grammar
Grammar-based code
Indexes
Information theory
Information, signal and communications theory
Labeling
lossless compression
minimal DAG representation
Production
Signal and communications theory
Telecommunications and information theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3
cites cdi_FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3
container_end_page 1386
container_issue 3
container_start_page 1373
container_title IEEE transactions on information theory
container_volume 60
creator Jie Zhang
En-Hui Yang
Kieffer, John C.
description We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.
doi_str_mv 10.1109/TIT.2013.2295392
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1109_TIT_2013_2295392</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>6689298</ieee_id><sourcerecordid>3223844301</sourcerecordid><originalsourceid>FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3</originalsourceid><addsrcrecordid>eNo9UE1LAzEQDaJgrd4FLwHxuDWTj93k2BathYKX7TmMSRa2bHdr0gr996a09DRf772ZeYQ8A5sAMPNeL-sJZyAmnBslDL8hI1CqKkyp5C0ZMQa6MFLqe_KQ0iaXUgEfkcWUrvv2L8SEHV1E3G4xFjNMwdP54ANthkhXQ0pdSCl3truYk3bo6dDQWdtjPNI6hpAeyV2DXQpPlzgm68-Pev5VrL4Xy_l0VThRin3hOGgwmjvvHUOBDJX8QWEq0KgaNFVQvvGSc0DPpAZRegVBO-641xIaMSavZ91dHH4PIe3tZjjEPq-0oBgTTFalzih2RrmYb4-hsbvY5s-OFpg92WWzXfZkl73YlSlvF2FMDrsmYu_adOVxLRmXWmXcyxnXhhCu47LUhhst_gFBZ3G5</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1500304768</pqid></control><display><type>article</type><title>A Universal Grammar-Based Code for Lossless Compression of Binary Trees</title><source>IEEE Electronic Library (IEL) Journals</source><creator>Jie Zhang ; En-Hui Yang ; Kieffer, John C.</creator><creatorcontrib>Jie Zhang ; En-Hui Yang ; Kieffer, John C.</creatorcontrib><description>We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.</description><identifier>ISSN: 0018-9448</identifier><identifier>EISSN: 1557-9654</identifier><identifier>DOI: 10.1109/TIT.2013.2295392</identifier><identifier>CODEN: IETTAW</identifier><language>eng</language><publisher>New York, NY: IEEE</publisher><subject>Applied sciences ; Binary system ; binary tree ; Binary trees ; Codes ; Coding, codes ; context-free grammar ; Decoding ; Encoding ; Exact sciences and technology ; Grammar ; Grammar-based code ; Indexes ; Information theory ; Information, signal and communications theory ; Labeling ; lossless compression ; minimal DAG representation ; Production ; Signal and communications theory ; Telecommunications and information theory</subject><ispartof>IEEE transactions on information theory, 2014-03, Vol.60 (3), p.1373-1386</ispartof><rights>2015 INIST-CNRS</rights><rights>Copyright The Institute of Electrical and Electronics Engineers, Inc. (IEEE) Mar 2014</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3</citedby><cites>FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/6689298$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>314,780,784,27923,27924,54795</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=28402485$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Jie Zhang</creatorcontrib><creatorcontrib>En-Hui Yang</creatorcontrib><creatorcontrib>Kieffer, John C.</creatorcontrib><title>A Universal Grammar-Based Code for Lossless Compression of Binary Trees</title><title>IEEE transactions on information theory</title><addtitle>TIT</addtitle><description>We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.</description><subject>Applied sciences</subject><subject>Binary system</subject><subject>binary tree</subject><subject>Binary trees</subject><subject>Codes</subject><subject>Coding, codes</subject><subject>context-free grammar</subject><subject>Decoding</subject><subject>Encoding</subject><subject>Exact sciences and technology</subject><subject>Grammar</subject><subject>Grammar-based code</subject><subject>Indexes</subject><subject>Information theory</subject><subject>Information, signal and communications theory</subject><subject>Labeling</subject><subject>lossless compression</subject><subject>minimal DAG representation</subject><subject>Production</subject><subject>Signal and communications theory</subject><subject>Telecommunications and information theory</subject><issn>0018-9448</issn><issn>1557-9654</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2014</creationdate><recordtype>article</recordtype><recordid>eNo9UE1LAzEQDaJgrd4FLwHxuDWTj93k2BathYKX7TmMSRa2bHdr0gr996a09DRf772ZeYQ8A5sAMPNeL-sJZyAmnBslDL8hI1CqKkyp5C0ZMQa6MFLqe_KQ0iaXUgEfkcWUrvv2L8SEHV1E3G4xFjNMwdP54ANthkhXQ0pdSCl3truYk3bo6dDQWdtjPNI6hpAeyV2DXQpPlzgm68-Pev5VrL4Xy_l0VThRin3hOGgwmjvvHUOBDJX8QWEq0KgaNFVQvvGSc0DPpAZRegVBO-641xIaMSavZ91dHH4PIe3tZjjEPq-0oBgTTFalzih2RrmYb4-hsbvY5s-OFpg92WWzXfZkl73YlSlvF2FMDrsmYu_adOVxLRmXWmXcyxnXhhCu47LUhhst_gFBZ3G5</recordid><startdate>20140301</startdate><enddate>20140301</enddate><creator>Jie Zhang</creator><creator>En-Hui Yang</creator><creator>Kieffer, John C.</creator><general>IEEE</general><general>Institute of Electrical and Electronics Engineers</general><general>The Institute of Electrical and Electronics Engineers, Inc. (IEEE)</general><scope>97E</scope><scope>RIA</scope><scope>RIE</scope><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>7SP</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>20140301</creationdate><title>A Universal Grammar-Based Code for Lossless Compression of Binary Trees</title><author>Jie Zhang ; En-Hui Yang ; Kieffer, John C.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2014</creationdate><topic>Applied sciences</topic><topic>Binary system</topic><topic>binary tree</topic><topic>Binary trees</topic><topic>Codes</topic><topic>Coding, codes</topic><topic>context-free grammar</topic><topic>Decoding</topic><topic>Encoding</topic><topic>Exact sciences and technology</topic><topic>Grammar</topic><topic>Grammar-based code</topic><topic>Indexes</topic><topic>Information theory</topic><topic>Information, signal and communications theory</topic><topic>Labeling</topic><topic>lossless compression</topic><topic>minimal DAG representation</topic><topic>Production</topic><topic>Signal and communications theory</topic><topic>Telecommunications and information theory</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Jie Zhang</creatorcontrib><creatorcontrib>En-Hui Yang</creatorcontrib><creatorcontrib>Kieffer, John C.</creatorcontrib><collection>IEEE All-Society Periodicals Package (ASPP) 2005-present</collection><collection>IEEE All-Society Periodicals Package (ASPP) 1998-Present</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Electronics &amp; Communications Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>IEEE transactions on information theory</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Jie Zhang</au><au>En-Hui Yang</au><au>Kieffer, John C.</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Universal Grammar-Based Code for Lossless Compression of Binary Trees</atitle><jtitle>IEEE transactions on information theory</jtitle><stitle>TIT</stitle><date>2014-03-01</date><risdate>2014</risdate><volume>60</volume><issue>3</issue><spage>1373</spage><epage>1386</epage><pages>1373-1386</pages><issn>0018-9448</issn><eissn>1557-9654</eissn><coden>IETTAW</coden><abstract>We consider the problem of lossless compression of binary trees, with the aim of reducing the number of code bits needed to store or transmit such trees. A lossless grammar-based code is presented, which encodes each binary tree into a binary codeword in two steps. In the first step, the tree is transformed into a context-free grammar from which the tree can be reconstructed. In the second step, the context-free grammar is encoded into a binary codeword. The decoder of the grammar-based code decodes the original tree from its codeword by reversing the two encoding steps. It is shown that the resulting grammar-based binary tree compression code is a universal code on a family of probabilistic binary tree source models satisfying certain weak restrictions.</abstract><cop>New York, NY</cop><pub>IEEE</pub><doi>10.1109/TIT.2013.2295392</doi><tpages>14</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0018-9448
ispartof IEEE transactions on information theory, 2014-03, Vol.60 (3), p.1373-1386
issn 0018-9448
1557-9654
language eng
recordid cdi_crossref_primary_10_1109_TIT_2013_2295392
source IEEE Electronic Library (IEL) Journals
subjects Applied sciences
Binary system
binary tree
Binary trees
Codes
Coding, codes
context-free grammar
Decoding
Encoding
Exact sciences and technology
Grammar
Grammar-based code
Indexes
Information theory
Information, signal and communications theory
Labeling
lossless compression
minimal DAG representation
Production
Signal and communications theory
Telecommunications and information theory
title A Universal Grammar-Based Code for Lossless Compression of Binary Trees
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-08T15%3A56%3A03IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20Universal%20Grammar-Based%20Code%20for%20Lossless%20Compression%20of%20Binary%20Trees&rft.jtitle=IEEE%20transactions%20on%20information%20theory&rft.au=Jie%20Zhang&rft.date=2014-03-01&rft.volume=60&rft.issue=3&rft.spage=1373&rft.epage=1386&rft.pages=1373-1386&rft.issn=0018-9448&rft.eissn=1557-9654&rft.coden=IETTAW&rft_id=info:doi/10.1109/TIT.2013.2295392&rft_dat=%3Cproquest_cross%3E3223844301%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c363t-c2181982cddc0a3a0a54ba39718a5fa97e5dfd4221ad048136d51e8c2c2d841f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1500304768&rft_id=info:pmid/&rft_ieee_id=6689298&rfr_iscdi=true