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!
Description
Summary: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.
ISSN:0018-9448
1557-9654
DOI:10.1109/TIT.2013.2295392