DocumentCode :
32454
Title :
A Universal Grammar-Based Code for Lossless Compression of Binary Trees
Author :
Jie Zhang ; En-Hui Yang ; Kieffer, John C.
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Waterloo, Waterloo, ON, Canada
Volume :
60
Issue :
3
fYear :
2014
fDate :
Mar-14
Firstpage :
1373
Lastpage :
1386
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.
Keywords :
binary codes; context-free grammars; data compression; decoding; tree codes; binary codeword; binary trees; code bits; context-free grammar; decoder; grammar-based binary tree compression code; lossless compression; lossless grammar-based code; probabilistic binary tree source models; universal code; universal grammar-based code; Binary trees; Decoding; Encoding; Grammar; Indexes; Labeling; Production; Grammar-based code; binary tree; context-free grammar; lossless compression; minimal DAG representation;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2013.2295392
Filename :
6689298
Link To Document :
بازگشت