Wavelet Trees have been introduced by Grossi et al. in SODA 2003 and have been rapidly recognized as a very flexible tool for the design of compressed full-text indexes and data compression algorithms. Although several papers have investigated the properties and usefulness of this data structure in the full-text indexing scenario, its impact on data compression has not been fully explored. In this paper we provide a throughout theoretical analysis of a wide class of compression algorithms based on Wavelet Trees. Also, we propose a novel framework, called Pruned Wavelet Trees, that aims for the best combination of Wavelet Trees of properly-designed shapes and compressors either binary (like, Run-Length encoders) or non-binary (like, Huffman and Arithmetic encoders). © 2009 Elsevier Inc. All rights reserved.
The myriad virtues of Wavelet Trees
Manzini Giovanni
2009
Abstract
Wavelet Trees have been introduced by Grossi et al. in SODA 2003 and have been rapidly recognized as a very flexible tool for the design of compressed full-text indexes and data compression algorithms. Although several papers have investigated the properties and usefulness of this data structure in the full-text indexing scenario, its impact on data compression has not been fully explored. In this paper we provide a throughout theoretical analysis of a wide class of compression algorithms based on Wavelet Trees. Also, we propose a novel framework, called Pruned Wavelet Trees, that aims for the best combination of Wavelet Trees of properly-designed shapes and compressors either binary (like, Run-Length encoders) or non-binary (like, Huffman and Arithmetic encoders). © 2009 Elsevier Inc. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
