Back to Search
Start Over
The myriad virtues of Wavelet Trees
- Source :
-
Information & Computation . Aug2009, Vol. 207 Issue 8, p849-866. 18p. - Publication Year :
- 2009
-
Abstract
- 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). [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 08905401
- Volume :
- 207
- Issue :
- 8
- Database :
- Academic Search Index
- Journal :
- Information & Computation
- Publication Type :
- Academic Journal
- Accession number :
- 40628277
- Full Text :
- https://doi.org/10.1016/j.ic.2008.12.010