Paper Info
Title
On the complexity of optimal tree pruning for source coding
Abstract
Tree-structured vector quantization is a technique to represent a codebook that simplifies encoding as well as quantizer design. The authors define the notion of an optimal pruned tree subject to a cost constraint, and study the computational complexity of finding such a tree. Under the assumption that all trees are equally probable, it is shown that on average the number of pruned trees in a given tree is exponential in the number of leaves. Finding an optimal pruned tree subject to constraints such as entropy or the expected depth is NP-hard. However, when the constraint is the number of leaves, the problem can be solved in O(nk) time, where n is the size of the initial tree and k the constraint size. Experimental results for image compression show the performance of the optimal pruned tree to be comparable with that of full-search vector quantizers
Year
DOI
Venue
1991
10.1109/DCC.1991.213363
Data Compression Conference
Keywords
Field
DocType
tree-structured vector quantisation,constraint size,trees (mathematics),number of leaves,data compression,encoding,constraint theory,codebook,computational complexity,source coding,picture processing,optimal tree pruning,entropy,optimal pruned tree,performance,cost constraint,image compression,vector quantization,computer science,algorithm design and analysis,source code,tree structure,time measurement,cost function
Range tree,AVL tree,Tree rearrangement,K-ary tree,Optimal binary search tree,Theoretical computer science,Segment tree,Mathematics,Search tree,Interval tree
Conference
ISBN
Citations 
PageRank 
0-8186-9202-2
6
1.98
References 
Authors
6
3
Name
Order
Citations
PageRank
Jianhua Lin182.87
James A. Storer2931156.06
Martin Cohn34113.54