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

DOI10.1109/TIT.2013.2295392MaRDI QIDQ2986464zbMATH OpenFDO

Authors Jie Zhang, Enhui Yang, John C. Kieffer

Publication date 16 May 2017

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.7392

Mathematics Subject Classification ID

Information theory (general) (94A15) Decoding (94B35)

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.

Cited in

(5)

• Distinct fringe subtrees in random trees
• Compression of dynamic graphs generated by a duplication model
• Constructing small tree grammars and small circuits for formulas
• Grammar-Based Tree Compression
• Lossless Compression of Binary Trees With Correlated Vertex Names

This page was built for publication: A Universal Grammar-Based Code for Lossless Compression of Binary Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986464)